트리 (Tree)

트리는 컴퓨터 과학에서 가장 중요하고 널리 사용되는 비선형 자료구조 중 하나이다.
계층적 관계를 표현하기에 적합한 구조로, 파일 시스템, 데이터베이스 색인, 검색 알고리즘 등 다양한 응용 분야에서 활용된다.

트리 자료구조는 컴퓨터 과학과 프로그래밍의 핵심 요소로, 다양한 문제와 응용 분야에서 중요한 역할을 한다.
기본적인 이진 트리부터 복잡한 세그먼트 트리, B+트리에 이르기까지 각 트리 자료구조는 특정 상황에 최적화된 성능과 기능을 제공한다.

최근의 트리 자료구조 연구와 활용 동향은 다음과 같다:

분산 시스템에서의 트리: 대규모 분산 시스템에서 일관성과 확장성을 보장하기 위한 특수한 트리 구조가 연구되고 있다.
인메모리 데이터베이스: 현대의 인메모리 데이터베이스는 최적화된 트리 구조를 사용하여 빠른 데이터 접근과 처리를 가능하게 한다.
기계 학습과 트리: 결정 트리와 그 앙상블(예: 랜덤 포레스트, 그래디언트 부스팅)은 해석 가능한 머신 러닝 모델로 계속해서 중요한 역할을 하고 있다.
양자 컴퓨팅과 트리: 양자 컴퓨팅 환경에서 효율적인 트리 알고리즘의 개발이 새로운 연구 영역으로 떠오르고 있다.
신경망과 트리의 결합: 트리 구조를 신경망과 결합하여 해석 가능성과 성능을 모두 개선하는 하이브리드 모델이 연구되고 있다.
트리 자료구조는 그 다양성과 적응성으로 인해 컴퓨터 과학의 발전과 함께 계속해서 진화하고 있으며, 미래의 컴퓨팅 패러다임에서도 중요한 위치를 차지할 것으로 예상되고 있다.
프로그래머와 컴퓨터 과학자는 다양한 트리 자료구조의 특성과 활용법을 잘 이해함으로써 효율적이고 견고한 소프트웨어 시스템을 설계하고 구현할 수 있다.

트리의 기본 개념

