[자료구조] 트리 (이진 트리, 이진 탐색 트리)
들어가며
트리는 컴퓨터 과학에서 자주 사용되는 기본적인 자료 구조 중 하나이다. 그 중에서도 이진 트리와 이진 탐색 트리는 특히 중요한 역할을 한다. 이 글에서는 이 두 자료 구조의 특징, 차이점 및 활용 예에 대해 알아보려고 한다.
이진 트리(Binary Tree)
정의: 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리이다. 이 두 자식 노드를 각각 왼쪽 자식과 오른쪽 자식이라고 부른다.
이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 특별한 형태로, 특정한 규칙을 따르는 구조를 가진다.
이진 탐색 트리의 핵심 원칙은 아래와 같다.
“모든 노드는 왼쪽 하위 트리에 있는 노드의 값들보다 크고, 오른쪽 하위 트리에 있는 노드의 값들보다 작다.”
이 원칙은 간단해 보이지만, 이를 통해 우리는 탐색, 삽입, 삭제 등의 연산을 매우 효율적으로 수행할 수 있게 된다. 즉, 이 원칙이 BST에 높은 성능을 제공하는 핵심 요소가 된다.
한눈에 봐도 이 규칙을 통해 트리의 왼쪽 가지는 항상 부모 노드보다 작은 값을, 오른쪽 가지는 부모 노드보다 큰 값을 갖게 된다. 이러한 구조는 데이터를 정렬된 상태로 보관하는 것과 유사하게 작동하므로, 이진 탐색 트리에서의 탐색 연산은 평균적으로 O(log n)의 시간 복잡도를 가지게 된다.
이진 탐색 트리의 이러한 특성은 많은 알고리즘과 애플리케이션에서 그 가치를 발휘한다. 이를 이해하고 활용하는 것은 데이터의 효율적인 관리와 알고리즘의 최적화에 있어서 핵심적이다.
종류
- 완전 이진 트리 (Complete Binary Tree): 모든 레벨이 꽉 차 있는 트리. 마지막 레벨만은 꽉 차 있지 않아도 된다.
- 포화 이진 트리 (Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 가진 트리.
- 균형 이진 트리 (Balanced Binary Tree): 모든 리프 노드의 깊이 차이가 1 이하인 트리.
이진 탐색 트리(Binary Search Tree, BST)
정의: 이진 탐색 트리는 이진 트리의 한 종류로, 다음 세 가지 속성을 만족한다.
왼쪽 서브트리의 모든 노드의 값은 현재 노드의 값보다 작아야 한다. 오른쪽 서브트리의 모든 노드의 값은 현재 노드의 값보다 커야 한다. 왼쪽과 오른쪽 서브트리 모두 이진 탐색 트리여야 한다.
장점 탐색, 삽입, 삭제 연산이 평균적으로 O(log n)의 시간 복잡도를 가집니다. 중위 순회(In-order traversal)를 통해 정렬된 순서로 노드를 방문할 수 있다.
단점 트리가 균형을 잃어버리면(예: 한쪽으로 치우친 트리) 연산의 시간 복잡도가 O(n)까지 늘어날 수 있다.
활용 예시
정렬: 이진 탐색 트리는 중위 순회를 통해 정렬된 데이터를 얻을 수 있다. 탐색 연산: 데이터베이스 시스템과 같은 곳에서 탐색 연산의 효율을 높이기 위해 사용됩니다. 밸런스드 트리: AVL 트리나 레드-블랙 트리와 같은 균형 이진 탐색 트리는 트리의 균형을 유지하면서 빠른 연산 속도를 보장합니다.
이진 탐색 트리의 특징
정렬된 데이터 구조: 이진 탐색 트리는 노드를 중위 순회하면 정렬된 데이터를 얻을 수 있다. 동적 크기: 삽입과 삭제 연산을 통해 동적으로 크기를 조절할 수 있다. 탐색 효율성: 균형잡힌 트리에서의 탐색, 삽입, 삭제 연산은 O(log n)의 시간 복잡도를 가집니다. 그러나 최악의 경우(편향된 트리) O(n)의 시간이 걸릴 수 있다.
이진 탐색 트리의 삽입 및 삭제 구현
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.key = key
class BST:
def __init__(self):
self.root = None
# 삽입 메서드
def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self._insert_rec(self.root, key)
def _insert_rec(self, node, key):
if key < node.key:
if node.left is None:
node.left = Node(key)
else:
self._insert_rec(node.left, key)
elif key > node.key:
if node.right is None:
node.right = Node(key)
else:
self._insert_rec(node.right, key)
# 삭제 메서드
def delete(self, key):
self.root = self._delete_rec(self.root, key)
def _delete_rec(self, node, key):
if not node:
return node
# 삭제할 노드를 찾는 과정
if key < node.key:
node.left = self._delete_rec(node.left, key)
elif key > node.key:
node.right = self._delete_rec(node.right, key)
else:
# 자식이 하나 또는 없는 노드를 삭제하는 경우
if not node.left:
return node.right
elif not node.right:
return node.left
# 자식이 두 개인 노드를 삭제하는 경우
node.key = self._min_value_node(node.right).key
node.right = self._delete_rec(node.right, node.key)
return node
def _min_value_node(self, node):
current_node = node
while current_node.left:
current_node = current_node.left
return current_node
위 코드에서는 이진 탐색 트리의 삽입 및 삭제 연산을 수행하는 방법을 보여준다. 이진 탐색 트리의 삭제 연산은 세 가지 경우를 고려해야 한다.
- 삭제할 노드가 자식이 없는 경우
- 삭제할 노드가 하나의 자식만 가지는 경우
- 삭제할 노드가 두 개의 자식을 가지는 경우
마무리
이진 탐색 트리(BST)는 그 구조와 원칙에서 기반한 알고리즘적 특성 때문에 많은 컴퓨터 과학 분야에서 중요하게 여겨진다. 그 자체의 단순한 구조 속에 근본적인 컴퓨팅 원리가 내재되어 있기 때문이다.
BST의 핵심 원칙은 모든 노드에서 왼쪽 하위 트리에는 더 작은 값의 노드만 있고, 오른쪽 하위 트리에는 더 큰 값의 노드만 있어야 한다는 것이다. 이 원칙 덕분에 BST는 많은 연산에서 높은 효율성을 자랑한다. 정렬, 탐색 및 관련 연산이 평균적으로 로그 시간에 수행되는 것은 이러한 구조 덕분이다.
하지만 모든 장점에는 그에 상응하는 단점이 따르곤 한다. BST의 주요 약점 중 하나는 균형이 잘 맞지 않으면 성능이 급격히 떨어진다는 것이다. 이는 트리가 한 쪽으로 치우친 경우 탐색 시간이 선형 시간에 가까워진다는 것을 의미한다. 이러한 문제점을 해결하기 위해 여러 밸런스드 트리 알고리즘이 탄생하게 되었다.
BST를 실생활에서 볼 수 있는 한 예는 데이터베이스의 인덱싱 메커니즘이다. 많은 데이터베이스 시스템들이 효율적인 검색을 위해 내부적으로 밸런스드 트리를 사용한다. 또한, BST는 프로그래밍 대회나 코딩 인터뷰에서 자주 출제되는 주제 중 하나이기도 한다. 이는 BST가 문제 해결에 있어 핵심적인 자료 구조로서의 역할을 담당하기 때문이다.
최종적으로, 이진 탐색 트리는 우리가 데이터를 효율적으로 관리하고 조작할 수 있는 방법 중 하나를 제공한다. 그 구조와 원칙, 그리고 그로 인한 알고리즘적 특성은 컴퓨터 과학의 핵심 개념 중 하나로, 그 중요성을 배울 때마다 깊이 있게 고민하고 이해하는 것이 중요하다. 이해와 활용 능력을 키우는 것은 여러분의 컴퓨터 과학 여정에서 가치 있는 경험을 제공할 것이다.
댓글남기기