データ構造入門：2つの最大HBLT（高さ優先左分木）を融合するアルゴリズム

HBLT（Height-Biased Leftist Tree、高さ優先左分木）同士の融合（meld）は、再帰を用いることで簡潔かつ効率的に実装できます。ここでは、融合対象となる2つの最大HBLTをAとBとして、その手順を解説します。

融合の基本戦略

まず、どちらか一方が空である場合は、空でないもう一方をそのまま結果として返すだけで処理は完了します。両方が空でない場合は、それぞれの根（ルート）が保持する要素を比較します。そして、より大きい要素を持つ根が、融合後のHBLTの根となります。

Aの根の方が大きいと仮定しましょう。Aの左部分木をLとし、Aの右部分木とBを融合した結果得られる最大HBLTをCとします。このとき、最終的なHBLTは「Aを根とし、LとCをその部分木とする木」になります。

s値の比較と子の入れ替え

ここで重要になるのがs値（各ノードから最も近い外部ノードまでの最短距離）の比較です。Lのs値がCのs値よりも小さい場合は、Cを左部分木とします。そうでなければ、Lがそのまま左部分木となります。この入れ替えにより、「左側のs値が常に右側のs値以上」というHBLTの本質的な性質が保たれるのです。

具体例1：単純な融合

以下のような2つのHBLTを例に考えてみます。

ノード内の数値は要素の値を表し、ノード外側の数値は対応するノードのs値を示しています。それでは、この2つの木を融合してみましょう。

まず、7を9の右の子として一時的に追加することを考えます。しかし、9の左部分木のs値 s(L) は0、右部分木のs値 s(R) は1となっており、左のs値が右より小さいためHBLTの性質に違反しています。そこで左右の子を入れ替え、7を9の右の子として配置し直します。

具体例2：性質違反の検出と修正

続いて、もう少し複雑なケースを見てみましょう。

別の例：

まず、小さい方のHBLTを、大きい方のHBLTの右側に一時的に追加します。

しかしこの状態では、HBLTが満たすべき「左側のs値 ≥ 右側のs値」という性質が崩れてしまっています。

そこで、性質に違反しているノードに対して子の入れ替えを行い、必要に応じて親へ遡りながら再帰的に修正を加えます。こうして得られるのが、正しい性質を備えた最大HBLTです。

まとめ

最大HBLTの融合は、①根の要素を比較して大きい方を新しい根とする、②小さい方を大きい方の右部分木と再帰的に融合する、③s値の条件に反する箇所があれば子を入れ替える、という流れで実現できます。木の高さに比例した処理のみで済むため、融合操作はO(log n)の時間計算量で効率的に実行できる点が大きな特徴です。