2-5. 자료구조: 트리
1. 트리: 자료구조의 계층적 표현
트리는 컴퓨터 과학에서 데이터를 계층적으로 표현하는 데 사용되는 비선형 자료구조입니다. 마치 실제 세상의 나무와 같이, 트리는 노드(node)와 엣지(edge)로 구성됩니다. 노드는 데이터를 저장하며, 엣지는 노드 간의 관계를 나타냅니다. 트리 구조는 데이터 간의 부모-자식 관계를 명확하게 표현하므로, 계층적인 데이터를 효율적으로 관리하고 검색하는 데 매우 유용합니다.
트리는 다양한 형태와 종류를 가지며, 각 종류는 특정 문제 해결에 특화되어 있습니다. 예를 들어, 파일 시스템, 조직도, 의사 결정 트리 등 다양한 곳에서 트리가 활용됩니다.
2. 트리 용어 및 기본 개념
트리의 기본적인 용어들을 살펴보겠습니다.
- 노드 (Node): 트리를 구성하는 기본 요소로, 데이터를 저장합니다.
- 엣지 (Edge): 노드 간의 연결 선으로, 부모-자식 관계를 나타냅니다.
- 루트 노드 (Root node): 트리의 최상위 노드로, 부모 노드가 없습니다.
- 자식 노드 (Child node): 특정 노드 아래에 연결된 노드.
- 부모 노드 (Parent node): 특정 노드의 상위 노드.
- 리프 노드 (Leaf node): 자식 노드가 없는 노드 (단말 노드).
- 레벨 (Level): 루트 노드부터 특정 노드까지의 거리. 루트 노드는 레벨 0입니다.
- 깊이 (Depth): 루트 노드에서 특정 노드까지의 엣지 수.
- 높이 (Height): 트리에서 가장 긴 경로의 길이 (리프 노드까지의 최대 레벨).
- 서브트리 (Subtree): 트리 내의 특정 노드와 그 자손 노드들로 구성된 작은 트리.
3. 트리 종류
트리는 여러 종류로 나눌 수 있으며, 대표적인 종류로는 이진 트리와 이진 탐색 트리가 있습니다.
1) 이진 트리 (Binary Tree)
이진 트리는 각 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지는 트리입니다. 이진 트리는 다양한 형태로 구현될 수 있으며, 특정 목적에 따라 여러 변형된 형태가 사용됩니다.
- 정 이진 트리 (Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖습니다.
- 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 채워집니다.
- 포화 이진 트리 (Perfect Binary Tree): 모든 레벨이 완전히 채워져 있으며, 모든 리프 노드가 같은 깊이를 가집니다.
2) 이진 탐색 트리 (Binary Search Tree, BST)
이진 탐색 트리는 이진 트리의 특별한 형태입니다. 이진 탐색 트리의 각 노드는 다음의 BST 속성을 만족합니다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 작습니다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 큽니다.
- 각 서브트리도 이진 탐색 트리입니다.
이러한 특성 때문에 이진 탐색 트리는 탐색(Search)에 매우 효율적입니다.
4. 이진 탐색 트리 구현
이진 탐색 트리는 일반적으로 노드 클래스로 구현되며, 각 노드는 데이터와 왼쪽/오른쪽 자식 노드에 대한 포인터를 가집니다.
1) 노드 클래스 정의
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
2) 삽입 (Insertion)
새로운 노드를 트리에 삽입하는 과정은 다음과 같습니다.
- 루트 노드부터 시작하여 삽입할 노드의 값과 비교합니다.
- 삽입할 노드의 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동하고, 크면 오른쪽 서브트리로 이동합니다.
- 빈 위치 (None)를 찾을 때까지 2단계를 반복합니다.
- 빈 위치에 새로운 노드를 삽입합니다.
class BST:
def __init__(self):
self.root = None
def insert(self, key):
new_node = Node(key)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if key < current.key:
if current.left is None:
current.left = new_node
return
current = current.left
elif key > current.key:
if current.right is None:
current.right = new_node
return
current = current.right
else: # 중복된 값은 삽입하지 않음
return
3) 탐색 (Search)
특정 값을 가진 노드를 찾는 과정은 다음과 같습니다.
- 루트 노드부터 시작하여 찾으려는 값과 비교합니다.
- 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료합니다.
- 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동하고, 크면 오른쪽 서브트리로 이동합니다.
- 찾는 값을 찾거나, 더 이상 탐색할 노드가 없을 때까지 2, 3단계를 반복합니다.
def search(self, key):
current = self.root
while current:
if key == current.key:
return True
elif key < current.key:
current = current.left
else:
current = current.right
return False
4) 삭제 (Deletion)
노드를 삭제하는 과정은 삽입, 탐색보다 복잡합니다. 삭제하려는 노드의 자식 노드 수에 따라 세 가지 경우로 나뉩니다.
- 삭제할 노드가 리프 노드인 경우: 해당 노드를 삭제합니다.
- 삭제할 노드가 하나의 자식 노드를 가진 경우: 해당 노드를 삭제하고, 자식 노드를 부모 노드에 연결합니다.
- 삭제할 노드가 두 개의 자식 노드를 가진 경우: 해당 노드의 자리에 successor (오른쪽 서브트리에서 가장 작은 값) 또는 predecessor (왼쪽 서브트리에서 가장 큰 값)를 대체하고, successor 또는 predecessor 노드를 삭제합니다.
def delete(self, key):
self.root = self._delete_recursive(self.root, key)
def _delete_recursive(self, root, key):
if not root:
return root
if key < root.key:
root.left = self._delete_recursive(root.left, key)
elif key > root.key:
root.right = self._delete_recursive(root.right, key)
else:
# 노드가 하나 또는 없는 자식을 가진 경우
if not root.left:
return root.right
elif not root.right:
return root.left
# 노드가 두 개의 자식을 가진 경우
root.key = self._min_value_node(root.right).key
root.right = self._delete_recursive(root.right, root.key)
return root
def _min_value_node(self, node):
current = node
while current.left:
current = current.left
return current
5. 트리 순회 (Traversal)
트리 순회는 트리의 모든 노드를 방문하는 방법을 의미합니다. 대표적인 트리 순회 방법은 다음과 같습니다.
1) 전위 순회 (Preorder Traversal)
루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 노드를 방문합니다.
def preorder_traversal(self, node):
if node:
print(node.key, end=" ")
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
2) 중위 순회 (Inorder Traversal)
왼쪽 서브트리 → 루트 노드 → 오른쪽 서브트리 순으로 노드를 방문합니다. 이진 탐색 트리에서 중위 순회는 정렬된 순서로 노드를 방문합니다.
def inorder_traversal(self, node):
if node:
self.inorder_traversal(node.left)
print(node.key, end=" ")
self.inorder_traversal(node.right)
3) 후위 순회 (Postorder Traversal)
왼쪽 서브트리 → 오른쪽 서브트리 → 루트 노드 순으로 노드를 방문합니다.
def postorder_traversal(self, node):
if node:
self.postorder_traversal(node.left)
self.postorder_traversal(node.right)
print(node.key, end=" ")
4) 레벨 순회 (Level Order Traversal)
각 레벨별로 왼쪽에서 오른쪽으로 노드를 방문합니다. 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다.
6. 이진 탐색 트리의 활용
이진 탐색 트리는 다음과 같은 분야에서 널리 활용됩니다.
- 데이터베이스 인덱싱: 빠른 검색을 위해 데이터베이스 시스템에서 인덱스를 구성하는 데 사용됩니다.
- 파일 시스템: 파일 및 디렉토리 구조를 구성하고 관리하는 데 사용됩니다.
- 정렬: 데이터를 효율적으로 정렬하는 데 사용됩니다. (중위 순회를 통해 정렬 가능)
- 컴퓨터 그래픽스: 3D 모델의 공간 분할 (예: KD-tree)에 활용됩니다.
- 컴파일러: 변수 테이블 및 심볼 테이블 구현에 사용됩니다.
7. 균형 트리 (Balanced Tree)
이진 탐색 트리의 성능은 트리의 균형에 크게 의존합니다. 최악의 경우, 트리가 한쪽으로 기울어진 형태(linked list와 유사)가 되어 탐색, 삽입, 삭제 연산의 시간 복잡도가 $O(n)$이 될 수 있습니다. 이러한 문제를 해결하기 위해, 트리의 균형을 유지하는 균형 트리 (예: AVL 트리, Red-Black 트리)가 사용됩니다. 균형 트리는 탐색, 삽입, 삭제 연산의 시간 복잡도를 $O(log n)$으로 유지하여, 대규모 데이터 세트에서도 효율적인 성능을 보장합니다.
8. 트리 사용 시 주의사항
- 균형 유지가 중요합니다: 이진 탐색 트리의 성능은 트리의 균형에 크게 의존합니다. 불균형 트리는 성능 저하를 초래하므로, 균형 트리를 고려하거나, 불균형 트리의 경우 주기적인 재구성을 수행해야 합니다.
- 메모리 사용을 고려합니다: 트리는 각 노드가 자식 노드에 대한 포인터를 저장하므로, 노드의 수가 많아질수록 메모리 사용량이 증가합니다. 대규모 데이터를 처리할 때는 메모리 사용량을 고려하여 설계를 해야 합니다.
- 삭제 연산의 구현을 신중하게 합니다: 노드 삭제 시, 삭제된 노드의 자식 노드들을 적절하게 재배치해야 합니다. 잘못된 구현은 트리의 구조를 손상시키고, 데이터 손실을 야기할 수 있습니다.
- 특정 상황에 맞는 트리를 선택합니다: 트리의 종류와 각 트리의 특성을 이해하고, 문제의 특성에 맞는 트리를 선택하는 것이 중요합니다.
9. 결론
트리는 계층적인 데이터를 효율적으로 관리하고 검색하기 위한 강력한 자료구조입니다. 이진 트리를 비롯한 다양한 트리 종류를 이해하고, 각 트리의 특성과 활용 방법을 숙지하면, 문제 해결 능력을 향상시키는 데 도움이 될 것입니다. 특히, 이진 탐색 트리는 검색, 삽입, 삭제 연산에서 뛰어난 성능을 보이며, 다양한 분야에서 널리 활용됩니다. 균형 트리의 개념을 이해하고, 상황에 맞게 활용하는 것 또한 중요합니다.
Coding Test
Comments (0)
No comments yet. Be the first to comment!
Please to write a comment.