Common Lisp 入門 の番外編です。今回は「平衡木」というデータ構造のひとつである「2 色木」を取り上げます。なお、このドキュメントは拙作のページ Memorandum で説明した「2 色木：データの削除」をまとめたものです。内容は重複していますが、ご了承くださいませ。
今回は 2 色木の「データの削除」を説明します。2 色木の場合、二分木と同様にデータを削除して、そのあと 2 色木の条件を満たすように木のバランスを修正します。
二分木：データの削除 で説明したように、実際に削除される節は「葉」の場合か、子をひとつだけ持っている場合です。もしも、削除する節が「赤」ならば簡単です。2 色木の条件により、子をひとつだけ持つ赤節は存在しないので、その赤節は「葉」であることがわかります。したがって、その節を削除するだけで OK です。黒高さに変化はないので、木のバランスを修正する必要もありません。
問題は黒節を削除する場合です。その黒節が子をひとつ持っている場合は簡単です。2 色木は黒高さが一定になるので、黒節がひとつだけ子を持つ場合、その子は赤節しかありえません。次の図を見てください。
root root
● 14 ● 14
／ ＼ ／ ＼
／ ＼ ／ ＼
● 12 ■ 16 => ● 12 ■ 16
＼ ／ ＼ ＼ ／ ＼
13 ■ ● 15 ● 17 13 ■ ● 15 ● 18
＼
■ 18
（Ａ） （Ｂ）
■：赤節点, ●：黒節点
図：データ (17) の削除
図 (A) でデータ 17 を削除します。図 (B) のように、削除する節 (17) とその子 (18) を置き換えたあと、節 (18) の色を黒に塗り替えるだけで 2 色木の条件を満たすことができます。
簡単なのはここまでです。たとえば、図 (A) で節 (15) を削除する場合を考えてみましょう。削除する黒節は「葉」なので、節 (16) の左部分木の黒高さがひとつ低くなりますね。この場合、木のバランスを修正するため回転操作が必要になります。図 (A) では、節 (16) 以下の部分木を左回転すれば、2 色木の条件を満たすことができます。
この例では簡単に木のバランスを修正できますが、実際には削除する節の親、兄弟、兄弟の子の「色」によって場合分けが必要になります。この処理がけっこう複雑になるのです。「データの挿入」でも節の色によって場合分けを行いましたが、「データの削除」はそれ以上に複雑なので、プログラムはちょっと面倒になります。
2 色木の場合、データを挿入するときは回転操作により黒節と黒節の間に赤節を挿入することで、木のバランスを修正しました。データを削除する場合、黒高さがひとつ低くなった部分木に回転操作で節を挿入して、黒高さが同じになるように節の色を塗り替える、というのが基本的な考え方です。
具体的には、削除する節の親、兄弟、兄弟の子から赤節を探して、回転操作と色の塗り替えにより木のバランスを修正します。たとえば、黒節をひとつ削除して、左部分木の黒高さがひとつ低くなった場合を考えてみます。この場合、次に示す 9 通りのパターンがあります。
●Ｙ ■ ●
／ ＼ ／ ＼ ／ ＼
●Ｘ ●Ｚ ● ● ● ■
／ ＼ ／ ＼ ／ ＼
●Ａ ●Ｂ ● ● ● ●
（１） （２） （３）
● ● ●
／ ＼ ／ ＼ ／ ＼
● ● ● ● ● ●
／ ＼ ／ ＼ ／ ＼
■ ● ● ■ ■ ■
（４） （５） （６）
■ ■ ■
／ ＼ ／ ＼ ／ ＼
● ● ● ● ● ●
／ ＼ ／ ＼ ／ ＼
■ ● ● ■ ■ ■
（７） （８） （９）
■：赤節点, ●：黒節点
図：左部分木の黒高さが -1 になる場合
上図は、部分木 X の黒高さが -1 になる場合です。この場合、節 X の色は黒になります。たとえば、黒節 (葉) を削除した場合、終端を表す節 END が節 X に相当しますが、END の色を黒とすれば上図で表すことができます。そして、X 以外の節 Y, Z, A, B の中でひとつでも赤節があれば、回転操作と色の塗り替えにより木のバランスを修正することができます。
逆にいえば、上図 (1) のように節 Y, Z, A, B がすべて黒節の場合、木のバランスは修正できません。この場合、節 Z 以下の右部分木の黒高さを左部分木と同じに揃えて、節 Y の親節で木のバランスを修正します。次の図を見てください。
●Ｙ ●Ｙ
／ ＼ ／ ＼
●Ｘ ●Ｚ => ●Ｘ ■Ｚ
／ ＼ ／ ＼
●Ａ ●Ｂ ●Ａ ●Ｂ
図：パターン (1) の修正
節 Z の色を赤に塗り替えれば、右部分木の黒高さはひとつ低くなります。これで、左右の部分木の黒高さを同じに揃えることができます。つまり、部分木 Y の黒高さがひとつ低くなるわけです。あとは、節 Y の親節で木のバランスを修正します。もしも、節 Y がルートであれば、これで木の修正は終わりです。この操作で、2 色木の黒高さはひとつ低くなります。
次はパターン (2) の修正を説明します。次の図を見てください。
■Ｙ ●Ｙ
／ ＼ ／ ＼
●Ｘ ●Ｚ => ●Ｘ ■Ｚ
／ ＼ ／ ＼
●Ａ ●Ｂ ●Ａ ●Ｂ
図：パターン (2) の修正
パターン (2) は節 Y だけが赤節で、節 Z, A, B が黒節の場合です。この場合は、節 Y と Z の色を塗り替えるだけで、木のバランスを修正できます。節 Y を黒に塗り替えると左右の部分木の黒高さは +1 されますが、節 Z を赤に塗り替えることで右部分木の黒高さが -1 されるので、左部分木だけ黒高さを +1 することができます。
節 Y は赤節なので、その親節は 2 色木の条件により必ず黒節になります。したがって、節 Y の色を黒に塗り替えても、2 色木の条件を満たしているので大丈夫です。
次はパターン (3) の修正を説明します。次の図を見てください。
●Ｙ ●Ｚ
／ ＼ ／ ＼
●Ｘ ■Ｚ => ■Ｙ ●Ｂ
／ ＼ ／ ＼
●Ａ ●Ｂ ●Ｘ ●Ａ
図：パターン (3) の修正
パターン (3) は節 Z だけが赤節で、節 Y, A, B が黒節の場合です。この場合、部分木 Y を左回転して、節 Y, Z の色を塗り替えます。すると、節 A と B の黒高さは同じままなので、赤節 Y の左部分木 X の黒高さが -1 になった場合に変換することができます。あとは、節 Y が「赤」のパターン (2), (7), (8), (9) を適用して、木のバランスを修正します。
次は節 B が「赤」のパターン (5), (6), (8), (9) の修正を説明します。次の図を見てください。
●Ｙ ●Ｚ ●Ｙ ●Ｚ
／ ＼ ／ ＼ ／ ＼ ／ ＼
●Ｘ ●Ｚ => ●Ｙ ●Ｂ ●Ｘ ●Ｚ => ●Ｙ ●Ｂ
／ ＼ ／ ＼ ／ ＼ ／ ＼
●Ａ ■Ｂ ●Ｘ ●Ａ ■Ａ ■Ｂ ●Ｘ ■Ａ
（５） （６）
■Ｙ ■Ｚ ■Ｙ ■Ｚ
／ ＼ ／ ＼ ／ ＼ ／ ＼
●Ｘ ●Ｚ => ●Ｙ ●Ｂ ●Ｘ ●Ｚ => ●Ｙ ●Ｂ
／ ＼ ／ ＼ ／ ＼ ／ ＼
●Ａ ■Ｂ ●Ｘ ●Ａ ■Ａ ■Ｂ ●Ｘ ■Ａ
（８） （９）
図：節 B が「赤」のパターン (5), (6), (8), (9) の修正
パターン (5), (6) は節 Y, Z が黒節で、節 B が赤節の場合です。この場合、部分木 Y を左回転して、節 B の色を「黒」に塗り替えます。経路 Y - Z - B は Y - B になりますが、節 B が「黒」になったので節 B の黒高さは同じままです。経路 Y - Z - A は Z - Y - A と順番が変わるだけなので、節 A の黒高さは同じままです。経路 Y - X は Z - Y - X になり、黒節 Z が挿入されるので、節 X の黒高さは +1 されます。
パターン (8), (9) も同様に、部分木 Y を左回転して節 B を「黒」に塗り替えますが、節 Y, Z の色も塗り替えることに注意してください。経路 Y - X は Z - Y - X になり、黒節 Y が挿入されるので、節 X の黒高さは +1 されます。ほかの節の黒高さは同じままです。これで木のバランスは修正されます。
最後に、節 B が「黒」で節 A が「赤」のパターン (4), (7) の修正を説明します。次の図を見てください。
●Ｙ ●Ｙ
／ ＼ ／ ＼
●Ｘ ●Ｚ => ●Ｘ ●Ａ
／ ＼ ／ ＼
■Ａ ●Ｂ ◎Ｃ ■Ｚ
／ ＼ ／ ＼
◎Ｃ ◎Ｄ ◎Ｄ ●Ｂ
（４）
■Ｙ ■Ｙ
／ ＼ ／ ＼
●Ｘ ●Ｚ => ●Ｘ ●Ａ
／ ＼ ／ ＼
■Ａ ●Ｂ ◎Ｃ ■Ｚ
／ ＼ ／ ＼
◎Ｃ ◎Ｄ ◎Ｄ ●Ｂ
（７）
図：パターン (4), (7) の修正
パターン (4) は節 A が赤節で、節 Y, Z, B が黒節の場合です。パターン (7) は節 A, Y が赤節で、節 Z, B が黒節の場合です。どちらの場合も、部分木 Z を右回転して節 A, Z の色を塗り替えることで、(4) ならばパターン (5), (6) に、(7) ならばパターン (8), (9) に変換します。あとは、部分木 Y を左回転して節の色を塗り替えれば、木のバランスを修正することができます。
このように、9 通りのパターンを 5 通りの修正パターンに場合分けすることができます。実際には、左部分木だけではなく右部分木の黒高さが -1 になる場合もあるので、プログラムを作るときには注意してください。
それでは、2 色木のデータを削除するプログラムを Common Lisp で作ってみましょう。節の定義と終端を表すオブジェクトは、2 色木（その１） で作成した「データの挿入」のプログラムと同じです。リストを再掲載します。
リスト：節と終端の定義（再掲） ; 節の定義 (defstruct Node color data right left) ; 終端を表すオブジェクトの定義 (setf END (make-Node :color 'B))
構造体 Node のスロット color には節の色をセットします。赤をシンボル R で、黒をシンボル B で表します。スロット data に格納するデータは整数値とします。それから、終端を Node のオブジェクト END で表すことにします。終端 END を黒節とすると、終端と黒節の場合分けが不用になるのでプログラムが簡単になります。
次はデータを削除する関数 delete-rb-tree を作成します。2 色木の場合、節を削除したあとで木のバランスをチェックします。2 分木ではデータの削除を再帰呼び出しでプログラムしましたが、木のバランスをチェックするにはちょっと面倒なので、「データの挿入」のプログラムと同様にループに展開することにします。プログラムは次のようになります。
リスト：2 色木「データの削除」
(defun delete-rb-tree (root num)
(let* ((path (search-delete-path root num))
(node (pop path))
(pnode (pop path)))
(cond ((null node) root) ; データ無し
; 左の子がある
((not (eq (Node-left node) END))
(setf (Node-data node) (Node-data (Node-left node))
(Node-left node) END)
root)
; 右の子がある
((not (eq (Node-right node) END))
(setf (Node-data node) (Node-data (Node-right node))
(Node-right node) END)
root)
; root を削除して空の木になる場合
((eq root node) END)
; 葉を削除する場合
(t
(if (left-child-p pnode node)
(setf (Node-left pnode) END)
(setf (Node-right pnode) END))
; 赤節は削除するだけでよい
(if (red-p node)
root
; バランスの修正
(delete-check-balance root END pnode path))))))
関数 search-delete-path は root から削除する節までの経路を求めます。ただし、経路は逆順であることに注意してください。root が空の木、または引数 num と同じデータが見つからない場合は nil を返します。次に、path から削除する節を取り出して変数 node にセットし、node の親節を pnode にセットします。node が nil の場合は削除する節がないので、root をそのまま返します。
削除するデータが見つかった場合、node が子を持っているかチェックします。左右どちらかの子があれば、node を削除するのではなく、node の data を子の data に書き換えることでデータを削除します。そして、node の left または right に END をセットして、不用になった節を削除します。
node が「葉」で root の場合、2 色木は空になったので END を返します。root でない場合は、pnode を書き換えて node を削除します。left-child-p は、node が pnode の左の子であれば真を返す関数です。左の子であれば pnode の left に、右の子であれば right に END をセットします。
次に、削除した node の色 (color) をチェックします。関数 red-p は、node の color が赤 (R) ならば真を返す関数です。node が赤節の場合は、木のバランスを修正する必要はありません。黒節の場合は、関数 delete-check-balance を呼び出して木のバランスを修正します。
次は関数 search-delete-path を説明します。次のリストを見てください。
リスト：削除する節までの経路を求める
(defun search-delete-path (node num)
(let (path find-node)
(while (not (eq node END))
; 節を記憶
(push node path)
(cond ((< num (Node-data node)) ; 左の子をたどる
(setf node (Node-left node)))
((< (Node-data node) num) ; 右の子をたどる
(setf node (Node-right node)))
(t (setf find-node node) ; 発見
(return))))
; データが見つからない場合は nil を返す
(when find-node
; 左右の子がある場合は右部分木から最小値を探す
(when (and (not (eq (Node-left node) END))
(not (eq (Node-right node) END)))
(setf node (Node-right node))
; 左の子をたどっていく
(loop
(push node path)
(if (eq (Node-left node) END) (return))
(setf node (Node-left node)))
; 最小値をセットする
(setf (Node-data find-node) (Node-data node)))
; 経路 path を返す
path)))
最初に、2 色木をたどって削除するデータ num を探します。経路は変数 path に格納します。見つけた場合、節を変数 find-node にセットします。次に、find-node が左右両方の子を持っているかチェックします。その場合は、右部分木の中から最小値のデータを探します。そして、find-node に最小値のデータをセットして、path を返します。この段階で数値 num は削除されますが、不用になった節は残されたままです。あとは delete-rb-tree で不用になった節を削除して、木のバランスをチェックします。
次は、黒節を削除したとき、木のバランスを修正する処理を説明します。次のリストを見てください。
リスト：黒節を削除したときのバランスのチェック
(defun delete-check-balance (root node pnode path)
(let (node-bro result gnode)
(loop
; 兄弟を求める
(if (left-child-p pnode node)
(setf node-bro (Node-right pnode))
(setf node-bro (Node-left pnode)))
(cond
((continue-p node-bro pnode)
; node-bro を赤に塗り替えて上の木でチェックする
(write-red node-bro)
(setf node pnode
pnode (pop path))
; root のチェック
(if (eq root node) (return root)))
(t
; 回転によるバランスの修正
(setf result (delete-rotate-tree node node-bro pnode))
; 節の付け替え
(setf gnode (pop path))
(cond ((null gnode) (setf root result)) ; root の付け替え
((left-child-p gnode pnode)
(setf (Node-left gnode) result))
(t
(setf (Node-right gnode) result)))
(return root))))))
関数 delete-check-balance の引数 node は、黒高さが -1 になった部分木を表します。引数 pnode が node の親節です。root がルートを表し、path がルートからの経路を表します。
最初に、node の兄弟を求めて変数 node-bro にセットします。そして、親節 pnode, 兄弟 node-bro, 兄弟の子がすべて黒節の パターン (1) かチェックします。この処理を関数 continue-p で行います。この場合、木のバランスは修正できないので、node-bro を「赤」に塗り替えて、pnode の親節でバランスを修正します。write-red は node の color を赤 (R) に塗り替える関数です。このとき、pnode がルートであれば、バランスの修正はこれで終わりです。
パターン (1) 以外の場合は、回転操作により木のバランスを修正します。この処理を関数 delete-rotate-tree で行います。結果は変数 result にセットします。そのあとで、pnode の親節を書き換えます。path から節を取り出して変数 gnode にセットします。gnode が nil ならばルートを書き換えるので、result をそのまま返します。そうでなければ、gnode の子を result に付け替えて root を返します。
次は delete-rotate-tree を説明します。次のリストを見てください。
リスト：回転によるバランスの修正
(defun delete-rotate-tree (node node-bro pnode)
(cond
((not-rotate-p node-bro pnode)
; 節の色を塗り替えて終了
(write-black pnode)
(write-red node-bro)
pnode)
((red-p node-bro)
; ２重回転
(if (left-child-p pnode node)
(delete-double-rotate-left node node-bro pnode)
(delete-double-rotate-right node node-bro pnode)))
(t
; 回転または２重回転
(if (left-child-p pnode node)
(delete-rotate-left node node-bro pnode)
(delete-rotate-right node node-bro pnode)))))
最初に、木を回転しなくてもバランスを修正できる パターン (2) かチェックします。この処理を関数 not-rotate-p で行います。そうであれば、節の色を塗り替えて pnode をそのまま返します。write-black は node の color を黒 (B) に塗り替える関数です。
node の兄弟 node-bro が赤節の場合、パターン (3) の修正を行います。左部分木の黒高さが -1 になったならば delete-double-rotate-left を呼び出し、右部分木ならば delete-double-rotate-right を呼び出します。
残りのパターンはひとつの関数で処理します。左部分木の黒高さが -1 になったならば delete-rotate-left を呼び出し、右部分木ならば delete-rotate-right を呼び出します。
次は、パターン (3) の修正を行う関数 delete-double-rotate-left を説明します。次のリストを見てください。
リスト： 2 重回転 [パターン (3)]
(defun delete-double-rotate-left (node node-bro pnode)
; 色の塗り替え
(write-red pnode)
(write-black node-bro)
; 左回転
(setf pnode (left-rotate pnode))
; 再度回転処理
(setf (Node-left pnode)
(delete-rotate-tree node
(Node-right (Node-left pnode))
(Node-left pnode)))
; pnode を返す
pnode)
最初に pnode と node-bro の色を塗り替えて、pnode の部分木を left-rotate で左回転します。回転した木は pnode にセットします。そのあと、再度 delete-rotate-tree を呼び出して、木のバランスを修正します。このとき、回転操作の対象になるのは pnode ではなく、pnode の左部分木になることに注意してください。よくわからない方は、パターン (3) の修正図を見てくださいね。修正後の部分木は pnode の left にセットして、pnode を返します。
delete-double-rotate-right は回転操作が左右対称になるだけなので、説明は省略いたします。
次は、パターン (4) - (9) の修正を行う関数 delete-rotate-left を説明します。次のリストを見てください。
リスト：左回転による修正
(defun delete-rotate-left (node node-bro pnode)
(when (black-p (Node-right node-bro))
; node-bro を右回転 : パターン (4), (7)
(write-red node-bro)
(write-black (Node-left node-bro))
(setf (Node-right pnode) (right-rotate node-bro)))
; 色の塗り替え : パターン (5), (6), (8), (9)
(when (red-p pnode)
; パターン (8), (9)
(write-black pnode)
(write-red (Node-right pnode)))
(write-black (Node-right (Node-right pnode)))
; pnode を左回転
(left-rotate pnode))
引数 node は、黒高さが -1 になった部分木を表します。引数 node-bro が node の兄弟で、pnode が node の親を表します。最初に、パターン (4), (7) をチェックします。node-bro の右の子が黒節ならば、node-bro と node-bro の左の子の色を塗り替えてから node-bro を右回転して、pnode の右部分木を書き換えます。これで、パターン (5), (6), (8), (9) に変換されます。
次に、パターン (8), (9) のチェックを行います。pnode が赤節ならば、pnode と pnode の右の子の色を塗り替えます。あとは、パターン (5), (6) と同じ処理になります。pnode の「右の子」の「右の子」の色を黒に塗り替えてから pnode を左回転します。よくわからない方は、修正図 を見ながらプログラムをお読みくださいませ。
delete-rotate-right は回転操作が左右対称になるだけなので、説明は省略いたします。これでプログラムは完成です。
それでは簡単な実行例を示しましょう。次に示す 2 色木で、1 から 10 までの数値を順番に削除してみましょう。
●1
●2
●3
●4
●5
●6
●7
■8
●9
■10
-- delete 1 --
●2
■3
●4
●5
●6
●7
●8
●9
■10
-- delete 2 --
●3
●4
●5
●6
●7
●8
●9
■10
-- delete 3 --
●4
■5
●6
●7
■8
●9
■10
-- delete 4 --
●5
●6
●7
■8
●9
■10
-- delete 5 --
●6
■7
●8
●9
■10
-- delete 6 --
●7
●8
●9
■10
-- delete 7 --
●8
●9
●10
-- delete 8 --
●9
■10
-- delete 9 --
●10
-- delete 10 --
nil
図：データ削除の実行例
図では print-rb-tree の出力を書き換えて、黒節を ● で、
赤節を ■ で表しています。どの経路でも黒高さが同じになっていることはすぐにわかると思います。興味のある方は、いろいろなデータで試してみてください。