Max HBLT에서 임의 노드 삭제란?
Max HBLT(Max Height-Biased Leftist Tree) 또는 Min HBLT에서 임의의 노드를 삭제하는 것은 우선순위 큐(Priority Queue)나 HBLT의 표준 연산은 아닙니다. 하지만 특정 상황에서는 루트가 아닌 임의의 노드 K를 트리에서 제거해야 할 필요가 생길 수 있습니다. 이 경우 다음과 같은 규칙에 따라 삭제 작업을 수행해야 합니다.
임의 노드 삭제 절차
- 서브트리 분리 및 병합(Meld): 노드 K를 루트로 하는 서브트리를 전체 트리에서 분리한 뒤, 그 자리를 노드 K의 두 자식 서브트리를 병합(meld)한 결과로 대체합니다.
- s 값(s-value) 갱신: 노드 K부터 루트까지의 경로에 있는 노드들의 s 값을 갱신하고, 경로상에서 HBLT의 성질이 유지되도록 필요하면 좌우 서브트리를 교환(swap)합니다.
s 값 갱신 과정의 동작 원리
K부터 루트까지 거슬러 올라가며 s 값을 갱신하려면 각 노드가 부모 포인터(parent pointer)를 가지고 있어야 합니다. 갱신 작업은 경로를 따라 올라가다가 s 값이 변하지 않는 노드를 만나는 순간 중단됩니다.
여기서 중요한 특징은, 변경된 s 값들이 반드시 오름차순 증가 수열을 이룬다는 점입니다. HBLT의 정의상 각 노드의 s 값은 자식 노드의 s 값보다 정확히 1만큼 커야 하기 때문입니다.
시간 복잡도 분석
HBLT에서 최대 s 값은 O(log n)이고 모든 s 값은 양수이므로, 갱신 과정에서 거쳐 가는 노드는 최대 O(log n)개로 제한됩니다. 또한 각 노드의 s 값 갱신에는 O(1)의 시간이 소요됩니다.
따라서 Max HBLT에서 임의의 노드 하나를 삭제하는 연산의 전체 시간 복잡도는 O(log n)이 됩니다.