본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.

• 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
  • IDE : IntelliJ IDEA (Ultimate Edition)
  • Java : JDK 21 (corretto-21)
  • Python : 3.9 (conda env)

트리(Tree) - Binary Tree

• 일반적인 Tree에 대한 전반적인 내용들은 다음 포스팅에서 확인하실 수 있습니다.
  • [자료구조] Tree - 개요 (기본 개념과 구현)

1. Binary Tree란?

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 자료구조입니다.

• 이 두 자식은 왼쪽 자식 노드(left child)와 오른쪽 자식 노드(right child)로 구분됩니다.
• 이진 트리는 자료를 효율적으로 정렬하고 탐색하는 데 매우 유용하며, 다양한 알고리즘에서 널리 사용됩니다.

1.1 Binary Tree의 주요 특징

• 자식 노드의 수 제한: 이진 트리의 가장 큰 특징은 각 노드가 최대 두 개의 자식 노드를 가질 수 있다는 점입니다.
  • 즉, 왼쪽 자식과 오른쪽 자식으로만 연결됩니다.
  • 둘 중 하나가 없거나 둘 다 없어도 무방하며, 3개를 넘지만 않으면 됩니다.

• 재귀적 구조: 트리는 본질적으로 재귀적 구조를 가지며, 하위 트리(subtree)들도 하나의 이진 트리로 취급됩니다.

• 균형성: 이진 트리에서는 노드가 어느 한쪽에 치우치지 않고 균형적으로 분포되는 것이 이상적입니다.

  • 균형 잡힌 트리(Balanced Binary Tree)는 탐색, 삽입, 삭제와 같은 연산에서 O(log n)의 시간 복잡도를 가집니다.
  • 반면, 비균형 트리는 특정한 경로가 지나치게 길어지면, 선형 탐색과 유사한 O(n) 시간 복잡도를 가질 수 있습니다.

(참고) 자체 균형 트리(Self-Balancing Tree)

• 비균형 이진 탐색 트리에서 발생하는 탐색 성능 문제를 해결하기 위해, 트리가 스스로 균형을 유지하는 자체 균형 트리(Self-Balancing Tree)라는 것이 있습니다.
  • 대표적인 예로 AVL 트리와 Red-Black 트리가 있습니다.
  • 이 트리들은 삽입과 삭제가 일어날 때 자동으로 트리의 균형을 조정하여 최악의 경우에도 O(log n) 시간 복잡도를 보장합니다.
• AVL 트리는 각 노드의 자식 트리의 높이 차이가 1 이하가 되도록 유지하며, Red-Black 트리는 노드에 색상을 부여하여 균형을 유지합니다.
• 이 트리들은 다뤄야할 내용이 많아서 이후 포스팅에서 따로 자세히 다룰 예정입니다.

1.2 Binary Tree의 용도

이진 트리는 그 특성상 여러 분야에서 탐색, 정렬, 데이터 관리 등의 목적으로 널리 사용됩니다.

• 이진 탐색 트리(Binary Search Tree, BST): 이진 탐색 트리는 각 노드가 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가지도록 구성된 트리입니다.
  • 이를 통해 빠른 검색과 정렬을 가능하게 합니다.
  • 다만, BST는 삽입과 삭제 과정에서 트리가 한쪽으로 치우쳐 비균형 상태가 될 수 있습니다.
    • 이 경우, 탐색 성능이 O(n)으로 저하될 수 있으며, 이를 해결하기 위해 AVL 트리나 Red-Black 트리와 같은 자체 균형 트리가 사용됩니다.

• 힙(Heap): 힙은 최대값 또는 최소값을 빠르게 찾기 위해 사용하는 완전 이진 트리입니다. 주로 우선순위 큐 및 최단 경로 탐색에 활용됩니다.
  • 최대 힙(Max Heap)에서는 부모 노드의 값이 자식 노드보다 크거나 같습니다, 반면에 최소 힙(Min Heap)에서는 부모 노드의 값이 자식 노드보다 작거나 같습니다.
  • 힙은 주로 우선순위 큐, 최단 경로 탐색 등의 알고리즘에서 사용되고, 바로 다음 포스팅에서 자세히 다룹니다.

