数据结构中的最大 WBLT 操作

这里将介绍不同的 Max-WBLT 操作。HBLT 具有插入、删除和初始化等不同操作。它们与 WBLT 也相当相似。然而，合并操作可以单次从上到下通过完成。

单次通过合并操作在 WBLT 中是可能的。因为我们可以沿途找到 w 值。我们可以更新 w 值并根据需要交换子树。在 HBLT 中，我们无法沿途找到进入树的 s 值。

由于合并可以单次从上到下通过完成，那么插入和删除也可以高效地执行。因此插入和删除更快，通过一个常数因子。在这里，我们无法在 O(log n) 时间内删除位于任意定位节点 K 中的元素。其背后的原因是节点 K 可能有 O(n) 个祖先，它们的 w 值将被更新。因此这不适用于可合并双端优先队列应用。

阿纳布·查克拉博蒂

更新于：2020-08-11

163 次浏览

开启您的职业生涯

完成课程后获得认证

开始