从数据结构中的最大HBLT中删除任意元素

从“最大”或“最小” HBLT中删除任意节点不是标准操作。优先队列或HBLT。如果要从HBLT中删除一个节点,例如K,则必须遵循以下规则。

  • 从树上分离以K为根的子树,并将其替换为节点K子树的融合体。

  • 从K到根的路径更新s的值,并根据需要交换此路径上的子树以维护HBLT的属性。

要将s的值从K更新为根,我们需要每个节点的父指针。当我们看到s值未更改时,将s值更新为向上节点的操作将停止。更改后的s值必须形成一个升序。因为每个节点必须比前一个多一个。由于max s的值为O(log n),并且所有s值为正,因此在更新过程中会遇到最大O(log n)节点。每个节点取O(1)来更新值。因此,删除任意节点的总体复杂度为O(log n)