높이 균형 좌향 트리(Height Balanced Leftist Tree)란?
이번 글에서는 높이 균형 좌향 트리(HBLT, Height Balanced Leftist Tree)가 무엇인지 자세히 살펴보겠습니다. HBLT를 이해하려면 먼저 확장 이진 트리(Extended Binary Tree)라는 개념부터 알아야 합니다.
확장 이진 트리와 외부 노드
이진 트리에서 비어 있는 모든 서브트리 자리를 외부 노드(External Node)라 불리는 특수한 노드로 대체한다고 가정해 봅시다. 그리고 외부 노드를 제외한 나머지 모든 노드를 내부 노드(Internal Node)라고 부릅니다. 이처럼 기존 이진 트리에 외부 노드들을 추가한 트리를 확장 이진 트리라고 합니다.
위 그림에서 잎(leaf)에 해당하는 외부 노드들의 간선을 제외하고 보면, 그것이 실제 원래의 이진 트리입니다. 반대로 외부 노드까지 모두 포함한 트리가 바로 확장 이진 트리입니다.
s(x) 값의 정의
이제 노드 x에서 그 서브트리 내의 외부 노드까지 이르는 가장 짧은 경로의 길이를 s(x)라고 정의합니다.
- x가 외부 노드인 경우: s(x) = 0
- x가 내부 노드인 경우: 아래 수식으로 계산
min{𝑠(𝐿), 𝑠(𝑅)} + 1여기서 L과 R은 각각 노드 x의 왼쪽 자식과 오른쪽 자식을 의미합니다. 즉, 내부 노드의 s 값은 두 자식 노드의 s 값 중 더 작은 값에 1을 더한 것입니다. 다음 그림은 주어진 트리의 s 값을 나타낸 것입니다.
HBLT의 정의
높이 균형 좌향 트리(HBLT)는 다음 조건을 만족하는 이진 트리입니다.
모든 내부 노드에서 왼쪽 자식의 s 값이 오른쪽 자식의 s 값보다 크거나 같아야 한다. 즉, s(L) ≥ s(R)
앞서 본 트리를 확인해 보면 이 트리는 HBLT가 아닙니다. 노드 a의 부모 노드만 s(L) = 0, s(R) = 1로 조건을 위반하고 있으며, 나머지 모든 노드는 HBLT의 규칙을 만족합니다. 따라서 해당 노드의 왼쪽 서브트리와 오른쪽 서브트리를 서로 교환하면 이 트리를 HBLT로 만들 수 있습니다.
맥스트리(Max Tree)와 민트리(Min Tree)
HBLT와 함께 알아두면 좋은 추가적인 정의는 다음과 같습니다.
- 맥스트리(Max Tree): 모든 노드의 값이 자식 노드의 값보다 크거나 같은 트리입니다.
- 민트리(Min Tree): 모든 노드의 값이 자식 노드의 값보다 작거나 같은 트리입니다.
이를 HBLT와 결합하면 다음과 같이 정의할 수 있습니다.
- 맥스 HBLT(Max HBLT): 맥스트리의 성질을 동시에 만족하는 HBLT
- 민 HBLT(Min HBLT): 민트리의 성질을 동시에 만족하는 HBLT
이러한 구조는 우선순위 큐(Priority Queue)를 효율적으로 구현하는 데 활용되며, 두 트리를 빠르게 병합(meld)할 수 있다는 점이 좌향 트리의 가장 큰 장점 중 하나입니다.