資料結構中的最大 WBLT 操作

這裡將介紹不同的 Max-WBLT 操作。HBLT 具有插入、刪除和初始化等不同操作。它們與 WBLT 也相當相似。然而，合併操作可以單次從上到下透過完成。

單次透過合併操作在 WBLT 中是可能的。因為我們可以沿途找到 w 值。我們可以更新 w 值並根據需要交換子樹。在 HBLT 中，我們無法沿途找到進入樹的 s 值。

由於合併可以單次從上到下透過完成，那麼插入和刪除也可以高效地執行。因此插入和刪除更快，透過一個常數因子。在這裡，我們無法在 O(log n) 時間內刪除位於任意定位節點 K 中的元素。其背後的原因是節點 K 可能有 O(n) 個祖先，它們的 w 值將被更新。因此這不適用於可合併雙端優先佇列應用。

阿納布·查克拉博蒂

更新於：2020-08-11

163 次瀏覽

開啟您的職業生涯

完成課程後獲得認證

開始