자료구조 기초3 - 이진 트리 Binary Tree

 

오늘은 이진 트리(Binary Tree)에 대해 이야기 해보려고 한다.

 

정의

이진 트리는 노드(Node)로 구성된 자료 구조로, 각 노드가 최대 두 개의 자식 노드를 가질 수 있다. 이진 트리의 노드들은 다음과 같은 구성 요소를 가진다:

 

 

 

 

 

• 노드(Node): 트리의 기본 단위로, 데이터를 저장하고 왼쪽 및 오른쪽 자식 노드에 대한 참조를 가진다.
• 루트 노드(Root Node): 트리의 최상위 노드로, 트리는 이 노드에서 시작된다.
• 자식 노드(Child Node): 다른 노드에 의해 참조되는 노드로, 왼쪽 자식 노드와 오른쪽 자식 노드로 나뉜다.
  • 왼쪽 자식(Left Child): 왼쪽에 연결된 하위 노드.
  • 오른쪽 자식(Right Child): 오른쪽에 연결된 하위 노드.
• 리프 노드(Leaf Node): 자식 노드가 없는 노드이다.
• 서브트리(Subtree): 트리 내의 임의의 노드를 루트로 하는 트리이다.

 

       A
      / \
     B   C
    / \ / \
   D  E F  G

 

이진 트리의 구조위의 구조에서:

• A는 루트 노드이다.
• B와 C는 A의 자식 노드이다.
• D와 E는 B의 자식 노드이다.
• F와 G는 C의 자식 노드이다.
• D, E, F, G는 리프 노드이다.

 

이진 탐색 트리(BST)의 연산 속도

BST의 주요 연산인 삽입, 삭제, 검색의 시간 복잡도는 트리의 높이에 따라 달라진다. 트리의 높이가 h일 때, 이들 연산의 평균적인 시간 복잡도는 O(h)이다.

 

최악의 경우

• 최악의 경우, 트리는 한쪽으로 치우친 일직선 모양(불균형 트리)이 된다.
• 이 경우, 트리의 높이는 노드의 개수 n과 같아져서 시간 복잡도는 O(n)이 된다.

예를 들어, 오름차순으로 노드를 삽입하면 다음과 같은 트리가 된다:

 

    1
     \
      2
       \
        3
         \
          4
           \
            5

 

이 트리의 높이는 5이고, 각 연산은 최대 5번의 비교를 필요로 한다.

최선의 경우

• 최선의 경우, 트리는 균형 잡힌 완전 이진 트리다.
• 이 경우, 트리의 높이는 log2(n)이 되어서 시간 복잡도는 O(logn)이 된다.

예를 들어, 균형 잡힌 트리는 다음과 같다:

 

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

 

이 트리의 높이는 3이고, 각 연산은 최대 3번의 비교를 필요로 한다.

 

 

이진 트리의 주요 연산

1. 삽입(Insertion): 새로운 노드를 트리에 추가한다.
2. 검색(Search): 특정 값을 가진 노드를 찾는다.
3. 삭제(Deletion): 특정 값을 가진 노드를 트리에서 제거한다.
4. 순회(Traversal): 트리의 모든 노드를 방문하여 데이터를 처리한다. 순회의 종류로는 중위 순회(Inorder Traversal), 전위 순회(Preorder Traversal), 후위 순회(Postorder Traversal)가 있다.

 

 

이진 트리의 종류

1. 포화 이진 트리(Full Binary Tree):
   • 모든 노드가 0개 또는 2개의 자식 노드를 가진다.
   • 모든 리프 노드(자식이 없는 노드)가 같은 깊이에 있다.
2. 완전 이진 트리(Complete Binary Tree):
   • 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있다.
   • 마지막 레벨의 노드들이 왼쪽부터 오른쪽으로 순차적으로 채워져 있다.
3. 정 이진 트리(Perfect Binary Tree):
   • 모든 레벨이 완전히 채워져 있다.
   • 모든 리프 노드가 같은 깊이에 있다.
4. 이진 탐색 트리(Binary Search Tree, BST):
   • 각 노드의 왼쪽 자식 노드는 자신보다 작고, 오른쪽 자식 노드는 자신보다 큰 값을 가진다.
   • 중복된 값을 허용하지 않다.
