2-3 트리(2-3 Tree)는 트리를 구성하는 모든 노드가 2-노드 또는 3-노드로 이루어진 자료구조입니다. 2-3 트리는 차수(order)가 3인 특수한 형태의 B-트리(B-Tree)로 분류됩니다.
여기서 각 노드의 의미는 다음과 같습니다.
- 2-노드: 데이터 값을 하나만 가지며, 두 개의 자식 노드를 갖습니다.
- 3-노드: 데이터 값을 두 개 가지며, 세 개의 자식 노드를 갖습니다.
2-3 트리의 주요 속성
- 모든 내부 노드(internal node)는 반드시 2-노드 또는 3-노드입니다.
- 데이터를 하나만 가진 노드는 정확히 두 개의 자식을 가진 2-노드이거나, 자식이 없는 리프 노드일 수 있습니다.
- 데이터를 두 개 가진 노드는 반드시 정확히 세 개의 자식을 가진 3-노드여야 합니다.
- 모든 리프 노드는 항상 동일한 깊이(레벨)에 위치합니다.
- 2-3 트리는 항상 높이 균형(height-balanced) 트리를 유지합니다.
- 데이터가 정렬된 상태로 유지되므로 탐색 연산이 빠르고 효율적입니다.
2-노드(2 Node)의 구조
- 정확히 두 개의 자식 노드를 가집니다.
- 왼쪽 자식은 부모의 데이터 값보다 작은 값을 가집니다.
- 오른쪽 자식은 부모의 데이터 값보다 큰 값을 가집니다.
- 자식이 없는 리프 노드일 수도 있습니다.
3-노드(3 Node)의 구조
- 정확히 세 개의 자식 노드를 가집니다.
- 두 개의 데이터 값을 가집니다.
- 왼쪽 자식은 왼쪽 데이터 값보다 작은 값을 가집니다.
- 중간 자식은 두 데이터 값 사이의 값을 가집니다.
- 오른쪽 자식은 오른쪽 데이터 값보다 큰 값을 가집니다.
- 절대 리프 노드가 될 수 없습니다.
2-3 트리의 주요 연산
1. 탐색(Search)
2-3 트리의 탐색은 데이터가 항상 정렬되어 있기 때문에 이진 탐색 트리(Binary Search Tree)의 탐색 방식과 매우 유사합니다. 트리에서 값 X를 찾는 과정은 다음과 같습니다.
- 트리가 비어 있으면 → 탐색 실패(False)를 반환합니다.
- 리프 노드까지 내려갔는데도 찾지 못하면 → 탐색 실패(False)를 반환합니다.
- X가 노드의 왼쪽 데이터 값보다 작으면 → 왼쪽 서브트리를 탐색합니다.
- X가 왼쪽 데이터 값보다 크고 오른쪽 데이터 값보다 작으면 → 중간 서브트리를 탐색합니다.
- X가 오른쪽 데이터 값보다 크면 → 오른쪽 서브트리를 탐색합니다.
2. 삽입(Insertion)
2-3 트리에 값 X를 삽입하는 과정은 다음과 같습니다.
- 트리가 비어 있으면 → X를 루트 노드로 추가합니다.
- X가 들어갈 올바른 위치를 탐색한 후, 해당 위치의 리프 노드에 추가합니다.
- 리프 노드에 데이터가 하나뿐이라면 → X를 함께 넣어 해당 노드를 2-노드로 만듭니다.
- 리프 노드에 이미 데이터가 두 개 있다면 → X를 임시로 추가한 뒤 3-노드를 분할(split)하고, 정렬 순서에 맞게 데이터를 부모 노드로 이동시킵니다.
예제: 빈 2-3 트리에 다음 순서대로 노드를 삽입해 보겠습니다 → 10, 5, 8, 15, 23, 21
3. 삭제(Deletion)
2-3 트리에서 값 X를 삭제하는 과정은 다음과 같습니다.
- 트리가 비어 있으면 → 삭제 실패(False)를 반환합니다.
- X의 위치를 탐색하여 삭제한 후, 트리의 균형을 다시 조정합니다.
- X가 3-노드에 속해 있는 경우 → X를 삭제한 뒤 남은 데이터 값들을 재배치하고, 필요하다면 조상 노드의 데이터 값도 함께 조정합니다.
- X가 2-노드에 속해 있는 경우 → 트리를 재귀적으로 조정하고 병합·분석하면서 노드들이 항상 정렬된 순서를 유지하도록 재구성합니다.
마무리
2-3 트리는 삽입과 삭제가 일어나도 스스로 균형을 유지하기 때문에 최악의 경우에도 O(log n)의 탐색 성능을 보장합니다. 이러한 특성 덕분에 2-3 트리는 B-트리, B+ 트리 등 실무에서 활용되는 다양한 균형 트리 자료구조의 이론적 기반이 됩니다.