データ構造におけるMax-WBLT（重み偏左木）の操作を徹底解説

Max-WBLTとは

WBLT（Weight-Biased Leftist Tree：重み偏左木）は、優先度付きキューの実装に用いられるヒープ構造の一種です。本記事では、Max-WBLTにおける各種操作について詳しく解説します。

HBLT（Height-Biased Leftist Tree：高さ偏左木）には、挿入（insert）、削除（delete）、初期化などの操作が存在しますが、これらはWBLTにもほぼ同様の形で適用できます。ただし、両者で大きく異なるのはmeld（併合）操作です。WBLTでは、meld操作をトップダウンの1回の走査で完了できるという大きな特徴があります。

1回のパスで実現できるmeld操作

WBLTにおいてmeld操作が単一パスで実現できる理由は、木を下降しながら各ノードのw値（部分木のノード数）を求められる点にあります。下降途中でw値を更新し、必要に応じて部分木の交換（スワップ）を行うことで、一度の走査だけで併合処理が完了します。

一方、HBLTの場合、s値（ノードから外部ノードまでの最短距離）は下降しながら求めることができません。そのため、HBLTのmeld操作にはボトムアップの処理が必要となり、WBLTほど効率的ではありません。

挿入・削除の効率性

meld操作がトップダウンの1回のパスで行えるため、WBLTでは挿入や削除も効率的に実行できます。具体的には、HBLTと比較して定数倍高速になるという利点があります。

任意位置ノード削除の制約

ただし、WBLTには注意すべき制約も存在します。木の中の任意の位置にあるノードKの要素をO(log n)時間で削除することはできません。その理由は、ノードKがO(n)個の祖先を持つ可能性があり、削除時にはそれらすべての祖先ノードのw値を更新する必要があるためです。

この制約により、WBLTはマージ可能な両端優先度キュー（mergeable double-ended priority queue）のような用途には適していません。このような要件がある場合は、別のデータ構造を検討する必要があります。