Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조의 Max HBLT에서 임의 요소 삭제


최대 또는 최소 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)

입니다.