データ構造の高さ平衡左偏木（HBLT）とは？定義とs値の計算方法を解説

高さ平衡左偏木（HBLT）とは

本記事では、データ構造の一つである高さ平衡左偏木（Height Balanced Leftist Tree：HBLT）について詳しく解説します。

外部ノードと拡張二分木

まず、空の部分木を外部ノード（external node）と呼ばれる特殊なノードで置き換えた二分木を考えてみましょう。外部ノード以外のすべてのノードは内部ノード（internal node）と呼ばれます。このように、既存の二分木に外部ノードを追加して完成させた木を拡張二分木（extended binary tree）といいます。

この木から葉につながる辺を取り除いて考えると、それが元々の二分木に相当し、外部ノードを含めた全体が拡張二分木となります。

s値の定義

次に、s(x) を「ノード x から、その部分木内にある外部ノードまでの最短経路の長さ」と定義します。

• x が外部ノードの場合：s(x) = 0
• x が内部ノードの場合：s(x) = min{s(L), s(R)} + 1

min{𝑠(𝐿), 𝑠(𝑅)} + 1

ここで、L と R はそれぞれノード x の左の子と右の子を表します。以下の図は、実際の木における s 値の計算例です。

HBLT の定義

HBLT の定義は次のとおりです。

ある二分木が高さ平衡左偏木（HBLT）であるのは、すべての内部ノードにおいて、左の子の s 値が右の子の s 値以上であるとき、かつそのときに限る。

先ほど示した木は HBLT ではありません。ノード a の親に注目すると、s(L) = 0、s(R) = 1 となっており、このノードだけが HBLT の条件を満たしていないためです。そこで、このノードの左右の部分木を入れ替えることで、木全体を HBLT に変換できます。

最大木・最小木との関係

HBLT に関連するその他の重要な定義を紹介します。

• 最大木（max tree）／最小木（min tree）：各ノードの値が、その子の値以上（最大木の場合）、または以下（最小木の場合）であるような木を指します。

• 最大 HBLT：最大木でもある HBLT。最小 HBLT：最小木でもある HBLT を意味します。

これらの構造は、マージ（併合）操作を効率的に実行できるヒープの一種として知られており、優先度付きキューの実装などに幅広く応用されています。