• 트리 기반 검색 알고리즘: 이진 트리는 이진 탐색, 트리 순회 알고리즘(Pre-order, In-order, Post-order) 등에서도 매우 유용하게 쓰입니다.

2. Binary Tree 종류

이진 트리(Binary Tree)는 그 구조와 성질에 따라 여러 가지로 분류할 수 있습니다.

• Perfect Binary Tree (포화 이진트리 혹은 완전 포화 이진트리)
• Complete Binary Tree (완전 이진트리)
• Full Binary Tree (정 이진트리 혹은 포화 이진트리)
• Skewed Binary Tree (편향트리 혹은 사향트리)
• Balanced Binary Tree (균형 이진트리)

2.1 포화 이진트리(Perfect Binary Tree, 완전 포화 이진트리)

일각에서는 Perfect Binary Tree를 완전 포화 이진트리라고 부르기도 합니다만, 여기선 포화 이진트리라는 용어를 사용하겠습니다.

• 모든 레벨이 꽉 찬 트리입니다.
  • 즉, 모든 내부 노드가 두 개의 자식 노드를 가지며, 모든 리프 노드가 같은 레벨에 있습니다.
• 트리의 높이가 h일 때, 노드의 총 개수는 2^h - 1입니다.
• 매우 균형 잡힌 완벽한 형태로, 데이터의 탐색, 삽입, 삭제 연산이 O(log n)의 성능을 유지합니다.

2.2 완전 이진트리(Complete Binary Tree)

• 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리입니다.
• 마지막 레벨은 왼쪽에서부터 채워지는 구조를 가지고 있습니다.
• 힙(Heap) 자료구조가 완전 이진 트리의 형태로 구현됩니다.

2.3 정 이진트리(Full Binary Tree, 포화 이진트리)

일각에서는 Full Binary Tree를 포화 이진트리라고 부르기도 합니다만, 여기서는 Perfect Binary Tree를 포화 이진트리라는 용어로 사용했기 때문에 Full Binary Tree를 정 이진트리로 사용하도록 하겠습니다.

• 두 용어 모두 어느정도는 비슷한 개념을 가지고 있기 때문에, 혼용해서 쓰일 수도 있다고 생각하시면 될듯 합니다.

• 각 노드가 0개 또는 2개의 자식만 가지는 트리입니다.
  • 즉, 자식이 없는 노드들은 모두 리프 노드이고, 나머지 노드들은 반드시 2개의 자식 노드를 가집니다.
• 균형이 잡혀 있지 않아도 되며, 노드가 2개씩 있다는 점에서 트리의 밀도가 높습니다.

2.4 편향트리(Skewed Binary Tree, 사향트리)

• 한쪽 방향으로만 자식 노드가 있는 트리입니다.
  • 왼쪽 편향 트리: 모든 노드가 왼쪽 자식만 가지는 구조.
  • 오른쪽 편향 트리: 모든 노드가 오른쪽 자식만 가지는 구조.
• 편향 트리는 실질적으로 연결 리스트와 유사하며, 트리의 탐색 성능이 최악의 경우 O(n)으로 떨어집니다.

2.5 균형 이진트리(Balanced Binary Tree)

• 균형 이진 트리는 트리의 모든 서브트리들이 균형을 이루며, 높이 차이가 일정한 한계를 넘지 않도록 유지됩니다.
• 대표적으로 AVL 트리와 Red-Black 트리가 있습니다.
  • AVL 트리는 각 노드의 자식 트리의 높이 차이가 1 이하로 유지되도록 관리합니다.
  • Red-Black 트리는 노드의 색상 규칙을 통해 트리의 균형을 유지합니다.
