최대 또는 최소 HBLT에서 임의 노드를 삭제하는 것은 표준 작업이 아닙니다. 우선 순위 대기열 또는 HBLT의 경우. HBLT에서 K라는 노드를 삭제하려면 다음 규칙을 따라야 합니다.
-
트리에서 K에 뿌리를 둔 하위 트리를 분리하고 노드 K의 하위 트리의 혼합으로 대체합니다.
-
K에서 루트까지의 경로에서 s 값을 업데이트하고 HBLT의 속성을 유지하기 위해 필요에 따라 이 경로의 하위 트리를 교체합니다.
s 값을 K에서 루트로 업데이트하려면 각 노드에 대한 부모 포인터가 필요합니다. s 값을 위쪽 노드로 업데이트하는 이 작업은 s 값이 변경되지 않은 것을 볼 때 중지됩니다. 변경된 s 값은 오름차순을 형성해야 합니다. 각 노드는 이전 노드보다 하나 더 많아야 하기 때문입니다. 최대 s 값이 O(log n)이고 모든 s 값이 양수이므로 업데이트 단계에서 최대 O(log n) 노드가 발생합니다. 각 노드는 값을 업데이트하기 위해 O(1)을 취합니다. 따라서 임의의 노드를 삭제하는 전체 복잡성은 O(log n)
입니다.