Self-Adjusting Binary Search Trees(1985)
August 12, 2023Self-Adjusting Binary Search Treeは、スプレー木といい、ノードを参照するたびに、ノードを木のルートに移動させる抽象データ構造である。 参照、挿入、削除の償却時間計算量は、ノード数\(n\)の木であれば\(\log(n)\)である。 さらに、十分な数の参照にかかる時間計算量は、その参照の系列に最適化された二分探索木の計算量の定数倍におさまる。
スプレーは、アクセスした直後のノードをルートに移動する再帰的な操作である。
ノードがルートの子であれば両者を結ぶ辺を回転するだけでいい。
親がルートではなく、ノードも親も左側または右側の子であれば、親と祖父母の辺を回転した後に、ノードと親の辺を回転する。
ノードと親の左右が違えば、ノードと親の辺を回転し、ノードとノードの新しい親の辺を回転する。
以上の手続きを参照されたノードがルートに到達するまでくりかえす。
以下の図は、ノードxにスプレーを適用する様子である。
ノードの追加や削除はスプレーによって実装できる。
ノードを挿入する場合、ノードが挿入されるべき位置を特定し、その位置にノードを追加し、最後に追加したノードにスプレーを適用する。
削除の場合、まず、削除対象のノードを特定し、ノードの左の子以下にある最大のノードにスプレーを適用し、新しく左の子となった最大のノードが右の子を持たないようにする。
次に、削除対象であるノードの右の子を左の子の右に配置する。
最後に、削除対象のノードを除外し、削除したノードの左の子を削除したノードの位置に移動する。
以下の図は、80を挿入し、30を削除する様子である。
論文から図を引用しました。