트리의 개념과 다양한 트리의 종류 소개

 트리는 계층적 구조를 가진 비선형 자료구조로, 데이터가 부모-자식 관계로 연결된 노드들로 구성됩니다. 트리는 루트 노드에서 시작하여 여러 자식 노드로 확장될 수 있으며, 모든 노드는 단 하나의 부모 노드만을 가질 수 있습니다. 트리는 그래프의 한 종류이지만, 사이클이 없는 비순환 연결 그래프라는 점에서 차별화됩니다. 트리는 파일 시스템, 조직도, 데이터베이스 인덱싱 등 다양한 분야에서 사용됩니다.

---

트리의 기본 구조와 용어

트리는 노드(node)와 간선(edge)으로 구성됩니다. 각 노드에는 데이터를 저장하고, 루트에서 자식 노드로 이어지는 연결이 간선으로 표현됩니다. 트리의 주요 용어는 다음과 같습니다.

• 루트 노드 (Root Node): 트리의 최상위 노드로, 부모가 없는 유일한 노드입니다.
• 자식 노드 (Child Node): 특정 노드의 하위에 연결된 노드입니다.
• 부모 노드 (Parent Node): 자식 노드를 가지는 노드입니다.
• 잎 노드 (Leaf Node): 자식이 없는 노드로, 트리의 말단에 위치합니다.
• 높이 (Height): 트리의 루트 노드에서 잎 노드까지의 가장 긴 경로의 길이를 뜻합니다.

---

트리의 종류와 예시 코드

1. 이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 자식 노드는 **왼쪽 자식(left child)**과 **오른쪽 자식(right child)**으로 구분됩니다. 이진 트리는 노드의 구조를 단순화하여 다양한 알고리즘에 유리하며, 특히 탐색에 적합합니다.

이진 트리 구현 (Python)

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

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

    # 노드 추가 (왼쪽 또는 오른쪽)
    def insert_left(self, current_node, data):
        current_node.left = Node(data)

    def insert_right(self, current_node, data):
        current_node.right = Node(data)

# 사용 예시
tree = BinaryTree(1)
tree.insert_left(tree.root, 2)
tree.insert_right(tree.root, 3)
tree.insert_left(tree.root.left, 4)
tree.insert_right(tree.root.left, 5)
# 트리 구조:
#        1
#       / \
#      2   3
#     / \
#    4   5

2. 이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리는 이진 트리의 한 종류로, 모든 노드가 특정 규칙에 따라 정렬된 트리입니다. 왼쪽 서브트리에는 부모 노드보다 작은 값이, 오른쪽 서브트리에는 부모 노드보다 큰 값이 저장됩니다. 이 규칙을 통해 빠른 탐색이 가능하여 데이터 검색, 삽입, 삭제에 자주 활용됩니다.

이진 탐색 트리 구현 (Python)

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    # 노드 삽입
    def insert(self, data):
        if not self.root:
            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)

# 사용 예시
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(2)
bst.insert(7)
# 트리 구조:
#        10
#       /  \
#      5    15
#     / \
#    2   7

3. 균형 트리 (Balanced Tree)

균형 트리는 노드들이 균형 있게 배치된 트리로, 특정 규칙에 따라 좌우 서브트리의 높이 차이가 적습니다. 대표적인 균형 트리로 AVL 트리와 레드-블랙 트리가 있습니다. 이러한 트리는 이진 탐색 트리의 불균형 문제를 해결하여, 탐색, 삽입, 삭제 연산이 더 빠르게 이루어지도록 합니다.

4. 힙 (Heap)

힙은 완전 이진 트리의 일종으로, 부모 노드가 자식 노드보다 크거나 작은 특성을 가집니다. 모든 부모 노드가 자식 노드보다 크면 최대 힙(Max Heap), 자식보다 작으면 **최소 힙(Min Heap)**이라고 합니다. 힙은 우선순위 큐(Priority Queue)를 구현하는 데 유용하게 사용됩니다.

최소 힙 구현 (Python)

import heapq

# 힙 생성
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 2)

print("최소 힙:", min_heap)  # 출력: [1, 2, 4, 3]
print("가장 작은 요소 추출:", heapq.heappop(min_heap))  # 출력: 1
print("추출 후 최소 힙:", min_heap)  # 출력: [2, 3, 4]

5. 트라이 (Trie)

트라이는 문자열이나 문자열 집합을 저장하고 검색하는 데 특화된 트리입니다. 특히 문자열 탐색에서 유용하며, 자동 완성, 사전 데이터 저장 등의 기능을 구현하는 데 사용됩니다.

트라이 구현 (Python)

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):
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_end_of_word = True

    # 단어 검색
    def search(self, word):
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.is_end_of_word

# 사용 예시
trie = Trie()
trie.insert("hello")
trie.insert("hi")
print("hello 검색:", trie.search("hello"))  # 출력: True
print("world 검색:", trie.search("world"))  # 출력: False

---

트리 종류 요약

트리 종류	설명	예시 사용 분야
이진 트리	각 노드가 최대 두 개의 자식을 가짐	수식 표현, 게임 트리
이진 탐색 트리 (BST)	왼쪽은 작고, 오른쪽은 큰 노드로 구성됨	데이터 탐색, 정렬
균형 트리	노드들이 균형 있게 배치된 트리	데이터베이스 인덱싱, 검색
힙	최대 힙 또는 최소 힙을 유지하는 트리	우선순위 큐, 작업 스케줄링
트라이	문자열 검색에 특화된 트리	자동 완성 기능, 사전 데이터 관리

트리는 다양한 종류와 특성을 가지며, 각 특성에 따라 특정 응용 분야에서 강력한 성능을 발휘합니다.