• 이 트리들은 삽입과 삭제 후에도 자동으로 균형을 조정하여 O(log n) 성능을 보장합니다.

균형 이진트리 시각화에 유용한 사이트

• AVL Tree, Red-Black Tree 등의 동작 원리를 파악하기에 좋은 사이트입니다. (물론 이외에도 다양한 알고리즘들과 자료구조를 시각화하며 직접 확인해 보실 수 있습니다.
  https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

AVL 트리와 Red-Black 트리는 다뤄야할 내용이 좀 많아서 추후 포스팅에서 따로 다루겠습니다.

3. 이진 트리 순회(Traversal) 알고리즘

이진 트리에서는 트리의 모든 노드를 방문하는 다양한 방식의 순회(traversal) 알고리즘이 존재합니다.

• 이 순회 알고리즘은 트리의 구조에 따라 데이터를 탐색하고 처리하는 중요한 역할을 합니다.
• 이진 트리에서 주로 사용하는 4가지 순회 방식에 대해 살펴보겠습니다.
  • 전위 순회 (Pre-order Traversal)
  • 중위 순회 (In-order Traversal)
  • 후위 순회 (Post-order Traversal)
  • 레벨 순서 순회 (Level-order Traversal)

3.1 전위 순회 (Pre-order Traversal)

전위 순회는 루트 노드를 먼저 방문한 후, 왼쪽 자식 노드와 오른쪽 자식 노드를 차례로 방문하는 방식입니다.

• 즉, "부모(P) -> 왼쪽 자식(L) -> 오른쪽 자식(R)"의 순서로 탐색합니다.

1. 현재 노드를 방문 (루트 노드)
2. 왼쪽 서브트리 순회
3. 오른쪽 서브트리 순회

3.2 중위 순회 (In-order Traversal)

중위 순회는 왼쪽 자식 노드를 먼저 방문한 후, 부모 노드를 방문하고 오른쪽 자식 노드를 방문하는 방식입니다.

• 즉, "왼쪽 자식(L) -> 부모(P) -> 오른쪽 자식(R)"의 순서로 탐색합니다.

1. 왼쪽 서브트리 순회
2. 현재 노드 방문 (부모 노드)
3. 오른쪽 서브트리 순회

3.3 후위 순회 (Post-order Traversal)

후위 순회는 왼쪽 자식 노드와 오른쪽 자식 노드를 먼저 방문한 후, 부모 노드를 마지막으로 방문하는 방식입니다.

• 즉, "왼쪽 자식(L) -> 오른쪽 자식(R) -> 부모(P)"의 순서로 탐색합니다.

1. 왼쪽 서브트리 순회
2. 오른쪽 서브트리 순회
3. 현재 노드 방문 (부모 노드)

3.4 레벨 순서 순회 (Level-order Traversal)

레벨 순서 순회는 노드의 깊이(레벨)에 따라 순서대로 방문하는 방식입니다.

• 주로 큐(Queue) 자료구조를 이용하여 구현하며, BFS(Breadth-First Search) 탐색 방법을 따릅니다.

트리 순회 요약

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

순회 방식	탐색 순서	예시 결과
전위 순회 (Pre-order)	부모 -> 왼쪽 -> 오른쪽	A B D E C F G
중위 순회 (In-order)	왼쪽 -> 부모 -> 오른쪽	D B E A F C G
후위 순회 (Post-order)	왼쪽 -> 오른쪽 -> 부모	D E B F G C A
레벨 순서 순회 (Level-order)	레벨 별 순차 방문	A B C D E F G

4. Node로 구현하는 Binary Tree (Java, Python)

이번 섹션부터는 이진 트리(Binary Tree)를 Java와 Python에서 어떻게 구현할 수 있는지 살펴보겠습니다.

• 이진 트리를 구현하기 위해 노드 클래스(Node Class)와 트리 클래스(Tree Class)를 정의하고, 각각의 순회 알고리즘도 함께 구현해 보겠습니다.

4.1 Java에서 Binary Tree 구현

Java에서는 각 노드를 클래스로 정의하고, 이를 연결하여 트리 구조를 구현할 수 있습니다.

4.1.1 노드 클래스(Node Class)

이진 트리의 각 노드는 데이터와 왼쪽 자식, 오른쪽 자식에 대한 참조를 가집니다. 이를 기반으로 Node 클래스를 정의할 수 있습니다.

class Node {
    String data;
    Node left;
    Node right;

    public Node(String data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

위 코드에서 Node 클래스는 데이터를 저장하고, 왼쪽과 오른쪽 자식을 가리키는 필드를 가집니다.

4.1.2 트리 클래스(Tree Class)

트리 클래스에서는 트리의 루트 노드를 관리하고, 여러 순회 알고리즘을 구현할 수 있습니다.

class BinaryTree {
    Node root;

    public BinaryTree(String rootData) {
        root = new Node(rootData);
    }

    // 전위 순회 (Pre-order Traversal)
    public void preOrderTraversal(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }

    // 중위 순회 (In-order Traversal)
    public void inOrderTraversal(Node node) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.left);
        System.out.print(node.data + " ");
        inOrderTraversal(node.right);
    }

    // 후위 순회 (Post-order Traversal)
    public void postOrderTraversal(Node node) {
        if (node == null) {
            return;
        }
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        System.out.print(node.data + " ");
    }

    // 레벨 순서 순회 (Level-order Traversal)
    public void levelOrderTraversal(Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            System.out.print(current.data + " ");
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }
}

BinaryTree 클래스는 루트 노드를 관리하며, 순회 알고리즘을 포함합니다.

4.1.3 트리 생성 및 순회 알고리즘 실행

다음은 트리를 생성하고, 각각의 순회 알고리즘을 실행하는 코드입니다.

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree("A");
        tree.root.left = new Node("B");
        tree.root.right = new Node("C");
        tree.root.left.left = new Node("D");
        tree.root.left.right = new Node("E");
        tree.root.right.left = new Node("F");
        tree.root.right.right = new Node("G");

        // 전위 순회
        System.out.print("Pre-order Traversal: ");
        tree.preOrderTraversal(tree.root);  // 출력: A B D E C F G

        // 중위 순회
        System.out.print("\nIn-order Traversal: ");
        tree.inOrderTraversal(tree.root);   // 출력: D B E A F C G

        // 후위 순회
        System.out.print("\nPost-order Traversal: ");
        tree.postOrderTraversal(tree.root); // 출력: D E B F G C A

        // 레벨 순서 순회
        System.out.print("\nLevel-order Traversal: ");
        tree.levelOrderTraversal(tree.root); // 출력: A B C D E F G
    }
}

