트리(Tree)

트리(Tree)

1. 개념

트리는 노드(node)들이 계층적으로 연결된 비선형 자료구조입니다. 각 노드는 여러 개의 자식 노드를 가질 수 있으며, 최상위 노드를 루트(root)라고 합니다. 트리는 계층적 관계를 표현하고 빠른 검색, 삽입, 삭제 연산을 지원합니다.

2. 트리의 기본 구성 요소

• 노드(Node): 트리의 기본 요소로, 데이터와 자식 노드에 대한 참조를 포함합니다.
• 루트(Root): 트리의 최상위 노드입니다.
• 부모(Parent): 직접적으로 연결된 상위 노드입니다.
• 자식(Child): 직접적으로 연결된 하위 노드입니다.
• 형제(Sibling): 같은 부모를 가진 노드들입니다.
• 리프(Leaf): 자식이 없는 노드입니다.
• 내부 노드(Internal Node): 자식이 있는 노드입니다.
• 경로(Path): 한 노드에서 다른 노드로 가는 노드들의 순서입니다.
• 깊이(Depth): 루트에서 특정 노드까지의 경로 길이입니다.
• 높이(Height): 노드에서 가장 먼 리프까지의 경로 길이입니다. 트리의 높이는 루트의 높이입니다.
• 서브트리(Subtree): 노드와 그 자손들로 구성된 트리입니다.

3. 트리의 종류

3.1. 이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식을 가지는 트리입니다.

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

3.1.1. 완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드는 왼쪽부터 채워져 있는 이진 트리입니다.

3.1.2. 포화 이진 트리(Full Binary Tree)

모든 내부 노드가 두 개의 자식을 가지고, 모든 리프 노드가 같은 레벨에 있는 이진 트리입니다.

3.1.3. 균형 이진 트리(Balanced Binary Tree)

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 이진 트리입니다.

3.2. 이진 검색 트리(Binary Search Tree)

모든 노드에 대해 왼쪽 서브트리의 모든 노드 값은 해당 노드 값보다 작고, 오른쪽 서브트리의 모든 노드 값은 해당 노드 값보다 큰 이진 트리입니다.

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

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        if self.root is None:
            self.root = BSTNode(data)
        else:
            self._insert_recursive(self.root, data)
    
    def _insert_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = BSTNode(data)
            else:
                self._insert_recursive(node.left, data)
        else:
            if node.right is None:
                node.right = BSTNode(data)
            else:
                self._insert_recursive(node.right, data)
    
    def search(self, data):
        return self._search_recursive(self.root, data)
    
    def _search_recursive(self, node, data):
        if node is None or node.data == data:
            return node
        
        if data < node.data:
            return self._search_recursive(node.left, data)
        return self._search_recursive(node.right, data)

3.3. AVL 트리

자가 균형 이진 검색 트리로, 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1입니다. 불균형이 발생하면 회전을 통해 균형을 유지합니다.

class AVLNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # 새 노드의 높이는 1

class AVLTree:
    def get_height(self, node):
        if node is None:
            return 0
        return node.height

    def get_balance(self, node):
        if node is None:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def right_rotate(self, y):
        x = y.left
        T2 = x.right

        # 회전 수행
        x.right = y
        y.left = T2

        # 높이 업데이트
        y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
        x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1

        return x

    def left_rotate(self, x):
        y = x.right
        T2 = y.left

        # 회전 수행
        y.left = x
        x.right = T2

        # 높이 업데이트
        x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1
        y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1

        return y

    def insert(self, root, data):
        # 1. 일반적인 BST 삽입 수행
        if root is None:
            return AVLNode(data)

        if data < root.data:
            root.left = self.insert(root.left, data)
        else:
            root.right = self.insert(root.right, data)

        # 2. 높이 업데이트
        root.height = max(self.get_height(root.left), self.get_height(root.right)) + 1

        # 3. 불균형 확인 및 회전
        balance = self.get_balance(root)

        # LL 케이스
        if balance > 1 and data < root.left.data:
            return self.right_rotate(root)

        # RR 케이스
        if balance < -1 and data > root.right.data:
            return self.left_rotate(root)

        # LR 케이스
        if balance > 1 and data > root.left.data:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # RL 케이스
        if balance < -1 and data < root.right.data:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

