平衡木のお話です。二分木は左右の部分木のバランスが崩れると、性能が劣化する欠点があります。極端な例ですが、ソートされたデータを二分木に挿入していくと、データは右側の木にしか挿入されず、連結リストと同じ線形探索になってしまいます。
これを補うために、木のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは、AVL 木、2 色 (赤黒) 木、2-3 木、B 木、B* 木などがあります。AVL 木と 2 色木は二分木ですが、2-3 木、B 木、B* 木は多分木です。
AVL 木と 2 色木は、木のバランスをチェックするための情報を節 (node) に付加し、バランスが崩れたら一定の範囲に収まるように木を修正します。これに対し、1985 年に Sleater と Tarjan が提案したスプレイ木 (Splay Tree) はちょっと変わっています。
スプレイ木は二分木と同じ構造なので、通常の操作（探索、挿入、削除など）は二分木と同様に行うことができます。スプレイ木の特徴は、このあとに行う操作にあります。スプレイ木はアクセスした節を木の根（ルート）に移動します。この方法を Move to Root といいます。MTF (Move to Front) 法の二分木バージョンと考えてください。これにより、頻繁にアクセスする節（データ）ほど木の浅いところに集まるので、平均探索時間を短くすることができます。
Move to Root は木の回転操作で簡単に実現することができます。しかしながら、この方法では木のバランスをとることはできません。そこで、スプレイ木は節をルートへ移動するときに独自の操作を行います。これを Splay 操作といいます。Splay 操作には zig, zig - zig, zig - zag という 3 つの基本操作があり、木の形状によって適用する操作が決まります。スプレイ木の場合、AVL 木や 2 色木のように、木のバランスをチェックするための情報を節に付加する必要はありません。
そのかわり、スプレイ木の高さが一定の範囲内に収まることは保証されていません。データにアクセスする順番によっては、木のバランスが大きく崩れることがあるのです。もしそうなったとしても、その後のデータアクセスによって、スプレイ木はバランスを回復することが可能です。
このように、スプレイ木は通常の操作のあとに Splay 操作を行うことで、一時的に木のバランスが崩れることがあっても、トータルとして考えると木のバランスを保つように動作します。このため、スプレイ木は「自己調整二分木」と呼ばれています。
スプレイ木の Splay 操作は、二分木の回転操作が基本になります。回転操作は拙作のページ Common Lisp 入門：番外編 の 2 色木 (1) をお読みください。
Splay 操作は二分木の回転操作を組み合わせたものです。Splay 操作は、次に示す 3 通りの方法があります。
最初に zig から説明します。次の図を見てください。
Ｙ Ｘ
／ ＼ zig ／ ＼
Ｘ Ｃ ──→ Ａ Ｙ
／ ＼ ／ ＼
Ａ Ｂ Ｂ Ｃ
図：zig
zig は節 X をルート方向へ一つ移動する操作です。これは回転操作と全く同じです。
次は zig - zig を説明します。次の図を見てください。
Ｚ Ｙ Ｘ
／ ＼ ／ ＼ ／ ＼
Ｙ Ｄ zig ／ ＼ zig Ａ Ｙ
／ ＼ ──→ Ｘ Ｚ ──→ ／ ＼
Ｘ Ｃ ／ ＼ ／ ＼ Ｂ Ｚ
／ ＼ Ａ Ｂ Ｃ Ｄ ／ ＼
Ａ Ｂ Ｃ Ｄ
図：zig - zig
zig - zig は節 X をルート方向へ二つ移動する操作です。X が Z の左部分木にある場合、X < Y < Z であれば zig - zig を適用します。Y < X < Z であれば、次に説明する zig - zag を適用します。zig - zig の特徴は回転操作を適用する順番です。最初に Z を zig で回転し、次に Y を zig で回転します。最初に Y を回転してから Z を回転すると Splay 操作にはなりません。ご注意ください。
最後に zig - zag を説明します。次の図を見てください。
Ｚ Ｚ Ｘ
／ ＼ ／ ＼ ／ ＼
Ｙ Ｄ zig Ｘ Ｄ zag ／ ＼
／ ＼ ──→ ／ ＼ ──→ Ｙ Ｚ
Ａ Ｘ Ｙ Ｃ ／ ＼ ／ ＼
／ ＼ ／ ＼ Ａ Ｂ Ｃ Ｄ
Ｂ Ｃ Ａ Ｂ
図：zig - zag
zig - zag も節 X をルート方向へ二つ移動する操作です。X が Z の左部分木にある場合、Y < X < Z であれば zig - zag を適用します。zig - zag は zig - zig とは違って、X の親節 Y を回転してから Z を回転します。zig - zig とは回転操作を適用する順番が異なることに注意してください。
Splay 操作は zig, zig - zig, zig - zag 操作を適用して、アクセスした節をルートまで移動 (Move to Root) する操作です。Move to Root は回転操作だけでも実現することができます。実際、アクセスした節の親節に回転操作を適用していくだけです。けっきょく Splay 操作の場合、zig と zig - zag は回転操作と同じで、異なる操作は zig - zig だけです。次の例を見てください。
Ｅ Ｅ Ａ
／ ＼ ／ ＼ ／ ＼
Ｄ Ｄ Ｅ
／ ＼ ／ ＼ ／ ＼
Ｃ ２回転 Ａ ２回転 Ｄ
／ ＼ ───→ ／ ＼ ───→ ／ ＼
Ｂ Ｃ Ｃ
／ ＼ ／ ＼ ／ ＼
Ａ Ｂ Ｂ
／ ＼ ／ ＼ ／ ＼
（１） （２） （３）
図：回転操作の場合
節 A を回転操作でルートへ移動します。(1) の状態で節 B を右回転し、次に節 C を右回転すると (2) の状態になります。次に節 D を右回転してから節 E を右回転すると、(3) のように節 A をルートへ移動することができます。回転操作の場合、(1) と (3) で木の高さは変化しません。
次は Splay 操作を適用してみましょう。下図を見てください。
Ｅ Ｅ Ａ
／ ＼ ／ ＼ ／ ＼
Ｄ Ｄ Ｄ
／ ＼ ／ ＼ ／ ＼
Ｃ zig-zig Ａ zig-zig ／ ＼
／ ＼ ───→ ／ ＼ ───→ Ｂ Ｅ
Ｂ Ｂ ／ ＼ ／ ＼
／ ＼ ／ ＼ Ｃ
Ａ Ｃ ／ ＼
／ ＼ ／ ＼
（１） （２） （３）
図：splay 操作の場合
(1) の状態で、部分木 C - B - A に zig - zig を適用すると (2) の状態になります。次に (2) の状態で、部分木 E - D - A に zig - zig を適用すると (3) の状態になり、節 A がルートにきます。(3) は (1) よりも木の高さが 1 つ低くなっていますね。これが Splay 操作の効果です。
ところで、今までの説明は移動する節からルート方向へ木をたどって zig, zig - zig, zig - zag 操作を適用する、いわゆるボトムアップで Splay 操作を行っています。これに対し、ルートから木をたどっいくトップダウンでも Splay 操作を行うことができます。これを Top-Down Splay といいます。
Top-Down Splay の基本的な考え方は簡単です。トップダウンでルートから節 X までたどるとき、X よりも大きい節は X の右部分木になります。逆に、X よりも小さな節は左部分木になります。そこで、木をたどりながら左右の部分木を作成することにします。そして、節 X に到達したら X の子を部分木に挿入し、その部分木を節 X につなげればいいわけです。
それでは zig 操作から説明しましょう。次の図を見てください。
Ｙ Ｗ
／ ＼ Ｘ ／ ＼
Ｘ Ｃ ──→ ／ ＼ Ｙ
／ ＼ Ａ Ｂ ／ ＼
Ａ Ｂ Ｃ
図：zig (1)
左右の部分木を格納する作業用の節 W を用意します。W の左の子には X よりも大きなデータを、右の子には X よりも小さなデータを追加します。このようにすると、部分木の作成が簡単になります。
たとえば、節 Y の左部分木をたどる場合、左部分木には Y より大きなデータはありません。したがって、次のデータを追加するとき、X よりも小さなデータは必ず Y の左の子になります。つまり、左部分木をたどる場合は節を W の左部分木に追加し、逆に右部分木をたどる場合は W の右部分木に節を追加すればいいわけです。
上図の場合、Y を W の左の子にセットして、節 X に到達します。次は、X の子を W の部分木に追加します。
Ｗ Ｘ
Ｘ ／ ＼ ／ ＼
／ ＼ Ｙ Ａ ──→ Ａ Ｙ
／ ＼ ／ ＼
Ｂ Ｃ Ｂ Ｃ
図：zig (2)
X の左の子 A は X よりも小さいので W の右部分木に追加します。上図の場合、W の右の子に A をセットします。X よりも大きい右の子 B は、W の左部分木である Y の左の子にセットします。あとは、W の左部分木を X の右の子に、W の右部分木を X の左の子にセットすればいいわけです。
次は zig - zig 操作を説明します。下図を見てください。
Ｚ Ｙ Ｘ Ｗ
／ ＼ ／ ＼ ／ ＼ ／ ＼
Ｙ Ｄ zig ／ ＼ Ａ Ｂ Ｙ
／ ＼ ──→ Ｘ Ｚ ──→ ／ ＼
Ｘ Ｃ ／ ＼ ／ ＼ Ｚ
／ ＼ Ａ Ｂ Ｃ Ｄ ／ ＼
Ａ Ｂ Ｃ Ｄ
図：zig - zig (1)
zig - zig 操作の場合、最初に節 Z を右回転するところは今までと同じです。それから、節 Y を W の左部分木にセットします。これで節 X に到達したので、X の子を W に追加します。これは zig 操作と同じです。次の図を見てください。
Ｘ Ｗ Ｘ
／ ＼ ／ ＼ ／ ＼
Ｙ Ａ ──→ Ａ Ｙ
／ ＼ ／ ＼
Ｂ Ｚ Ｂ Ｚ
／ ＼ ／ ＼
Ｃ Ｄ Ｃ Ｄ
図：zig - zig (2)
X の左の子 A を W の右の子に、X の右の子 B を Y の左の子にセットします。最後に、W の左部分木を X の右の子に、W の右部分木を X の左の子にセットします。
次は zig - zag 操作を説明します。下図を見てください。
Ｚ Ｙ Ｗ
／ ＼ ／ ＼ ／ ＼
Ｙ Ｄ Ａ Ｘ Ｚ
／ ＼ ──→ ／ ＼ ／ ＼
Ａ Ｘ Ｂ Ｃ Ｄ
／ ＼
Ｂ Ｃ
図：zig - zag (1)
zig - zag 操作の場合、回転操作が不要なので zig - zig 操作よりも簡単です。節 Y は節 Z の左部分木なので、Z を W の左部分木に追加します。
Ｙ Ｗ Ｘ Ｗ
／ ＼ ／ ＼ ／ ＼ ／ ＼
Ａ Ｘ Ｚ ──→ Ｂ Ｃ ／ ＼
／ ＼ ／ ＼ Ｚ Ｙ
Ｂ Ｃ Ｄ ／ ＼ ／ ＼
Ｄ Ａ
図：zig - zag (2)
次に、節 X は Y の右部分木なので、Y を W の右部分木に追加します。これで X に到達したので、X の子を W の部分木に追加します。
Ｘ Ｗ Ｘ
／ ＼ ／ ＼ ／ ＼
／ ＼ ──→ ／ ＼
Ｚ Ｙ Ｙ Ｚ
／ ＼ ／ ＼ ／ ＼ ／ ＼
Ｃ Ｄ Ａ Ｂ Ａ Ｂ Ｃ Ｄ
図：zig - zag (3)
X の左の子 B は W の右部分木である Y の右の子に、X の右の子 C は W の左部分木である Z の左の子にセットします。あとは、W の左部分木を X の右の子に、W の右部分木を X の左の子にセットするだけです。
このように、トップダウンでも Splay 操作を実現することができます。それでは、Top-Down Splay の簡単な例を示しましょう。次の図を見てください。
Ｅ Ｃ Ｗ
／ ＼ ／ ＼ ／ ＼
Ｄ Ｂ Ｄ
／ ＼ ／ ＼ ／ ＼
Ｃ zig-zig Ａ Ｅ
／ ＼ ───→ ／ ＼ ／ ＼
Ｂ
／ ＼
Ａ
／ ＼
図：splay 操作の場合 (1)
節 A をルートに移動します。最初は部分木 E - D - C に zig - zig 操作を適用します。すると、節 W の左の子に節 D がセットされます。次に、部分木 C - B - A に zig - zig 操作を適用します。次の図を見てください。
Ｃ Ｗ Ｗ Ａ
／ ＼ ／ ＼ zig-zig Ａ ／ ＼ ／ ＼
Ｂ Ｄ ───→ ／ ＼ Ｄ ─→ Ｄ
／ ＼ ／ ＼ ／ ＼ ／ ＼
Ａ Ｅ ／ ＼ ／ ＼
／ ＼ ／ ＼ Ｂ Ｅ Ｂ Ｅ
／ ＼ ／ ＼ ／ ＼ ／ ＼
Ｃ Ｃ
／ ＼ ／ ＼
図：splay 操作の場合 (2)
節 D の左の子に節 B がセットされ、節 A に到達しました。あとは、A の子を W の部分木に追加して、W の左部分木を A の右の子に、W の右部分木を A の左の子にセットするだけです。
それでは Top-Down Splay のプログラムを Common Lisp で作ってみましょう。次のリストを見てください。
リスト：Top-Down Splay
; 節の定義
(defstruct Node data left right)
; Top-Down Splay
(defun splay (node data)
(let* ((w_node (make-Node)) (r_node w_node) (l_node w_node))
(loop
(cond ((= data (Node-data node))
(setf (Node-left r_node) (Node-right node)
(Node-right l_node) (Node-left node)
(Node-left node) (Node-right w_node)
(Node-right node) (Node-left w_node))
(return node))
((< data (Node-data node))
(if (< data (Node-data (Node-left node)))
; 右回転
(setf node (right-rotate node)))
(setf (Node-left r_node) node
r_node node
node (Node-left node)))
(t
(if (> data (Node-data (Node-right node)))
; 左回転
(setf node (left-rotate node)))
(setf (Node-right l_node) node
l_node node
node (Node-right node)))))))
二分木の節 Node は構造体で定義します。Top-Down Splay を行う関数が splay です。引数 node にはスプレイ木のルートを渡します。data はルートへ移動するデータです。今回は簡単な例題ということで、data には数値を格納することにします。また、data はスプレイ木に必ず存在することとします。
ボトムアップでスプレイ操作を行う場合、データを探索または挿入したあと、そのデータをルートへ移動します。ところが Top-Down Splay の場合、データの有無にかかわらず Splay 操作を行うことが可能です。この方法はあとで説明するとして、今回はオーソドックスにスプレイ木にあるデータをルートへ移動することにします。
関数 splay は前回説明した Top-Down Splay をそのままプログラムしただけです。w_node が部分木を格納する節、r_node が右部分木になる節、l_node が左部分木になる節を表します。r_node と l_node は w_node に初期化します。そして、data より大きな節 (node) は r_node の左の子にセットし、r_node を node に書き換えます。data より小さい場合は l_node の右の子にセットし、l_node を node に書き換えます。このとき、zig - zig 操作を行うかチェックし、そうであれば木を回転することに注意してください。
data を見つけた場合、node の左右の子を r_node と l_node にセットします。そして、w_node の右部分木を node の左の子に、w_node の左部分木を node の右の子にセットしてから node を返します。
これでプログラムは完成です。それでは、簡単な実行例を示します。
(setq root nil)
nil
(dolist (x '(5 4 3 2 1))
(setq root (insert-tree root x)))
nil
(print-tree 0 root)
1
2
3
4
5
nil
(setq root (splay root 1))
(print-tree 0 root)
1
2
3
4
5
nil
(setq root (splay root 3))
(print-tree 0 root)
1
2
3
4
5
nil
正常に動作していますね。
ところで、Top-Down Splay は指定したデータが見つからない場合でも、スプレイ操作を行うことができます。基本的な考え方は簡単です。Top-Down Splay は木をルートからトップダウンでたどりながら、ルートへ移動するデータを探します。これは二分木でデータを探索する動作と同じです。データを X とすると、X が見つからない場合でも、最後にアクセスした節のデータ Y は、X より小さなデータの中で一番大きな値か、X よりも大きなデータの中で一番小さな値のどちらかになります。
そこで、X が見つからない場合は、この Y をルートへ移動することにします。そうすると、データの探索は Top-Down Splay を行ってから、ルートのデータをチェックするだけで実現できます。データの挿入と削除も、Top-Dwon Splay を行ったあとで簡単に実現することができます。
それではプログラムを作りましょう。最初に、Top-Down Splay を行う関数 splay を改造します。次のリストを見てください。
リスト：Top-Down Splay
(defun splay (node data)
(let* ((w_node (make-Node)) (r_node w_node) (l_node w_node))
(loop
(cond ((= data (Node-data node)) (return))
((< data (Node-data node))
(if (null (Node-left node)) (return))
(when (< data (Node-data (Node-left node)))
; 右回転
(setf node (right-rotate node))
(if (null (Node-left node)) (return)))
(setf (Node-left r_node) node
r_node node
node (Node-left node)))
(t
(if (null (Node-right node)) (return))
(when (> data (Node-data (Node-right node)))
; 左回転
(setf node (left-rotate node))
(if (null (Node-right node)) (return)))
(setf (Node-right l_node) node
l_node node
node (Node-right node)))))
;
(setf (Node-left r_node) (Node-right node)
(Node-right l_node) (Node-left node)
(Node-left node) (Node-right w_node)
(Node-right node) (Node-left w_node))
node))
data を見つけたら return で loop を脱出します。左部分木をたどるとき、節 node の左の子がない場合は、そこで loop を脱出して node をルートへ移動します。右回転したときは、もう一度 node に左の子があるかチェックします。右部分木をたどるときも同様に、節 node の右の子があるかチェックします。子がない場合はそこで loop を脱出して node をルートへ移動します。
loop を脱出したら、node の左右の子を r_node と l_node にセットします。そして、w_node の右部分木を node の左の子に、w_node の左部分木を node の右の子にセットしてから node を返します。
これでプログラムは完成です。それでは、簡単な実行例を示します。
(setq root nil)
nil
(dolist (x '(0 2 4 6 8 10))
(setq root (insert-tree root x)))
nil
(print-tree 0 root)
0
2
4
6
8
10
nil
(setq root (splay root 11))
(print-tree 0 root)
0
2
4
6
8
10
nil
(setq root (splay root 5))
(print-tree 0 root)
0
2
4
6
8
10
nil
スプレイ木にデータ 5 と 11 はありませんが、スプレイ操作は正常に行われています。このように、データが見つからない場合でも、Top-Down Splay はスプレイ操作を行うことができます。
次は Top-Down Splay を行ってからデータを挿入するプログラムを作ってみましょう。次のリストを見てください。
リスト：データの挿入
(defun insert-splay-tree (node data)
(let ((new-node (make-Node :data data)))
(if (null node)
(return-from insert-splay-tree new-node))
(setf node (splay node data))
(cond ((= data (Node-data node)) node)
((< data (Node-data node))
(setf (Node-right new-node) node
(Node-left new-node) (Node-left node)
(Node-left node) nil)
new-node)
(t
(setf (Node-left new-node) node
(Node-right new-node) (Node-right node)
(Node-right node) nil)
new-node))))
最初に新しい節 new-node を作ります。引数 node が nil の場合、スプレイ木は空なので new-node を返します。そうでなければ、関数 splay で Top-Down Splay を行います。ルートの節 node のデータが data と等しい場合は、同じデータがあるので node をそのまま返します。
data が node のデータよりも小さい場合は、new-node の右の子に node をセットします。node の左部分木は data よりも小さなデータしかないので、node の左部分木を new-node の左の子にセットし、node の左の子を nil に書き換えます。これで node の左部分木の高さを 1 つ低くすることができます。最後に new-node を返します。
逆に、data が node のデータよりも大きい場合は、new-node の左の子に node をセットします。node の右部分木は data よりも大きなデータしかないので、node の右部分木を new-node の右の子にセットし、node の右の子を nil に書き換えます。これで node の右部分木の高さを 1 つ低くすることができます。最後に new-node を返します。
それでは、簡単な実行例を示しましょう。
(setq root nil)
nil
(dolist (x '(0 2 4 6 8))
(setq root (insert-splay-tree root x))
(print-tree 0 root)
(terpri))
0
0
2
0
2
4
0
2
4
6
0
2
4
6
8
nil
(setq root (insert-splay-tree root 5))
(print-tree 0 root)
0
2
4
5
6
8
nil
スプレイ木の場合、ソート済みのデータ (0 2 4 6 8) を順番に挿入すると、データは左右に均等に分配されず偏った木になってしまいます。ここで、他のデータ (5) を挿入すると、スプレイ木はバランスを取るように働きます。このように、一時的に木のバランスが崩れることがあっても、トータルとして考えると木のバランスを保つように動作するのがスプレイ木の特徴です。
次は Top-Down Splay を行ってからデータを削除するプログラムを作ってみましょう。次のリストを見てください。
リスト：データの削除
(defun delete-splay-tree (node data)
(when node
(setf node (splay node data))
(if (= data (Node-data node))
; データあり
(cond ((null (Node-left node)) (Node-right node))
((null (Node-right node)) (Node-left node))
(t
(let ((node1 (splay (Node-left node) data)))
(setf (Node-right node1) (Node-right node))
node1)))
; データなし
node)))
引数 node が nil の場合、スプレイ木は空なので nil を返します。そうでなければ、関数 splay で Top-Down Splay を行います。ルートの節 node のデータが data と等しい場合は、そのデータを削除します。そうでなければ、スプレイ木に data はないので node を返します。
データを削除するとき、node の子が 0 または 1 個の場合は簡単です。右の子がない場合は左の子を返し、左の子がない場合は右の子を返すだけです。子がない場合は nil が返されるので、スプレイ木は空になります。
二分木の場合、子が 2 つあるデータを削除する処理はちょっと複雑になります。削除するデータの右部分木の中から最小値のデータを探して、それと削除するデータと置き換えれば、二分木の条件を満たすことができます。逆に、左部分木の中から最大値を探して、それと削除するデータを置き換えてもかまいません。詳しい説明は拙作のページ Common Lisp 入門：番外編 二分木：データの削除 を参照してください。
スプレイ木の場合、データの削除処理は Top-Down Splay を使うと簡単に実現できます。node の左部分木に対し、data を与えて Top-Down Splay を行います。node の左部分木は data よりも小さなデータしかありません。したがって、data を与えて Top-Down Splay を行うと、node1 は左部分木の中で一番大きなデータになり、node1 の右部分木は空の木になります。あとは、node1 の右の子に node の右の子をセットして node1 を返すだけです。
それでは、簡単な実行例を示しましょう。
(setq root nil)
nil
(dotimes (x 5)
(setq root (insert-splay-tree root x)))
nil
(print-tree 0 root)
0
1
2
3
4
nil
(dotimes (x 5)
(setq root (delete-splay-tree root x))
(print-tree 0 root)
(terpri))
1
2
3
4
2
3
4
3
4
4
nil
正常に動作していますね。