4.2 Python에서 Binary Tree 구현

Python에서도 클래스 기반으로 이진 트리를 쉽게 구현할 수 있습니다.

• Node 클래스와 Tree 클래스를 정의하고, 각각의 순회 알고리즘을 구현합니다.

4.2.1 노드 클래스(Node Class)

Python에서의 노드 클래스 정의는 매우 간단합니다. 각 노드는 데이터와 왼쪽, 오른쪽 자식 노드에 대한 참조를 가집니다.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

4.2.2 트리 클래스(Tree Class)

Tree 클래스에서는 트리의 루트 노드를 관리하고, 순회 알고리즘을 정의합니다.

class BinaryTree:
    def __init__(self, root_data):
        self.root = Node(root_data)

    # 전위 순회 (Pre-order Traversal)
    def pre_order(self, node):
        if node:
            print(node.data, end=' ')
            self.pre_order(node.left)
            self.pre_order(node.right)

    # 중위 순회 (In-order Traversal)
    def in_order(self, node):
        if node:
            self.in_order(node.left)
            print(node.data, end=' ')
            self.in_order(node.right)

    # 후위 순회 (Post-order Traversal)
    def post_order(self, node):
        if node:
            self.post_order(node.left)
            self.post_order(node.right)
            print(node.data, end=' ')

    # 레벨 순서 순회 (Level-order Traversal)
    def level_order(self, node):
        if not node:
            return
        queue = [node]
        while queue:
            current = queue.pop(0)
            print(current.data, end=' ')
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)

