Max HBLT에서의 최댓값 삭제 원리
Max HBLT(Height-Biased Leftist Tree, 높이 편향 좌편향 트리)에서는 트리 전체에서 가장 큰 값인 최댓값(max element)이 항상 루트(root)에 위치합니다. 이러한 구조적 특성 덕분에 최댓값을 삭제하는 작업은 매우 효율적으로 처리할 수 있습니다.
삭제 과정
최댓값을 삭제한다는 것은 곧 루트 노드를 제거하는 것을 의미합니다. 루트가 삭제되면 기존의 하나였던 트리가 왼쪽 서브트리와 오른쪽 서브트리라는 두 개의 독립적인 Max HBLT로 분리됩니다.
이때 분리된 두 개의 Max HBLT를 meld(병합) 연산으로 다시 하나로 합칩니다. meld 연산은 두 개의 HBLT를 입력으로 받아 하나의 유효한 Max HBLT를 반환하는 핵심 연산입니다.
연산 결과와 복잡도
병합이 완료되면 삭제된 최댓값을 제외한 나머지 모든 요소들이 하나의 Max HBLT 안에 그대로 유지됩니다. 즉, 삭제 연산은 다음 세 단계로 요약할 수 있습니다.
1. 루트(최댓값) 제거
2. 왼쪽·오른쪽 서브트리 분리
3. 두 서브트리를 meld로 재병합
전체 수행 시간은 meld 연산에 의해 결정되며, 시간 복잡도는 O(log n)입니다.