レベルリンク付き(2,4)木：データ構造における効率的な指探索の実現

本記事では、レベルリンク(level links)の導入によって(2,4)木がどのように効率的な指探索(finger search)を実現できるのかを解説します。ここで説明する考え方は、b ≥ 2a を満たす、より一般的な高さ平衡木である(a,b)木のクラスにもそのまま適用できます。

(2,4)木の基本性質

(2,4)木とは、すべての葉が同じ深さを持ち、すべての内部ノードの次数(子の数)が2、3、4のいずれかである高さ平衡探索木として定義されます。要素は葉に格納され、内部ノードには探索を導くためのキーのみが格納されます。各内部ノードの次数が2以上であるため、(2,4)木の高さは O(log n) に収まり、探索は O(log n) 時間で実行できます。

(2,4)木の重要な性質として、指(finger)で指定した位置への挿入と削除が償却 O(1) 時間で行えることが挙げられます(この性質は(2,3)木にはありません。(2,3)木では、Θ(m log m) 時間を要する m 回の挿入・削除列が存在します)。さらに、m 個の葉を持つ(2,4)木は、大きさ m1 と m2 の2つの木へ償却 O(log min(m1, m2)) 時間で分割できます。同様に、大きさ m1 と m2 の2つの(2,4)木も、償却 O(log min(m1, m2)) 時間で連結(結合)できます。

レベルリンクによる拡張

指探索をサポートするために、(2,4)木にはレベルリンクが追加されます。これは、同じ深さを持つすべてのノードを双方向連結リストでつなぐ仕組みです。次の図は、レベルリンクで拡張された(2,4)木を示しています。すべての辺が双方向のリンクを表すことに注意してください。追加されたレベルリンクは、(2,4)木の挿入・削除・分割・結合の各操作の間も容易に維持できます。

指探索の手順

X から Y への指探索を行うには、まず Y が X の左側にあるか右側にあるかを判定します。ここでは一般性を失うことなく、Y が X の右側にあると仮定します。次に、X から根へ向かう経路を辿りながら、経路上のノード V とその右隣のノードを調べ、Y が V を根とする部分木、あるいは V の右隣のノードを根とする部分木に含まれることが確定するまで探索を続けます。その時点で上向きの探索を終了し、V および/または V の右隣のノードから、Y を目標とする下向きの探索を最大2回開始します。図1では、j から t への指探索の際に辿られるポインタが太線で示されています。

探索時間 O(log d) の根拠

O(log d) の探索時間は、次の観察から導かれます。上向きの探索をノード V からその親へ進めるとき、Y は V の右隣のノードの最左部分木よりも右側に存在することが分かります。つまり、d はそれまでに到達した高さに対して少なくとも指数関数的に大きくなります。

図1では、ノード「q r」を根とする部分木より右側に Y が存在することが「s」の位置から分かるため、内部ノード「l n」からノード「h」へと探索を進めています。

外部記憶への拡張

レベルリンク付き(2,4)木の構成は、外部記憶(external memory)上に実装可能なレベルリンク付き(a,b)木へと直接一般化できます。内部ノードが外部記憶の1ブロックに収まるように b = 2a となる a と b を選ぶことで、挿入と削除を O(1) 回のメモリ転送で、指探索を O(log_b n) 回のメモリ転送で実現する、外部記憶向けの指探索木が得られます。