5. 균형 이진 트리(Balanced Binary Tree):
   • 트리의 높이를 최소화하도록 유지하여 삽입, 삭제, 검색 등의 연산이 O(log n) 시간 복잡도를 갖도록 한다.
   • 예: AVL 트리, 레드-블랙 트리.

 

Java로 이진 탐색 트리를 구현하는 방법

이제 Java로 간단한 이진 탐색 트리(Binary Search Tree, BST)를 구현하는 방법을 설명하겠다.

 

// 노드 클래스 정의
class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

// 이진 탐색 트리 클래스 정의
class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

    // 노드 삽입
    void insert(int value) {
        root = insertRec(root, value);
    }

    Node insertRec(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }

        if (value < root.value)
            root.left = insertRec(root.left, value);
        else if (value > root.value)
            root.right = insertRec(root.right, value);

        return root;
    }

    // 노드 검색
    boolean search(int value) {
        return searchRec(root, value);
    }

    boolean searchRec(Node root, int value) {
        if (root == null)
            return false;

        if (root.value == value)
            return true;

        return value < root.value
            ? searchRec(root.left, value)
            : searchRec(root.right, value);
    }

    // 중위 순회 (Inorder Traversal)
    void inorder() {
        inorderRec(root);
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.value + " ");
            inorderRec(root.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        /* 노드 삽입 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // 중위 순회
        tree.inorder();

        // 검색
        System.out.println("\nSearch 40: " + tree.search(40)); // true
        System.out.println("Search 90: " + tree.search(90)); // false
    }
}

 

 

B 트리는 이진 트리 (Binary Tree) 와 다른건가?

 

이진 트리 (Binary Tree)

• 구조: 각 노드는 최대 두 개의 자식 노드를 가진다. 이 자식 노드들은 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분된다.
• 용도: 트리 기반 검색, 힙, 트라이, 우선순위 큐 등 여러 알고리즘 및 자료 구조의 기초로 사용된다.

 

B 트리 (B-Tree)

        [10 | 20]
       /    |    \
  [5]  [15]  [25 | 30 | 35]

B 트리의 차수가 3인 경우 (각 노드는 최대 2개의 키와 3개의 자식을 가질 수 있다).

 

• 구조: 다진 트리(multiway tree)로, 하나의 노드가 여러 개의 자식 노드를 가질 수 있다. B 트리의 각 노드는 최대 M개의 자식 노드를 가질 수 있으며, 여기서 M은 B 트리의 차수이다.
• 특징:
  • 균형 유지: B 트리는 항상 균형을 유지하여 모든 리프 노드가 같은 깊이를 가진다.
  • 내부 노드의 자식 수: 내부 노드는 최소 ⌈M/2⌉개의 자식 노드를 가져야 한다.
  • 키의 개수: 각 노드는 최대 M-1개의 키를 가질 수 있다.
  • 자식 노드 분할: 노드가 꽉 차게 되면, 노드는 분할되어 상위 노드로 승격된다.
• 용도: 주로 데이터베이스와 파일 시스템에서 대량의 데이터를 효율적으로 관리하고 빠르게 접근하기 위해 사용된다.

 

B+ 트리 (B+ Tree)

        [10 | 20]
       /    |    \
    [5, 10] [15, 20] [25, 30, 35]
     |       |        |
    (5)     (10, 15)  (20, 25, 30, 35)

B+ 트리의 차수가 3인 경우 (각 노드는 최대 2개의 키와 3개의 자식을 가질 수 있다).

 

• 구조: B 트리의 확장형으로, B+ 트리의 내부 노드는 인덱스 역할을 하고, 모든 실제 데이터는 리프 노드에 저장된다.
• 특징:
  • 리프 노드: 모든 리프 노드는 링크드 리스트 형태로 연결되어 있어, 범위 검색(range query)과 순차 접근(sequential access)이 용이하다.
  • 내부 노드: 내부 노드는 인덱스 역할만 하며, 실제 데이터는 저장되지 않는다.
  • 균형 유지: B 트리와 마찬가지로 B+ 트리도 균형을 유지하여 모든 리프 노드가 같은 깊이를 가진다.
  • 데이터 중복: B+ 트리의 경우, 리프 노드에만 데이터를 저장하기 때문에 내부 노드에서 데이터가 중복되지 않는다.
• 용도: 데이터베이스와 파일 시스템에서 매우 자주 사용되며, 특히 순차적인 데이터 접근이 필요하거나 범위 검색이 빈번한 경우에 유리하다.

 

B 트리와 B+ 트리의 비교

1. 데이터 저장 위치:
   • B 트리: 모든 노드(내부 노드와 리프 노드)에 데이터를 저장한다.
   • B+ 트리: 모든 데이터는 리프 노드에만 저장된다. 내부 노드는 인덱스로만 사용된다.
2. 리프 노드 간 연결:
   • B 트리: 리프 노드 간에 특별한 연결이 없다.
   • B+ 트리: 모든 리프 노드는 링크드 리스트로 연결되어 있어, 순차 접근이 매우 효율적이다.
3. 검색 효율성:
   • B 트리: 검색 시 리프 노드뿐만 아니라 내부 노드에서도 데이터를 찾을 수 있다.
   • B+ 트리: 검색 시 모든 실제 데이터는 리프 노드에 있기 때문에 리프 노드에 도달해야 한다. 그러나 범위 검색과 순차 접근이 더 효율적이다.
4. 공간 효율성:
   • B 트리: 내부 노드에도 데이터를 저장하기 때문에 B+ 트리에 비해 공간 효율성이 떨어질 수 있다.
   • B+ 트리: 모든 데이터가 리프 노드에만 있기 때문에 공간 효율성이 더 높다.

 

불균형 트리의 문제점

이진 탐색 트리(Binary Search Tree, BST)는 삽입되는 데이터의 순서에 따라 불균형해질 수 있다. 예를 들어, 삽입되는 데이터가 오름차순이거나 내림차순인 경우 트리가 일직선으로 늘어나게 된다. 이 경우, 트리는 리스트와 같은 구조가 되어 평균적으로 O(log n) 시간 복잡도를 가지는 연산이 O(n)으로 증가한다.

 

균형 이진 트리의 해결책

균형 이진 트리는 트리의 높이를 가능한 낮게 유지하여 이러한 문제를 해결한다. 이를 위해, 특정 조건을 만족시키도록 트리를 재구성하는 알고리즘을 사용한다. 대표적인 균형 이진 트리로는 AVL 트리와 레드-블랙 트리가 있다.

 

AVL 트리

AVL 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1이 되도록 유지하는 트리이다. AVL 트리는 삽입과 삭제 연산 후에 트리를 재구성하여 균형을 유지한다. 다음은 AVL 트리의 균형을 유지하는 과정이다:

1. 삽입: 노드를 삽입한 후, 삽입된 노드로부터 루트 노드까지 거슬러 올라가며 각 노드의 균형 인수를 계산한다. 균형 인수가 -1, 0, 1인 경우는 균형이 잡혀 있지만, 그 외의 경우는 불균형 상태이다.
2. 재구성: 불균형 상태인 노드에서 회전 연산을 수행하여 트리를 균형 상태로 만든다. 회전 연산에는 다음과 같은 네 가지가 있다:
   • 단순 회전: 왼쪽 회전(Left Rotation), 오른쪽 회전(Right Rotation)
   • 복합 회전: 좌우 회전(Left-Right Rotation), 우좌 회전(Right-Left Rotation)

레드-블랙 트리

레드-블랙 트리는 노드가 '레드' 또는 '블랙' 색상을 가지며, 다음과 같은 속성을 만족하여 트리를 균형 상태로 유지한다:

1. 노드는 레드 또는 블랙 색상을 가진다.
2. 루트 노드는 항상 블랙이다.
3. 모든 리프 노드(NIL 노드)는 블랙이다.
4. 레드 노드의 자식 노드는 항상 블랙이다(즉, 레드 노드는 연속적으로 나타나지 않는다).
5. 루트 노드에서 모든 리프 노드까지의 경로에는 동일한 개수의 블랙 노드가 존재한다.

레드-블랙 트리는 삽입과 삭제 시 트리의 속성을 유지하기 위해 재구성(회전 및 색상 변경)을 수행한다.

 

예제: AVL 트리 삽입과 회전

아래는 AVL 트리에 노드를 삽입하고 필요한 경우 회전을 통해 균형을 유지하는 Java 코드 예제이다.

class Node {
    int value, height;
    Node left, right;

    Node(int d) {
        value = d;
        height = 1;
    }
}

class AVLTree {
    Node root;

    int height(Node N) {
        if (N == null)
            return 0;
        return N.height;
    }

    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        return x;
    }

    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        return y;
    }

    int getBalance(Node N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    Node insert(Node node, int value) {
        if (node == null)
            return (new Node(value));

        if (value < node.value)
            node.left = insert(node.left, value);
        else if (value > node.value)
            node.right = insert(node.right, value);
        else
            return node;

        node.height = 1 + max(height(node.left), height(node.right));

        int balance = getBalance(node);

        if (balance > 1 && value < node.left.value)
            return rightRotate(node);

        if (balance < -1 && value > node.right.value)
            return leftRotate(node);

        if (balance > 1 && value > node.left.value) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && value < node.right.value) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    void inorder(Node node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.value + " ");
            inorder(node.right);
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);

        tree.inorder(tree.root); // 출력: 10 20 25 30 40 50
    }
}

 

 

이 코드에서 AVL 트리에 노드를 삽입하고 불균형이 발생하면 회전 연산을 통해 균형을 유지한다. 이러한 균형 유지 덕분에 AVL 트리는 항상 O(log n) 시간 복잡도로 연산을 수행할 수 있다.

 

 

이진 트리와 관련된 코딩 테스트 문제 유형

1. 이진 트리의 기본 연산:
   • 노드 삽입
   • 노드 삭제
   • 노드 검색
2. 트리 순회:
   • 전위 순회 (Preorder Traversal)
   • 중위 순회 (Inorder Traversal)
   • 후위 순회 (Postorder Traversal)
   • 레벨 순서 순회 (Level Order Traversal, BFS)
3. 트리의 속성 계산:
   • 트리의 높이(Depth) 계산
   • 트리의 크기(Size) 계산
   • 리프 노드 개수 계산
4. 특정 유형의 트리:
   • 이진 탐색 트리(BST) 검사 및 변환
   • 균형 트리(AVL 트리, Red-Black 트리) 문제
5. 경로 문제:
   • 루트에서 리프까지의 경로 출력
   • 특정 합을 가지는 경로 찾기

 

이진 트리의 활용 예

1. 이진 탐색 트리(BST):
   • 데이터의 삽입, 삭제, 검색 연산을 효율적으로 수행하기 위해 사용된다.
   • 예: 데이터베이스 인덱스, 사전(dictionary) 구현 등.
2. 힙(Heap):
   • 완전 이진 트리 형태로, 우선순위 큐(priority queue)를 구현하는 데 사용된다.
   • 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분된다.
   • 예: 작업 스케줄링, 다익스트라 알고리즘 등.
3. 이진 표현식 트리(Binary Expression Tree):
   • 수학적 표현식을 트리 구조로 나타낸 것.
   • 각 노드는 연산자 또는 피연산자를 나타내며, 표현식의 계산 순서를 나타낸다.
   • 예: 계산기 프로그램, 컴파일러의 수식 처리 등.
4. 허프만 트리(Huffman Tree):
   • 데이터 압축 알고리즘에서 사용되며, 자주 사용되는 문자에 짧은 코드값을 할당한다.
   • 허프만 코딩은 가변 길이 코드로 효율적인 데이터 압축을 제공한다.
   • 예: 파일 압축, 이미지 및 오디오 압축 등.

 

해결 전략

1. 재귀 함수 사용:
   • 트리 구조는 재귀적으로 정의되기 때문에, 재귀 함수가 트리 문제를 해결하는 데 유용하다. 예를 들어, 트리의 높이를 계산할 때는 루트 노드에서 출발하여 각 자식 노드의 높이를 재귀적으로 계산하고, 그 중 최대 값을 선택하는 방식으로 해결할 수 있다.
2. 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS):
   • DFS는 재귀적 또는 스택을 이용해 구현할 수 있으며, 트리의 깊이를 탐색하거나 특정 경로를 찾는 문제에서 유용하다.
   • BFS는 큐를 사용하여 구현하며, 레벨 순서 순회와 같은 문제에서 유용하다.