3.4. 레드-블랙 트리(Red-Black Tree)

자가 균형 이진 검색 트리로, 각 노드는 레드 또는 블랙 색상을 가지며 다음 규칙을 만족합니다:

1. 모든 노드는 레드 또는 블랙입니다.
2. 루트는 블랙입니다.
3. 모든 리프(NIL)는 블랙입니다.
4. 레드 노드의 자식은 모두 블랙입니다.
5. 임의의 노드에서 모든 리프까지의 경로에 있는 블랙 노드의 수는 동일합니다.

3.5. B-트리(B-Tree)

자식 노드의 수가 2개를 초과할 수 있는 균형 검색 트리로, 주로 데이터베이스와 파일 시스템에서 사용됩니다.

3.6. 트라이(Trie)

문자열을 저장하고 검색하는 데 특화된 트리로, 각 노드가 문자를 나타냅니다. 주로 사전, 자동 완성 등에 사용됩니다.

4. 이진 트리 순회(Traversal)

이진 트리를 방문하는 여러 가지 방법이 있습니다:

4.1. 전위 순회(Preorder Traversal)

루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 방문합니다.

def preorder_traversal(node):
    if node is None:
        return

    print(node.data, end=" ")  # 현재 노드 방문
    preorder_traversal(node.left)  # 왼쪽 서브트리 방문
    preorder_traversal(node.right)  # 오른쪽 서브트리 방문

4.2. 중위 순회(Inorder Traversal)

왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순으로 방문합니다. 이진 검색 트리에서는 오름차순으로 노드를 방문합니다.

def inorder_traversal(node):
    if node is None:
        return

    inorder_traversal(node.left)  # 왼쪽 서브트리 방문
    print(node.data, end=" ")  # 현재 노드 방문
    inorder_traversal(node.right)  # 오른쪽 서브트리 방문

4.3. 후위 순회(Postorder Traversal)

왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순으로 방문합니다.

def postorder_traversal(node):
    if node is None:
        return

    postorder_traversal(node.left)  # 왼쪽 서브트리 방문
    postorder_traversal(node.right)  # 오른쪽 서브트리 방문
    print(node.data, end=" ")  # 현재 노드 방문

4.4. 레벨 순회(Level Order Traversal)

각 레벨의 노드를 왼쪽에서 오른쪽으로 방문합니다. 너비 우선 탐색(BFS)을 사용하여 구현합니다.

from collections import deque

def level_order_traversal(root):
    if root is None:
        return

    queue = deque([root])

    while queue:
        node = queue.popleft()
        print(node.data, end=" ")

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

5. 이진 검색 트리(BST) 연산

5.1. 삽입

def insert(root, data):
    if root is None:
        return TreeNode(data)

    if data < root.data:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)

    return root

5.2. 검색

def search(root, data):
    if root is None or root.data == data:
        return root

    if data < root.data:
        return search(root.left, data)
    return search(root.right, data)

5.3. 최소값 찾기

def find_min(root):
    current = root
    while current and current.left:
        current = current.left
    return current

5.4. 최대값 찾기

def find_max(root):
    current = root
    while current and current.right:
        current = current.right
    return current

5.5. 삭제

def delete(root, data):
    if root is None:
        return root

    # 삭제할 노드 찾기
    if data < root.data:
        root.left = delete(root.left, data)
    elif data > root.data:
        root.right = delete(root.right, data)
    else:
        # 자식이 하나이거나 없는 경우
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left

        # 두 자식이 있는 경우
        # 오른쪽 서브트리에서 가장 작은 값(중위 후속자)을 찾아 현재 노드를 대체
        temp = find_min(root.right)
        root.data = temp.data
        root.right = delete(root.right, temp.data)

    return root

6. 트리의 시간 복잡도

6.1. 이진 검색 트리(BST)

연산	평균	최악
접근	O(log n)	O(n)
검색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

6.2. 균형 이진 검색 트리(AVL, 레드-블랙 트리)

연산	평균	최악
접근	O(log n)	O(log n)
검색	O(log n)	O(log n)
삽입	O(log n)	O(log n)
삭제	O(log n)	O(log n)

7. 트리 응용

7.1. 표현식 트리(Expression Tree)