4.2.3 트리 생성 및 순회 알고리즘 실행

다음은 Python에서 트리를 생성하고 각각의 순회 알고리즘을 실행하는 코드입니다.

# 트리 생성
tree = BinaryTree("A")
tree.root.left = Node("B")
tree.root.right = Node("C")
tree.root.left.left = Node("D")
tree.root.left.right = Node("E")
tree.root.right.left = Node("F")
tree.root.right.right = Node("G")

# 전위 순회
print("Pre-order Traversal: ", end='')
tree.pre_order(tree.root)  # 출력: A B D E C F G

# 중위 순회
print("\nIn-order Traversal: ", end='')
tree.in_order(tree.root)   # 출력: D B E A F C G

# 후위 순회
print("\nPost-order Traversal: ", end='')
tree.post_order(tree.root) # 출력: D E B F G C A

# 레벨 순서 순회
print("\nLevel-order Traversal: ", end='')
tree.level_order(tree.root) # 출력: A B C D E F G

5. 배열로 구현하는 완전(Complete) 이진트리

완전 이진 트리(Complete Binary Tree)는 배열을 사용하여 구현할 수 있습니다.

• 이 방식에서는 트리의 각 노드를 배열의 인덱스로 나타냅니다.
• 자식 노드와 부모 노드의 관계는 인덱스 계산을 통해 연결됩니다.

배열의 완전이진트리 인덱스 계산법

부모 노드의 인덱스가 i일 때:

• 왼쪽 자식의 인덱스는 2 * i + 1
• 오른쪽 자식의 인덱스는 2 * i + 2

5.1 배열을 사용한 Binary Tree 구현 (Java)

배열을 이용한 이진 트리 구현은 노드의 자리를 배열의 인덱스로 표현합니다.

class BinaryTreeArray {
    int[] tree;
    int size;

    public BinaryTreeArray(int size) {
        tree = new int[size];
        this.size = size;
    }

    // 배열 트리에서 전위 순회
    void preOrderTraversal(int index) {
        if (index >= size || tree[index] == -1) return;

        System.out.print(tree[index] + " ");
        preOrderTraversal(2 * index + 1);  // 왼쪽 자식
        preOrderTraversal(2 * index + 2);  // 오른쪽 자식
    }

    public static void main(String[] args) {
        BinaryTreeArray tree = new BinaryTreeArray(7);
        tree.tree[0] = 1;
        tree.tree[1] = 2;
        tree.tree[2] = 3;
        tree.tree[3] = 4;
        tree.tree[4] = 5;
        tree.tree[5] = -1;  // 빈 노드
        tree.tree[6] = -1;  // 빈 노드

        System.out.println("Pre-order Traversal:");
        tree.preOrderTraversal(0);  // 출력: 1 2 4 5 3
    }
}

• 위 코드에서 -1은 노드가 비어 있음을 나타냅니다.
• 위 예시에선 전위 순회를 통해 배열로 표현된 트리를 탐색하였습니다.

5.2 배열을 사용한 Binary Tree 구현 (Python)

Python에서도 배열로 이진 트리를 구현할 수 있으며, Java와 동일한 방식으로 인덱스를 계산합니다.

class BinaryTreeArray:
    def __init__(self, size):
        self.tree = [-1] * size
        self.size = size

    # 배열 트리에서 전위 순회
    def pre_order_traversal(self, index):
        if index >= self.size or self.tree[index] == -1:
            return

        print(self.tree[index], end=' ')
        self.pre_order_traversal(2 * index + 1)  # 왼쪽 자식
        self.pre_order_traversal(2 * index + 2)  # 오른쪽 자식

