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

데이터 구조의 최대 WBLT 연산


여기에서 다양한 Max-WBLT 작업이 무엇인지 확인할 수 있습니다. HBLT에는 삽입, 삭제 및 초기화와 같은 다양한 작업이 있습니다. 그들은 또한 WBLT와 매우 유사합니다. 그러나 단일 위에서 아래로 통과하는 병합 작업을 수행할 수 있습니다.

WBLT에 대해 단일 패스 멜드 작업이 가능합니다. 내려가는 길에 w 값을 찾을 수 있기 때문입니다. 필요에 따라 w 값을 업데이트하고 하위 트리를 교체할 수 있습니다. HBLT의 경우 트리로 내려가는 도중에 s 값을 찾을 수 없습니다.

단일 위에서 아래로 병합이 수행될 수 있으므로 삽입 및 삭제도 효율적으로 수행할 수 있습니다. 따라서 삽입 및 삭제는 일정한 요소에 의해 더 빠릅니다. 여기서 O(log n) 시간에 임의로 위치한 노드 K의 요소를 삭제할 수 없습니다. 그 이면에 있는 이유는 노드 K에 w 값이 업데이트될 O(n) 조상이 있을 수 있기 때문입니다. 따라서 병합 가능한 이중 종료 우선 순위 대기열 응용 프로그램에는 적합하지 않습니다.