Post

Tree 트리(2)

Tree 트리의 종류

Posted
By song yeong rok
11 min read
Tree 트리(2)

1. 이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 구조이다. 자식 노드는 왼쪽과 오른쪽으로 구분되며, 주로 계층적 데이터 표현이나 간단한 탐색 트리에 사용된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class BinaryTreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

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

print("Binary Tree Root:", root.key)  # 결과: 1

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

이진 탐색 트리는 이진 트리의 특수한 형태로, 각 노드의 왼쪽 서브트리에는 부모 노드보다 작은 값들이, 오른쪽 서브트리에는 더 큰 값들이 저장되는 구조이다. 이 특성 덕분에 빠른 검색이 가능하다.

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

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

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

    def insert(self, key):
        if self.root is None:
            self.root = BSTNode(key)
        else:
            self._insert(self.root, key)

    def _insert(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = BSTNode(key)
            else:
                self._insert(node.left, key)
        else:
            if node.right is None:
                node.right = BSTNode(key)
            else:
                self._insert(node.right, key)

# BST 생성 예시
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(7)
print("BST Root:", bst.root.key)  # 결과: 10

3. 힙 (Heap)

힙은 완전 이진 트리 구조로 최대 힙과 최소 힙으로 구분된다. 최대 힙에서는 부모 노드가 자식 노드보다 크고, 최소 힙에서는 부모 노드가 자식 노드보다 작다. 힙은 우선순위 큐와 같은 자료구조를 구현할 때 유용하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import heapq

# Min-Heap 예시
min_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 20)
print("Min Heap:", min_heap)  # 결과: [5, 10, 20]

# Max-Heap 예시 (음수로 변환하여 사용)
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -20)
print("Max Heap:", [-x for x in max_heap])  # 결과: [20, 10, 5]

4. 트라이 (Trie)

트라이는 문자열 검색에 최적화된 트리이다. 문자열의 각 문자마다 노드를 생성하여 접두사를 빠르게 검색할 수 있다. 검색 엔진, 사전 등에서 문자열 검색이나 자동 완성 기능에 자주 사용된다.

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

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

# Trie 사용 예시
trie = Trie()
trie.insert("hello")
print("Search 'hello':", trie.search("hello"))  # 결과: True
print("Search 'world':", trie.search("world"))  # 결과: False

5. AVL 트리

AVL 트리는 균형을 유지하는 이진 탐색 트리(BST)의 한 종류로, 높이 균형 트리라고도 한다. AVL 트리는 트리의 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1을 넘지 않도록 한다. 만약 삽입이나 삭제 연산 중 이 균형이 깨진다면, 트리 회전(Rotation) 연산을 통해 균형을 복구한다.

  • 이름 유래: AVL 트리는 두 발명가 Adelson-Velsky와 Landis의 이름을 따서 지어졌다.
  • 주요 특징:
    • 이진 탐색 트리의 속성을 가지면서 균형을 유지한다.
    • 삽입 및 삭제 연산 후 높이 균형을 맞추기 위해 회전 연산을 수행한다.
    • 탐색, 삽입, 삭제의 시간 복잡도는 모두 (O(\log n))이다.

AVL 트리의 회전(Rotation)

AVL 트리는 불균형이 발생했을 때 트리의 균형을 맞추기 위해 회전 연산을 수행한다. 회전에는 단일 회전(Single Rotation)과 이중 회전(Double Rotation)이 있으며, 삽입된 위치에 따라 회전 방식이 달라진다.

  1. LL 회전 (Left-Left): 왼쪽 자식의 왼쪽 서브트리에 삽입되었을 때 불균형 해소를 위해 오른쪽으로 회전.
  2. RR 회전 (Right-Right): 오른쪽 자식의 오른쪽 서브트리에 삽입되었을 때 불균형 해소를 위해 왼쪽으로 회전.
  3. LR 회전 (Left-Right): 왼쪽 자식의 오른쪽 서브트리에 삽입되었을 때, 좌-우 방향으로 이중 회전을 수행.
  4. RL 회전 (Right-Left): 오른쪽 자식의 왼쪽 서브트리에 삽입되었을 때, 우-좌 방향으로 이중 회전을 수행.

AVL 트리의 회전 연산은 구현이 복잡하여 코드로 나타내기 어렵지만, AVL 트리는 회전을 통해 항상 트리의 균형을 유지하도록 한다.

AVL 트리의 활용

AVL 트리는 데이터가 빈번히 삽입되고 삭제되는 상황에서 균형을 유지하면서 효율적인 검색을 제공하는 데 유리하다. 특히, 빠른 데이터 접근이 필요한 경우 효율적으로 사용될 수 있다.

6. B-트리

B-트리는 균형을 유지하는 다중 자식 트리(Multi-way Tree)의 일종으로, 대용량 데이터를 효율적으로 저장하고 탐색할 수 있도록 설계된 트리 자료구조이다. 주로 데이터베이스와 파일 시스템에 사용되며, 노드 하나에 여러 키를 저장하고 자식 노드도 여러 개 가질 수 있다. B-트리는 대개 디스크 기반 시스템에서 성능을 극대화하기 위해 설계되었다.

  • 특징:
    • 각 노드에 여러 개의 키와 자식 노드를 가질 수 있다.
    • B-트리는 항상 균형을 유지하며, 모든 리프 노드가 같은 높이를 유지한다.
    • 검색, 삽입, 삭제 연산의 시간 복잡도는 (O(\log n))이다.

B-트리의 구조

B-트리는 차수(Order)라는 속성을 가지며, 트리의 각 노드는 최대 차수만큼의 자식 노드와 키를 가질 수 있다. 예를 들어, 차수 3인 B-트리는 한 노드에 최대 2개의 키와 3개의 자식 노드를 가질 수 있다. 새 노드를 삽입할 때 노드가 차수 이상으로 가득 차게 되면 분할(Split) 연산을 수행하여 트리를 균형 상태로 유지한다.

  • 삽입과 분할: 노드가 가득 차면 노드를 분할하여 부모 노드에 새로운 노드를 생성하고, 키를 상위 노드로 올린다.
  • 삭제와 병합: 노드의 키가 너무 적어질 경우, 형제 노드에서 키를 빌리거나 병합하여 균형을 유지한다.

B+ 트리

B+ 트리는 B-트리의 변형으로, 모든 키가 리프 노드에 저장되고 리프 노드가 순서대로 연결된 구조이다. B+ 트리는 B-트리보다 범위 검색이 더 효율적이다. 데이터베이스 인덱스에서 흔히 사용된다.

B-트리의 활용

B-트리는 대용량 데이터베이스에서 인덱싱을 효율적으로 수행하는 데 적합하다. 특히, 디스크 접근이 많은 경우 B-트리는 한 번의 접근으로 더 많은 데이터를 불러올 수 있어 성능이 높다. 데이터베이스 관리 시스템, 파일 시스템의 인덱스 등에 자주 사용된다.

AVL 트리와 B-트리는 모두 효율적인 검색과 균형 유지에 유리한 트리 구조이지만, 활용되는 환경과 목적이 다르다. AVL 트리는 메모리 내 자료 관리에 적합하고, B-트리는 디스크 기반 대용량 데이터 관리에서 최적의 성능을 발휘하도록 설계된 트리 구조이다.

CS, Data Structure
Computer Science Data Structure Tree
This post is licensed under CC BY 4.0 by the author.