2-3 트리란 무엇인가?
2-3 트리(2-3 Tree)는 균형 잡힌 트리 데이터 구조의 한 종류로, 자식을 가지는 모든 내부 노드(internal node)가 다음 두 형태 중 하나를 만족해야 합니다.
- 2-노드(2-node): 하나의 데이터 요소와 두 개의 자식 노드를 가짐
- 3-노드(3-node): 두 개의 데이터 요소와 세 개의 자식 노드를 가짐
기본 정의
내부 노드가 하나의 데이터 요소와 두 개의 자식을 가지면 이를 2-노드라고 부릅니다.
내부 노드가 두 개의 데이터 요소와 세 개의 자식을 가지면 이를 3-노드라고 부릅니다.
트리 T가 다음 조건 중 하나를 만족할 때, T를 2-3 트리라고 정의합니다.
- T가 비어 있는 경우, 즉 T에 어떠한 노드도 존재하지 않는 경우
- T가 데이터 요소 a를 가진 2-노드이고, 왼쪽 자식 L과 오른쪽 자식 R을 가질 때 다음을 만족하는 경우:
- L과 R은 서로 같은 높이를 가지는 비어 있지 않은 2-3 트리여야 함
- a는 L에 있는 모든 요소보다 커야 함
- a는 R에 있는 모든 데이터 요소보다 작거나 같아야 함
- T가 데이터 요소 a와 b(a < b)를 가진 3-노드이고, 왼쪽 자식 L, 가운데 자식 M, 오른쪽 자식 R을 가질 때 다음을 만족하는 경우:
- L, M, R은 서로 같은 높이를 가지는 비어 있지 않은 2-3 트리여야 함
- a는 L의 모든 데이터 요소보다 크고, M의 모든 데이터 요소보다 작거나 같아야 함
- b는 M의 모든 데이터 요소보다 크고, R의 모든 데이터 요소보다 작거나 같아야 함
2-3 트리의 주요 속성
- 모든 내부 노드는 반드시 2-노드 또는 3-노드입니다.
- 모든 리프(leaf) 노드는 동일한 깊이(레벨)에 위치합니다.
- 모든 데이터는 항상 정렬된 순서로 유지됩니다.
주요 연산
1. 탐색(Searching)
2-3 트리에서 특정 항목을 탐색하는 방법은 이진 탐색 트리(binary search tree)의 탐색 방식과 매우 유사합니다. 각 노드의 데이터 요소는 순서대로 정렬되어 있으므로, 탐색 함수는 올바른 하위 트리(subtree)로 이동하고 최종적으로 해당 항목이 존재하는 노드에 도달하게 됩니다.
탐색 과정을 단계별로 살펴보겠습니다. T를 2-3 트리, d를 찾고자 하는 데이터 요소라고 가정합니다.
- T가 비어 있다면 d는 T에 존재하지 않으며, 탐색은 종료됩니다.
- r을 T의 루트(root) 노드라고 합니다.
- r이 리프 노드라면, r에 d가 없을 경우 d는 T에 존재하지 않는 것이고, r에 d가 있다면 탐색에 성공한 것입니다. 더 이상 추가 단계가 필요하지 않습니다.
- r이 왼쪽 자식 L과 오른쪽 자식 R을 가진 2-노드이고, e를 r의 데이터 요소라고 할 때 다음 세 가지 경우로 나뉩니다:
- d = e인 경우: T에서 d를 찾았으므로 탐색을 종료합니다.
- d < e인 경우: T를 L로 설정하고 2단계로 돌아갑니다.
- d > e인 경우: T를 R로 설정하고 2단계로 돌아갑니다.
- r이 왼쪽 자식 L, 가운데 자식 M, 오른쪽 자식 R을 가진 3-노드이고, a와 b(r의 두 데이터 요소, a < b)라고 할 때 다음 네 가지 경우로 나뉩니다:
- d = a 또는 d = b인 경우: d는 T에 존재하므로 탐색을 종료합니다.
- d < a인 경우: T를 L로 설정하고 2단계로 돌아갑니다.
- a < d < b인 경우: T를 M으로 설정하고 2단계로 돌아갑니다.
- d > b인 경우: T를 R로 설정하고 2단계로 돌아갑니다.
2. 삽입(Insertion)
삽입 연산은 먼저 키(key)가 들어갈 적절한 위치를 탐색한 후, 그 자리에 새 키를 추가하는 방식으로 수행됩니다. 삽입 후 노드가 4-노드가 되면, 해당 노드는 두 개의 2-노드로 분할되고 가운데 키는 부모 노드로 올려집니다. 이때 부모 노드 역시 4-노드가 될 수 있으며, 그런 경우 부모 노드도 분할되어 키를 상위 부모로 전파(propagation)합니다.
이 과정은 다음 중 하나가 발생할 때까지 반복됩니다.
- 분할이 필요 없는 2-노드인 부모에 도달한 경우
- 루트에 도달한 경우 — 전파된 요소를 사용하여 새로운 2-노드 루트를 생성합니다.
이 알고리즘을 사용하면 수행해야 하는 연산 횟수는 트리의 높이에 비례합니다. 2-3 트리는 완벽하게 균형 잡혀 있으므로, 연산 복잡도는 로그 시간(logarithmic time)이 됩니다. 또한 이 과정은 결과물이 항상 유효한 2-3 트리임을 보장하며, 특히 모든 리프 노드는 동일한 깊이를 유지하게 됩니다.
아래 다이어그램은 이 과정에서 발생할 수 있는 경우들을 보여줍니다.
위 그림은 2-3 트리에 숫자를 삽입할 때 발생할 수 있는 세 가지 경우를 나타냅니다.