![Tree Data Structure](Introduction-to-tree-.webp “https://www.geeksforgeeks.org/introduction-to-tree-data-structure/)

트리의 정의

트리는 노드(node)라고 불리는 요소들과 이들을 연결하는 간선(edge)으로 구성된 계층적 자료구조이다.

다음과 같은 특성을 가진다:

하나의 루트 노드(root node)가 존재한다.
모든 노드는 0개 이상의 자식 노드(child node)를 가질 수 있다.
사이클(cycle)이 존재하지 않는다.
모든 노드는 루트 노드로부터 하나의 경로로만 도달할 수 있다.
n개의 노드를 가진 트리는 정확히 n-1개의 간선을 가진다.

트리의 용어

트리를 이해하기 위한 주요 용어들을 살펴보면:

노드(Node): 트리를 구성하는 기본 요소로 데이터와 다른 노드에 대한 참조를 포함한다.
루트 노드(Root Node): 트리의 최상위에 위치한 노드로, 부모가 없는 유일한 노드.
부모 노드(Parent Node): 특정 노드의 직속 상위 노드.
자식 노드(Child Node): 특정 노드의 직속 하위 노드.
형제 노드(Sibling Nodes): 같은 부모를 공유하는 노드들.
리프 노드(Leaf Node): 자식이 없는 노드로, 트리의 가장 말단에 위치한다.
내부 노드(Internal Node): 적어도 하나의 자식을 가진 노드로, 리프 노드가 아닌 모든 노드.
경로(Path): 한 노드에서 다른 노드로 이동하기 위해 거쳐야 하는 노드들의 순서.
깊이(Depth): 루트 노드로부터 특정 노드까지의 간선 수.
높이(Height): 루트 노드로부터 가장 먼 리프 노드까지의 간선 수.
서브트리(Subtree): 특정 노드와 그 자손들로 구성된 트리.
차수(Degree): 노드가 가진 자식 노드의 수.

트리의 기본 구현(Python)

트리의 기본적인 구현 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class TreeNode:
    def __init__(self, data):
        self.data = data          # 노드의 데이터
        self.children = []        # 자식 노드들을 담는 리스트
    
    def add_child(self, child_node):
        self.children.append(child_node)
    
    def __str__(self):
        return str(self.data)

# 트리 생성 예시
root = TreeNode("A")
node_b = TreeNode("B")
node_c = TreeNode("C")
node_d = TreeNode("D")
node_e = TreeNode("E")

root.add_child(node_b)
root.add_child(node_c)
node_b.add_child(node_d)
node_b.add_child(node_e)

트리의 순회(Traversal)

트리의 모든 노드를 방문하는 방법을 순회라고 한다.

트리의 순회 방법에는 여러 가지가 있다.

깊이 우선 순회(Depth-First Traversal)

전위 순회(Preorder Traversal)

방문 순서: 루트 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
1. 노드를 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다.

1
2
3
4
5
6
7
8
def preorder_traversal(node):
    if node is None:
        return
    
    print(node.data, end=' ')  # 현재 노드 방문
    
    for child in node.children:
        preorder_traversal(child)  # 자식 노드들 순회

특징: 루트 노드를 가장 먼저 방문하므로, 트리의 구조를 복사하거나 표현할 때 유용하다.

1
2
3
4
5
      A
     / \
    B   C
   / \ / \
  D  E F  G

예시: 위의 트리를 전위 순회하면 방문 순서는 A → B → D → E → C → F → G가 된다.

후위 순회(Postorder Traversal)

방문 순서: 왼쪽 자식 노드 → 오른쪽 자식 노드 → 루트 노드
1. 왼쪽 서브트리를 후위 순회한다.
2. 오른쪽 서브트리를 후위 순회한다.
3. 노드를 방문한다.

1
2
3
4
5
6
7
8
def postorder_traversal(node):
    if node is None:
        return
    
    for child in node.children:
        postorder_traversal(child)  # 자식 노드들 순회
    
    print(node.data, end=' ')  # 현재 노드 방문

특징: 자식 노드를 모두 방문한 후에 부모 노드를 방문하므로, 디렉토리나 파일 시스템에서 폴더를 삭제할 때와 같이 하위 요소를 먼저 처리해야 하는 경우에 유용하다.

1
2
3
4
5
      A
     / \
    B   C
   / \ / \
  D  E F  G

예시: 위 트리를 후위 순회하면 방문 순서는 D → E → B → F → G → C → A가 된다.

너비 우선 순회(Breadth-First Traversal)

너비 우선 순회는 트리의 각 레벨을 순서대로 방문하는 방법이다.
같은 레벨의 노드들을 모두 방문한 후 다음 레벨로 넘어간다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from collections import deque

def breadth_first_traversal(root):
    if root is None:
        return
    
    queue = deque([root])
    
    while queue:
        current = queue.popleft()
        print(current.data, end=' ')  # 현재 노드 방문
        
        for child in current.children:
            queue.append(child)  # 자식 노드들을 큐에 추가

이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리로, 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분된다.

이진 트리의 종류

포화 이진 트리(Full Binary Tree): 모든 내부 노드가 두 개의 자식을 가지고, 모든 리프 노드가 같은 레벨에 있는 이진 트리이다.
완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 채워져 있는 이진 트리이다.
균형 이진 트리(Balanced Binary Tree): 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1을 초과하지 않는 이진 트리이다.

이진 트리의 구현(Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None  # 왼쪽 자식
        self.right = None  # 오른쪽 자식
    
    def __str__(self):
        return str(self.data)

# 이진 트리 생성 예시
root = BinaryTreeNode(1)
root.left = BinaryTreeNode(2)
root.right = BinaryTreeNode(3)
root.left.left = BinaryTreeNode(4)
root.left.right = BinaryTreeNode(5)

이진 트리의 순회

이진 트리의 순회에는 특별히 중위 순회가 추가된다.

중위 순회(Inorder Traversal)

방문 순서: 왼쪽 자식 노드 → 루트 노드 → 오른쪽 자식 노드
1. 왼쪽 서브트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브트리를 중위 순회한다.

1
2
3
4
5
6
7
def inorder_traversal(node):
    if node is None:
        return
    
    inorder_traversal(node.left)  # 왼쪽 서브트리 순회
    print(node.data, end=' ')     # 현재 노드 방문
    inorder_traversal(node.right)  # 오른쪽 서브트리 순회

특징: 이진 탐색 트리에서 중위 순회를 하면 노드의 값이 오름차순으로 정렬된다.

1
2
3
4
5
      A
     / \
    B   C
   / \ / \
  D  E F  G

예시: 위 트리를 중위 순회하면 방문 순서는 D → B → E → A → F → C → G가 된다.

이진 트리의 중위 순회는 이진 검색 트리에서 정렬된 순서로 노드를 방문한다는 특징이 있다.

이진 검색 트리(Binary Search Tree, BST)

이진 검색 트리는 다음과 같은 특성을 가진 이진 트리이다:

모든 노드에 대해, 왼쪽 서브트리의 모든 노드 값은 현재 노드의 값보다 작다.
모든 노드에 대해, 오른쪽 서브트리의 모든 노드 값은 현재 노드의 값보다 크다.
왼쪽과 오른쪽 서브트리도 각각 이진 검색 트리이다.

이진 검색 트리의 연산

탐색(Search)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def search(root, key):
    # 기본 경우: 루트가 None이거나 키가 루트에 있는 경우
    if root is None or root.data == key:
        return root
    
    # 키가 루트보다 작은 경우
    if key < root.data:
        return search(root.left, key)
    
    # 키가 루트보다 큰 경우
    return search(root.right, key)

삽입(Insertion)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def insert(root, key):
    # 트리가 비어있는 경우, 새 노드 반환
    if root is None:
        return BinaryTreeNode(key)
    
    # 그렇지 않으면 트리를 재귀적으로 탐색
    if key < root.data:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    
    return root

삭제(Deletion)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def find_min_value_node(node):
    current = node
    
    # 가장 왼쪽 리프 노드를 찾음
    while current.left is not None:
        current = current.left
    
    return current

def delete(root, key):
    # 기본 경우
    if root is None:
        return root
    
    # 키가 루트보다 작은 경우, 왼쪽 서브트리에서 삭제
    if key < root.data:
        root.left = delete(root.left, key)
    
    # 키가 루트보다 큰 경우, 오른쪽 서브트리에서 삭제
    elif key > root.data:
        root.right = delete(root.right, key)
    
    # 키가 루트와 같은 경우, 이 노드가 삭제될 노드
    else:
        # 자식이 하나이거나 없는 경우
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        
        # 자식이 둘인 경우, 중위 후속자(오른쪽 서브트리에서 가장 작은 노드)를 찾음
        temp = find_min_value_node(root.right)
        
        # 중위 후속자의 데이터를 복사
        root.data = temp.data
        
        # 중위 후속자를 삭제
        root.right = delete(root.right, temp.data)
    
    return root

이진 검색 트리의 시간 복잡도

탐색: 평균 O(log n), 최악 O(n)
삽입: 평균 O(log n), 최악 O(n)
삭제: 평균 O(log n), 최악 O(n)

최악의 경우는 트리가 한쪽으로 치우친 경우(skewed tree)에 발생한다.

균형 이진 검색 트리(Balanced Binary Search Tree)

일반적인 이진 검색 트리는 불균형하게 구성될 경우 성능이 저하될 수 있다.
이를 해결하기 위해 자가 균형(self-balancing) 특성을 가진 트리들이, 즉 균형 이진 검색 트리가 개발되었다.

AVL 트리

AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1인 균형 이진 검색 트리이다.
균형 인수(Balance Factor)를 이용하여 균형을 유지한다.

`1`	`균형 인수(BF) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이`

균형이 깨질 경우, 회전(rotation) 연산을 통해 균형을 회복한다:

LL 회전(Right Rotation): 왼쪽으로 치우친 경우
RR 회전(Left Rotation): 오른쪽으로 치우친 경우
LR 회전(Left-Right Rotation): 왼쪽-오른쪽으로 치우친 경우
RL 회전(Right-Left Rotation): 오른쪽-왼쪽으로 치우친 경우

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

레드-블랙 트리는 각 노드가 빨간색 또는 검은색인 이진 검색 트리로, 다음과 같은 속성을 만족한다:

모든 노드는 빨간색 또는 검은색이다.
루트 노드는 검은색이다.
모든 리프 노드(NIL)는 검은색이다.
빨간색 노드의 자식은 모두 검은색이다.
모든 경로에서 검은색 노드의 수는 동일하다.
이러한 속성을 통해 트리의 균형을 유지하며, 최악의 경우에도 O(log n)의 시간 복잡도를 보장한다.

B-트리와 B+트리

B-트리와 B+트리는 이진 트리를 확장한 다분기 트리(multi-way tree)로, 한 노드가 두 개 이상의 자식을 가질 수 있다.
주로 데이터베이스와 파일 시스템에서 사용된다.

B-트리

B-트리는 다음과 같은 특성을 가진다:

모든 리프 노드는 같은 깊이에 있다.
루트를 제외한 모든 노드는 최소[m/2]개, 최대 m개의 자식을 가진다(m은 B-트리의 차수).
각 노드는 자식 수보다 하나 적은 수의 키를 가진다.

B+트리

B+트리는 B-트리의 변형으로, 다음과 같은 차이점이 있다:

모든 키는 리프 노드에도 저장된다.
리프 노드들은 연결 리스트로 연결되어 있어 순차적 접근이 용이하다.
내부 노드는 인덱스 역할만 하고, 실제 데이터는 리프 노드에 저장된다.

B+트리는 데이터베이스 인덱싱에 널리 사용된다.

트라이(Trie)

트라이는 문자열을 저장하고 검색하는 데 최적화된 트리 자료구조이다.
각 노드는 문자를 나타내며, 루트에서 특정 노드까지의 경로가 문자열을 형성한다.

트라이의 특성

루트 노드는 빈 문자를 나타낸다.
각 간선은 하나의 문자를 나타낸다.
각 노드는 여러 자식 노드를 가질 수 있다(일반적으로 알파벳 크기만큼).
어떤 노드가 단어의 끝임을 표시하는 플래그가 있다.

트라이의 구현(Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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  # 접두사가 존재함

트라이의 응용

자동 완성(auto-completion)
철자 검사(spell checking)
IP 라우팅(longest prefix matching)
문자열 검색(string searching)

힙(Heap)

힙은 완전 이진 트리 구조를 가지며, 특정 순서 속성을 만족하는 자료구조이다.
주로 우선순위 큐를 구현하는 데 사용된다.

힙의 종류

최대 힙(Max Heap)
모든 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리이다.
최소 힙(Min Heap)
모든 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리이다.

힙의 구현(Python)

Python의 heapq 모듈은 최소 힙을 제공합니다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import heapq

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

# 최소값 추출
min_value = heapq.heappop(min_heap)  # 1

# 최대 힙 구현(부호 반전 이용)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)

# 최대값 추출
max_value = -heapq.heappop(max_heap)  # 3

힙의 응용

우선순위 큐(priority queue)
다익스트라 알고리즘(Dijkstra’s algorithm)
힙 정렬(heap sort)
메디안 찾기(finding median)

세그먼트 트리(Segment Tree)

세그먼트 트리는 구간 쿼리(range query)를 효율적으로 처리하기 위한 트리 자료구조이다.
주로 구간 합, 최소값, 최대값 등을 빠르게 계산하는 데 사용된다.

세그먼트 트리의 구현(Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        # 세그먼트 트리의 크기는 원래 배열의 4배 정도면 충분
        self.tree = [0] * (4 * self.n)
        self.build(arr, 1, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            # 리프 노드
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            # 왼쪽 자식 노드 재귀 호출
            self.build(arr, 2 * node, start, mid)
            # 오른쪽 자식 노드 재귀 호출
            self.build(arr, 2 * node + 1, mid + 1, end)
            # 부모 노드 = 자식 노드들의 합
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, node, start, end, left, right):
        if left > end or right < start:
            # 구간이 겹치지 않는 경우
            return 0
        
        if left <= start and end <= right:
            # 현재 노드의 구간이 쿼리 구간에 완전히 포함되는 경우
            return self.tree[node]
        
        # 구간이 일부 겹치는 경우
        mid = (start + end) // 2
        left_sum = self.query(2 * node, start, mid, left, right)
        right_sum = self.query(2 * node + 1, mid + 1, end, left, right)
        return left_sum + right_sum
    
    def update(self, node, start, end, idx, val):
        if start == end:
            # 리프 노드인 경우 값 업데이트
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if start <= idx <= mid:
                # 왼쪽 자식으로 이동
                self.update(2 * node, start, mid, idx, val)
            else:
                # 오른쪽 자식으로 이동
                self.update(2 * node + 1, mid + 1, end, idx, val)
            # 부모 노드 업데이트
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

세그먼트 트리의 응용

구간 합(range sum) 쿼리
구간 최소/최대(range minimum/maximum) 쿼리
구간 업데이트(range update)

트리 자료구조의 실제 응용

파일 시스템
대부분의 파일 시스템은 디렉토리와 파일을 계층적으로 관리하기 위해 트리 구조를 사용한다.
각 노드는 디렉토리나 파일을 나타내며, 부모-자식 관계는 디렉토리-서브디렉토리 관계를 나타낸다.
데이터베이스 인덱싱
B-트리와 B+트리는 데이터베이스에서 인덱스를 구현하는 데 널리 사용된다.
이러한 트리는 디스크 기반 환경에서 효율적인 검색, 삽입, 삭제를 가능하게 한다.
DOM(Document Object Model)
웹 브라우저는 HTML 문서를 파싱하여 DOM 트리를 생성한다.
이 트리는 문서의 구조를 나타내며, JavaScript를 통해 접근하고 조작할 수 있다.
게임 개발의 의사 결정 트리
인공지능 기반 게임에서 컴퓨터 플레이어는 미니맥스(Minimax) 알고리즘과 같은 의사 결정 트리를 사용하여 최적의 행동을 결정한다.
네트워크 라우팅
IP 라우팅 테이블은 종종 트라이와 같은 특수한 트리 구조를 사용하여 구현된다.
이를 통해 최장 접두사 매칭(longest prefix matching)을 효율적으로 수행할 수 있다.

트리 자료구조의 시간 복잡도 비교

다양한 트리 자료구조의 주요 연산에 대한 시간 복잡도 비교:

트리 종류	검색	삽입	삭제	높이	특징
이진 검색 트리	평균: O(log n) 최악: O(n)	평균: O(log n) 최악: O(n)	평균: O(log n) 최악: O(n)	평균: O(log n) 최악: O(n)	정렬된 순서로 데이터 접근 가능
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)	균형 유지, 실제 시스템에서 많이 사용
B-트리	O(log n)	O(log n)	O(log n)	O(log n)	다분기, 디스크 기반 환경에 적합
트라이	O(m)	O(m)	O(m)	O(m)	m은 문자열 길이, 접두사 검색에 최적화
힙	O(n)	O(log n)	O(log n)	O(log n)	최대/최소 요소 빠른 접근, 우선순위 큐 구현
세그먼트 트리	O(log n)	O(log n)	O(log n)	O(log n)	구간 쿼리에 최적화

고급 트리 자료구조

스플레이 트리(Splay Tree)

스플레이 트리는 접근 패턴에 자가 최적화되는 이진 검색 트리이다.
검색, 삽입, 삭제와 같은 연산 후에 해당 노드를 루트로 이동시키는 스플레이(splay) 연산을 수행한다.

주요 특징:

최근에 접근한 요소에 빠르게 접근 가능
자주 사용되는 요소가 트리의 상단에 위치
최악의 경우에도 평균적으로 O(log n) 성능 보장
추가 메모리 없이 자가 최적화 가능

트리맵(Treemap)

트리맵은 키-값 쌍을 저장하는 정렬된 맵 인터페이스를 제공하는 자료구조로, 내부적으로 레드-블랙 트리와 같은 균형 이진 검색 트리로 구현된다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from sortedcontainers import SortedDict

# 트리맵 생성
treemap = SortedDict()
treemap['a'] = 1
treemap['c'] = 3
treemap['b'] = 2

# 정렬된 순서로 순회
for key, value in treemap.items():
    print(key, value)  # a 1, b 2, c 3

# 가장 작은/큰 키 접근
smallest_key = treemap.peekitem(0)[0]  # a
largest_key = treemap.peekitem(-1)[0]  # c

트리셋(Treeset)

트리셋은 정렬된 순서로 고유한 요소를 저장하는 집합 인터페이스를 제공하는 자료구조로, 내부적으로 균형 이진 검색 트리로 구현된다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from sortedcontainers import SortedSet

# 트리셋 생성
treeset = SortedSet([3, 1, 2, 2])  # 중복 요소는 한 번만 저장됨

# 정렬된 순서로 요소 접근
print(list(treeset))  # [1, 2, 3]

# 이진 검색
index = treeset.bisect_left(2)  # 요소 2의 위치: 1

페너위 트리(Fenwick Tree 또는 Binary Indexed Tree)

페너위 트리는 구간 합을 효율적으로 계산하고 업데이트하기 위한 자료구조이다. 세그먼트 트리보다 메모리 효율적이지만, 범위가 제한적이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    
    def update(self, idx, delta):
        """인덱스 idx의 값을 delta만큼 증가"""
        while idx <= self.size:
            self.tree[idx] += delta
            idx += idx & -idx  # 최하위 비트 더하기
    
    def prefix_sum(self, idx):
        """인덱스 1부터 idx까지의 합 계산"""
        result = 0
        while idx > 0:
            result += self.tree[idx]
            idx -= idx & -idx  # 최하위 비트 빼기
        return result
    
    def range_sum(self, left, right):
        """left부터 right까지의 구간 합 계산"""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

R-트리(R-Tree)

R-트리는 공간 데이터(예: 좌표, 지리적 위치)를 인덱싱하기 위한 트리 자료구조이다.
다차원 객체를 직사각형의 최소 경계 상자(minimum bounding rectangle, MBR)로 묶어 계층적으로 구성한다.

주요 특징:

공간 데이터 검색을 위한 최적화
근접 검색, 범위 검색에 효율적
GIS(지리 정보 시스템)와 데이터베이스에서 널리 사용
각 노드는 여러 항목의 MBR을 포함

트리의 구현과 관련된 심화 주제

메모리 효율적인 트리 구현

대규모 트리를 효율적으로 구현하기 위한 메모리 최적화 기법:

노드 표현 최적화

1
2
3
4
5
6
7
class CompactNode:
    __slots__ = ['data', 'left', 'right']  # __slots__를 사용하여 메모리 사용량 감소
    
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

트리 압축 기법

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 경로 압축을 사용한 트라이
class CompressedTrie:
    def __init__(self):
        self.root = {}
    
    def insert(self, word):
        node = self.root
        i = 0
        while i < len(word):
            # 현재 노드에서 시작하는 가장 긴 공통 접두사 찾기
            prefix = ""
            for key in node:
                j = 0
                while i + j < len(word) and j < len(key) and word[i + j] == key[j]:
                    prefix += word[i + j]
                    j += 1
                if j > 0:  # 공통 접두사가 있는 경우
                    # 기존 키 분할
                    old_key = key
                    old_value = node[old_key]
                    del node[old_key]
                    
                    if j == len(old_key):  # 키가 완전히 일치
                        node[prefix] = old_value
                        i += j
                    else:  # 부분 일치
                        # 분할 지점 생성
                        node[prefix] = {}
                        node[prefix][old_key[j:]] = old_value
                        i += j
                    break
            
            # 일치하는 접두사가 없는 경우
            if not prefix:
                node[word[i:]] = {}
                break
        
        # 단어의 끝 표시
        if isinstance(node, dict):
            node[""] = True

병렬 트리 알고리즘

멀티코어 환경에서 트리 연산을 최적화하기 위한 병렬 처리 기법:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import concurrent.futures

def parallel_tree_traversal(root):
    if root is None:
        return []
    
    result = [root.data]
    
    with concurrent.futures.ThreadPoolExecutor() as executor:
        left_future = executor.submit(parallel_tree_traversal, root.left)
        right_future = executor.submit(parallel_tree_traversal, root.right)
        
        left_result = left_future.result()
        right_result = right_future.result()
    
    return result + left_result + right_result

영속적 트리(Persistent Tree)

영속적 트리는 이전 버전을 유지하면서 수정 가능한 자료구조이다.
일반적으로 경로 복사(path copying) 또는 노드 복사(node copying) 기법을 사용한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class PersistentTreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def insert(root, key):
    """새 노드를 삽입하고 새 트리 버전 반환"""
    if root is None:
        return PersistentTreeNode(key)
    
    if key < root.data:
        # 왼쪽 서브트리에 삽입하고 새 트리 생성
        new_left = insert(root.left, key)
        return PersistentTreeNode(root.data, new_left, root.right)
    else:
        # 오른쪽 서브트리에 삽입하고 새 트리 생성
        new_right = insert(root.right, key)
        return PersistentTreeNode(root.data, root.left, new_right)

트리의 응용 심화

결정 트리(Decision Tree)
결정 트리는 기계 학습에서 사용되는 예측 모델링 도구로, 데이터의 특성을 기반으로 분류나 회귀 분석을 수행한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris

# 아이리스 데이터셋 로드
iris = load_iris()
X, y = iris.data, iris.target

# 결정 트리 분류기 생성 및 훈련
clf = DecisionTreeClassifier(max_depth=3)
clf.fit(X, y)

# 새 데이터 예측
predictions = clf.predict([[5.1, 3.5, 1.4, 0.2]])

구문 분석 트리(Parse Tree)
구문 분석 트리는 프로그래밍 언어나 자연어의 구문 구조를 표현하는 트리이다.
컴파일러나 인터프리터에서 중요한 역할을 한다.

1
2
3
4
5
6
7
8
9
import ast

# Python 코드 파싱
code = "def factorial(n):\n    if n <= 1:\n        return 1\n    return n * factorial(n-1)"
tree = ast.parse(code)

# AST(Abstract Syntax Tree) 순회
for node in ast.walk(tree):
    print(type(node).__name__)

최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리는 그래프의 모든 정점을 연결하는 트리 중에서 간선 가중치의 합이 최소인 트리이다.
크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 대표적이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 크루스칼 알고리즘 구현
def kruskal(graph, vertices):
    """
    graph: (u, v, w) 형태의 간선 리스트 (u, v: 정점, w: 가중치)
    vertices: 정점의 수
    """
    # 간선을 가중치 기준으로 정렬
    graph.sort(key=lambda edge: edge[2])

    # Union-Find 자료구조 초기화
    parent = list(range(vertices))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        parent[find(x)] = find(y)

    mst = []
    for u, v, w in graph:
        if find(u) != find(v):  # 사이클이 생기지 않는 경우
            union(u, v)
            mst.append((u, v, w))

    return mst

접미사 트리(Suffix Tree)
접미사 트리는 문자열의 모든 접미사를 저장하는 압축된 트라이이다.
문자열 검색, 패턴 매칭, 최장 공통 부분 문자열 찾기 등에 사용된다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 단순화된 접미사 트리 구현 (실제로는 Ukkonen의 알고리즘을 사용)
class SuffixTreeNode:
    def __init__(self):
        self.children = {}
        self.indices = []

class SuffixTree:
    def __init__(self, text):
        self.root = SuffixTreeNode()
        self.text = text

        # 모든 접미사 삽입
        for i in range(len(text)):
            self._insert_suffix(i)

    def _insert_suffix(self, idx):
        node = self.root
        suffix = self.text[idx:]

        for char in suffix:
            if char not in node.children:
                node.children[char] = SuffixTreeNode()
            node = node.children[char]
            node.indices.append(idx)

    def search(self, pattern):
        """패턴이 시작하는 모든 인덱스 반환"""
        node = self.root

        for char in pattern:
            if char not in node.children:
                return []
            node = node.children[char]

        return node.indices

트리의 활용 사례와 실전 예시

파일 시스템 구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class FileSystemNode:
    def __init__(self, name, is_directory=False):
        self.name = name
        self.is_directory = is_directory
        self.children = {} if is_directory else None
        self.content = "" if not is_directory else None
    
    def add_child(self, child):
        if not self.is_directory:
            raise ValueError("Cannot add child to a file")
        self.children[child.name] = child
    
    def get_child(self, name):
        if not self.is_directory:
            return None
        return self.children.get(name)
    
    def list_contents(self, indent=0):
        prefix = " " * indent
        print(f"{prefix}{self.name}{'/' if self.is_directory else ''}")
        
        if self.is_directory:
            for child in self.children.values():
                child.list_contents(indent + 2)

# 파일 시스템 예시
root = FileSystemNode("root", True)
documents = FileSystemNode("documents", True)
pictures = FileSystemNode("pictures", True)
resume = FileSystemNode("resume.txt", False)
photo = FileSystemNode("photo.jpg", False)

root.add_child(documents)
root.add_child(pictures)
documents.add_child(resume)
pictures.add_child(photo)

# 파일 시스템 탐색
root.list_contents()

데이터베이스 인덱스 시뮬레이션

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class BPlusTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []
        self.next = None  # 리프 노드 연결을 위한 참조

class BPlusTree:
    def __init__(self, order):
        self.root = BPlusTreeNode(True)
        self.order = order  # B+트리의 차수
    
    def search(self, key):
        """키에 해당하는 값을 검색"""
        node = self._find_leaf(self.root, key)
        for i, k in enumerate(node.keys):
            if k == key:
                return i  # 실제로는 값을 반환하지만, 여기서는 간단히 인덱스만 반환
        return None
    
    def _find_leaf(self, node, key):
        """키가 있을 리프 노드 찾기"""
        if node.leaf:
            return node
        
        # 적절한 자식 노드 찾기
        i = 0
        while i < len(node.keys) and key >= node.keys[i]:
            i += 1
        
        return self._find_leaf(node.children[i], key)
    
    # 삽입, 삭제 등 다른 메서드는 복잡성을 위해 생략

게임 개발에서의 AI 의사 결정

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class GameState:
    def __init__(self, board, player):
        self.board = board
        self.player = player
    
    def get_possible_moves(self):
        # 현재 상태에서 가능한 모든 이동 반환
        # (구현은 게임에 따라 다름)
        pass
    
    def make_move(self, move):
        # 이동을 적용하고 새 상태 반환
        # (구현은 게임에 따라 다름)
        pass
    
    def evaluate(self):
        # 현재 상태의 점수 평가
        # (구현은 게임에 따라 다름)
        pass
    
    def is_terminal(self):
        # 게임이 종료 상태인지 확인
        # (구현은 게임에 따라 다름)
        pass

def minimax(state, depth, is_maximizing):
    """미니맥스 알고리즘 구현"""
    if depth == 0 or state.is_terminal():
        return state.evaluate()
    
    if is_maximizing:
        max_eval = float('-inf')
        for move in state.get_possible_moves():
            new_state = state.make_move(move)
            eval = minimax(new_state, depth - 1, False)
            max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = float('inf')
        for move in state.get_possible_moves():
            new_state = state.make_move(move)
            eval = minimax(new_state, depth - 1, True)
            min_eval = min(min_eval, eval)
        return min_eval

트리 (Tree)#

트리의 기본 개념#

트리의 정의#

트리의 용어#

트리의 기본 구현(Python)#

트리의 순회(Traversal)#

깊이 우선 순회(Depth-First Traversal)#

전위 순회(Preorder Traversal)#

후위 순회(Postorder Traversal)#

너비 우선 순회(Breadth-First Traversal)#

이진 트리(Binary Tree)#

이진 트리의 종류#

이진 트리의 구현(Python)#

이진 트리의 순회#

중위 순회(Inorder Traversal)#

이진 검색 트리(Binary Search Tree, BST)#

이진 검색 트리의 연산#

탐색(Search)#

삽입(Insertion)#

삭제(Deletion)#

이진 검색 트리의 시간 복잡도#

균형 이진 검색 트리(Balanced Binary Search Tree)#

AVL 트리#

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

B-트리와 B+트리#

B-트리#

B+트리#

트라이(Trie)#

트라이의 특성#

트라이의 구현(Python)#

트라이의 응용#

힙(Heap)#

힙의 종류#

힙의 구현(Python)#

힙의 응용#

세그먼트 트리(Segment Tree)#

세그먼트 트리의 구현(Python)#

세그먼트 트리의 응용#

트리 자료구조의 실제 응용#

트리 자료구조의 시간 복잡도 비교#

고급 트리 자료구조#

스플레이 트리(Splay Tree)#

트리맵(Treemap)#

트리셋(Treeset)#

페너위 트리(Fenwick Tree 또는 Binary Indexed Tree)#

R-트리(R-Tree)#

트리의 구현과 관련된 심화 주제#

메모리 효율적인 트리 구현#

노드 표현 최적화#

트리 압축 기법#

병렬 트리 알고리즘#

영속적 트리(Persistent Tree)#

트리의 응용 심화#

트리의 활용 사례와 실전 예시#

파일 시스템 구현#

데이터베이스 인덱스 시뮬레이션#

게임 개발에서의 AI 의사 결정#

참고 및 출처#