가중치 편향 좌파 트리(Weight Biased Leftist Tree, WBLT)는 좌파 트리(Leftist Tree)의 또 다른 변형입니다. 일반적인 좌파 트리가 루트에서 외부 노드(external node)까지의 최단 경로 길이를 기준으로 삼는 것과 달리, WBLT는 서브트리에 포함된 노드의 개수를 기준으로 사용한다는 점이 특징입니다.
노드 가중치 w(x)의 정의
WBLT에서는 노드 x의 가중치(weight) w(x)를 다음과 같이 정의합니다.
- w(x): 노드 x를 루트로 하는 서브트리에 포함된 내부 노드(internal node)의 개수
- x가 외부 노드라면 가중치는 0입니다.
- x가 내부 노드라면 가중치는 두 자식 노드의 가중치 합보다 1만큼 큽니다. 즉, w(x) = w(왼쪽 자식) + w(오른쪽 자식) + 1 입니다.
가중치 계산 예시
다음과 같은 이진 트리가 있다고 가정해 보겠습니다.
각 노드에 대해 w(x) 값을 계산하면 아래 그림과 같이 나타납니다.
외부 노드의 가중치는 0이며, 각 내부 노드의 가중치는 자식 노드들의 가중치를 모두 더한 값에 1을 더한 것임을 확인할 수 있습니다.
가중치 편향 좌파 트리(WBLT)의 정의
이진 트리가 가중치 편향 좌파 트리(WBLT)가 되기 위한 필요충분조건은 다음과 같습니다.
모든 내부 노드에서 왼쪽 자식의 w(x) 값이 오른쪽 자식의 w(x) 값보다 크거나 같아야 한다.
즉, 어떤 내부 노드에서든 w(왼쪽 자식) ≥ w(오른쪽 자식)가 항상 성립해야 한다는 의미입니다.
여기에 힙(heap)의 성질을 결합하면 두 종류의 WBLT를 구분할 수 있습니다.
- 최대 WBLT(Max WBLT): WBLT의 조건을 만족하면서 동시에 최대 트리(max tree), 즉 부모 노드의 값이 자식 노드의 값보다 크거나 같은 트리
- 최소 WBLT(Min WBLT): WBLT의 조건을 만족하면서 동시에 최소 트리(min tree), 즉 부모 노드의 값이 자식 노드의 값보다 작거나 같은 트리
이러한 구조적 특성 덕분에 WBLT는 우선순위 큐(priority queue) 구현이나 두 힙을 빠르게 병합(merge)하는 연산 등에 활용될 수 있습니다.