# 트리 생성 및 전위 순회 실행
tree = BinaryTreeArray(7)
tree.tree[0] = 1
tree.tree[1] = 2
tree.tree[2] = 3
tree.tree[3] = 4
tree.tree[4] = 5

print("Pre-order Traversal:")
tree.pre_order_traversal(0)  # 출력: 1 2 4 5 3

배열 기반 이진 트리는 메모리 효율성이 높은 반면, 배열 크기를 미리 할당해야 하는 단점이 있습니다.

6. Node 기반 트리와 배열 기반 트리의 비교

이진 트리를 구현하는 방식에는 Node 기반 구현과 배열 기반 구현이 있으며, 두 방식 모두 각기 다른 장단점을 가지고 있습니다.

6.1 Node 기반 트리의 장단점

Node 기반 트리는 동적으로 노드를 추가하거나 트리의 크기를 유연하게 조정할 수 있다는 장점이 있습니다.

장점:

• 동적 크기: 트리의 크기를 미리 지정하지 않아도 됩니다.
• 가변 구조: 노드를 삽입하거나 삭제하는데 유연합니다.
• 메모리 효율적: 필요한 만큼만 메모리를 사용합니다.

단점:

• 노드 간 연결을 위한 추가 메모리(포인터)가 필요합니다.
• 노드 탐색 시 포인터 참조가 필요해 추가 연산 비용이 발생할 수 있습니다.

6.2 배열 기반 트리의 장단점

배열 기반 트리는 배열 인덱스를 이용하여 부모-자식 관계를 효율적으로 관리할 수 있으며, 특히 완전 이진 트리의 경우에 효과적입니다.

장점:

• 메모리 접근이 빠르고, 배열 인덱스 계산을 통해 부모와 자식 노드 간의 관계를 효율적으로 표현할 수 있습니다.
• 구조가 단순하고, 포인터가 없어 메모리 오버헤드가 적습니다.

단점:

• 배열의 크기를 미리 지정해야 하며, 크기 변경이 어렵습니다.
• 비균형 트리의 경우 배열 공간이 비효율적으로 사용될 수 있습니다.
• 트리 크기가 커질수록 배열 크기 조정이 어려워집니다.

6.3 비교 요약

구현 방식	장점	단점
Node 기반	동적으로 크기를 확장 가능 메모리 효율적 사용	포인터 참조 필요 탐색 시 추가 연산 비용 발생
배열 기반	빠른 메모리 접근 간단한 구조	크기 변경이 어려움 비균형 트리에서 공간 낭비

마무리

이 포스팅에서는 이진 트리(Binary Tree)의 개념부터 Node 기반과 배열 기반 트리 구현 방식을 다루고, 트리 순회 알고리즘에 대해 살펴보았습니다.

• 두 가지 구현 방식의 장단점을 비교하며, 상황에 따라 어떤 방식이 적합한지 이해하는 것이 중요합니다.

또한 균형 이진 트리(AVL, Red-Black Tree)와 같은 고급 트리 구조는 이후 다룰 예정이니, 이진 탐색 트리의 성능 이슈나 트리의 균형 유지를 위한 알고리즘이 궁금하신 분들은 이후에 작성될 포스팅을 기대해 주세요.

추가로 트리와 같은 다양한 자료구조를 더 깊이 이해하고 시각적으로 확인해 보고 싶다면, 다음 사이트에서 다양한 자료구조 및 알고리즘을 시각화하며 학습해 보시는 걸 추천드립니다.

Visualizing Data Structures and Algorithms: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

이 사이트를 활용하면 AVL 트리, Red-Black 트리 등 다양한 트리 구조와 알고리즘을 직접 실습하며 이해할 수 있습니다.

다음 포스팅에서는 힙(Heap)과 우선순위 큐(Priority Queue)에 대해 다양한 알고리즘과 응용 사례를 함께 살펴보겠습니다.