수학적 표현식을 트리 형태로 표현하여 계산할 수 있습니다.

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

    def is_operator(self, c):
        return c in ['+', '-', '*', '/', '^']

    def evaluate(self, node):
        if node is None:
            return 0

        if not self.is_operator(node.data):
            return float(node.data)

        left_val = self.evaluate(node.left)
        right_val = self.evaluate(node.right)

        if node.data == '+':
            return left_val + right_val
        elif node.data == '-':
            return left_val - right_val
        elif node.data == '*':
            return left_val * right_val
        elif node.data == '/':
            return left_val / right_val
        elif node.data == '^':
            return left_val ** right_val

7.2. 힙(Heap)

최대 힙(max heap) 또는 최소 힙(min heap)은 완전 이진 트리로 구현되며, 우선순위 큐 등에 사용됩니다.

7.3. 트라이(Trie)를 이용한 문자열 검색

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

8. 트리 실전 문제

8.1. 트리의 높이 구하기

def height(root):
    if root is None:
        return 0
    return max(height(root.left), height(root.right)) + 1

8.2. 이진 트리의 최대 경로 합

def max_path_sum(root):
    max_sum = [float('-inf')]  # 참조를 통해 최대값 갱신

    def max_gain(node):
        if not node:
            return 0

        # 왼쪽과 오른쪽 서브트리에서 얻을 수 있는 최대 이득
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # 현재 노드를 포함하는 경로의 최대 합 갱신
        current_path_sum = node.data + left_gain + right_gain
        max_sum[0] = max(max_sum[0], current_path_sum)

        # 부모 노드로 전달할 수 있는 최대 합
        return node.data + max(left_gain, right_gain)

    max_gain(root)
    return max_sum[0]

8.3. 두 이진 트리 비교

def is_same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.data != q.data:
        return False

    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

8.4. 이진 트리의 직경(Diameter)

def diameter_of_binary_tree(root):
    diameter = [0]

    def depth(node):
        if not node:
            return 0

        left_depth = depth(node.left)
        right_depth = depth(node.right)

        # 현재 노드를 지나는 경로의 길이 갱신
        diameter[0] = max(diameter[0], left_depth + right_depth)

        # 현재 노드에서의 깊이 반환
        return max(left_depth, right_depth) + 1

    depth(root)
    return diameter[0]

9. 트리의 장단점

9.1. 장점

• 계층적 데이터 표현: 자연스럽게 계층적 관계를 표현할 수 있습니다.
• 효율적인 검색: 이진 검색 트리는 평균적으로 O(log n) 시간 복잡도로 검색할 수 있습니다.
• 빠른 삽입/삭제: 균형 트리에서는 O(log n) 시간 복잡도로 삽입/삭제가 가능합니다.
• 유연성: 다양한 형태와 응용이 가능합니다.

9.2. 단점

• 구현 복잡성: 특히 균형 트리의 경우 구현이 복잡할 수 있습니다.
• 불균형: 불균형한 트리는 성능이 저하될 수 있습니다.
• 추가 메모리 사용: 포인터를 저장하기 위한 추가 메모리가 필요합니다.

10. 트리 구현 최적화

10.1. 균형 유지

AVL 트리나 레드-블랙 트리를 사용하여 균형을 유지하면 최악의 경우에도 O(log n) 성능을 보장할 수 있습니다.

10.2. 메모리 최적화

이진 트리 표현에서 메모리를 절약하는 방법:

# 배열을 사용한 이진 트리 표현
class BinaryTree:
    def __init__(self, size):
        self.tree = [None] * size

    def root(self, i):
        return i

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def parent(self, i):
        return (i - 1) // 2

    def insert(self, i, data):
        if i < len(self.tree):
            self.tree[i] = data

11. 결론

트리는 계층적 데이터를 표현하고 효율적인 검색, 삽입, 삭제 연산을 지원하는 강력한 자료구조입니다. 이진 검색 트리, AVL 트리, 레드-블랙 트리와 같은 다양한 변형이 있으며, 각각 특정 상황에 최적화되어 있습니다.

파일 시스템, 데이터베이스 인덱싱, 우선순위 큐, 표현식 평가, 문자열 처리 등 다양한 응용 분야에서 트리가 사용됩니다. 트리의 구조와 특성을 이해하고 적절하게 활용하면 효율적인 알고리즘을 설계할 수 있습니다.