이번 글에서는 최대 WBLT(Max Weight-Biased Leftist Tree)에서 사용되는 다양한 연산들을 자세히 살펴보겠습니다.
HBLT와 WBLT의 관계
HBLT(Height-Biased Leftist Tree, 높이 편향 좌측 트리)에는 삽입(insert), 삭제(delete), 초기화(initialization)와 같은 여러 연산이 존재합니다. 흥미로운 점은 이러한 연산들이 WBLT(Weight-Biased Leftist Tree, 가중 편향 좌측 트리)에서도 거의 동일한 방식으로 적용된다는 것입니다.
단일 패스(Single-Pass) 병합(Meld) 연산
WBLT의 가장 큰 장점 중 하나는 병합(meld) 연산을 위에서 아래로(top-to-bottom) 내려가는 단일 패스만으로 수행할 수 있다는 점입니다.
그 이유는 다음과 같습니다. WBLT에서는 트리를 따라 내려가는 도중에 각 노드의 w 값(weight 값, 즉 서브트리의 노드 개수)을 바로 계산할 수 있습니다. 따라서 내려가면서 w 값을 즉시 갱신하고, 필요하다면 두 서브트리를 교환(swap)하는 작업도 함께 처리할 수 있습니다.
반면 HBLT의 경우, 트리를 아래로 내려가는 과정에서 s 값(shortest 값, 외부 노드까지의 최단 경로 길이)을 미리 알 수 없습니다. s 값은 올라오는 과정에서야 정확히 계산되기 때문에, HBLT의 병합 연산은 일반적으로 위에서 아래로 내려간 뒤 다시 되돌아오는 방식으로 진행됩니다.
효율적인 삽입과 삭제
병합 연산이 단일 패스로 가능하기 때문에, WBLT에서는 삽입(insert)과 삭제(delete) 역시 효율적으로 수행할 수 있습니다. 삽입은 새로운 원소를 하나의 노드로 보고 병합하면 되고, 삭제는 루트를 제거한 후 남은 두 서브트리를 병합하면 됩니다.
특히 WBLT의 삽입과 삭제는 HBLT에 비해 상수 배(constant factor)만큼 더 빠릅니다. 이는 병합 과정에서 불필요한 되돌아가기(backtracking) 작업이 없기 때문입니다.
임의 위치 노드 삭제의 한계
다만 WBLT에도 분명한 한계가 존재합니다. 트리 내 임의의 위치에 있는 노드 K의 원소를 O(log n) 시간 안에 삭제하는 것은 불가능합니다.
그 이유는 노드 K가 최악의 경우 O(n)개에 달하는 조상(ancestor) 노드들을 가질 수 있고, 삭제 시 이 조상들의 w 값을 모두 갱신해 주어야 하기 때문입니다. 조상 노드의 w 값이 변경되지 않으면 트리의 균형 정보가 깨져 WBLT의 성질이 유지되지 않습니다.
따라서 WBLT는 임의 노드의 삭제가 빈번하게 발생하는 환경에는 적합하지 않으며, 특히 병합 가능한 양방향 우선순위 큐(mergeable double-ended priority queue)와 같은 응용 분야에서는 주의해서 사용해야 합니다.
정리
최대 WBLT는 단일 패스 병합 연산 덕분에 삽입과 삭제가 상수 배 빠르다는 강력한 장점을 지니지만, 임의 위치 노드 삭제 시 O(n)개의 조상 w 값 갱신 문제로 인해 특정 응용 분야에서는 제약이 있습니다. 자료구조를 선택할 때는 이러한 특성을 잘 고려하는 것이 중요합니다.