ie_test: 赤黒木

以下を参考にしたメモ
http://www.geocities.jp/m_hiroi/light/pyalgo16.html

赤黒木の定義
　赤黒木は次の条件を満たす「二分木」

各ノードは赤または黒に区分される。
赤ノードの子は必ず黒である。(黒ノードの子に制限はない。)
ルートからリーフまでの黒節の個数を「黒高さ」という。赤黒木はルートからリーフへのどの経路でも黒高さが同じであることを要求する。ここで、子が一つのノードもリーフと取り扱い、上記の条件を満たすことを要求する。
ルートのノードは黒。

上記を満たすように挿入、削除を行うことでノードの個数に対して、高さを低く保つことになる。

挿入
まず二分木としてノードを挿入する。この時、挿入されたノードは赤として挿入する。
次に赤黒木の定義を満たすためにノードの色の更新を行う。
二分木の挿入は全てリーフとして挿入されるが、挿入したノードの親ノードが黒の場合は赤黒木の定義に違反することはない。挿入したノードの親ノードが赤の場合、修正操作が必要となる。

一般に二分木に対して次の回転と呼ばれる操作がある。

図1

図2

図3

回転の操作は二分木の条件を満たしつつ行われる操作であり、この操作を組み合わせることで赤黒木の条件を満たすように木を修正する。

挿入の場合分け

以下での説明のためのスライドにおいては挿入されたノードは「n」で表す。また通常挿入されるノードはリーフであるが、証明の都合により、挿入されたノードがリーフでない場合も含めて論証する。またその際、黒高さの条件は満たされており、挿入されたノード以下では赤ノードに関する条件は満たされているとする。
1. 挿入したノードの親が黒ノードの場合

赤黒木の条件を崩さないのでこのままで良い。(図4)

図4

2. 挿入したノードの親が赤ノードの場合

この時、親ノードの親ノードは黒であり、兄弟ノードの親ノードの兄弟ノードの色の場合によって、以下の 3 通りに場合分けされる。
2-1. 親の兄弟がいない場合

この場合、黒高さの条件より、親ノードも子ノードを持たず、自ノードも子ノードを持たない。また挿入したノードが内側にある場合と外側にある場合で、操作に差が出る。以下の 2 通りに場合分けする。
2-1-1.挿入したノードが外側にある場合(図5)

図5

親ノードの親ノードで回転し、親ノードの親ノードと親ノードの色を交換する。これで条件を回復する。

2-1-2. 挿入したノードが外側にある場合(図6)

図6

親ノードの親ノードを起点としてRLの二重回転を行うい、自ノードと親ノードの親ノードの色を変える。これで赤黒木の条件が回復する。

2-2. 親ノードの兄弟が赤ノードの場合(図7)

図7

親ノードの色を赤に、兄弟ノードの自ノードを黒にする。こうすることで、黒高さに対する条件を満たした状態になり、問題をよりルートに近い位置に赤ノードを挿入した場合に帰着できる。木の高さは有限なので、この操作は有限回である。しかし親ノードの親ノードに対する操作がルートまで到達した際には、ルートは黒にして操作が終了する。

2-3. 親ノードの兄弟が黒ノードの場合

挿入したノードが内側にある場合と外側にある場合で、操作に差が出る。以下の 2 通りに場合分けする。
2-3-1.挿入したノードが外側にある場合(図8)

図8

親ノードの親ノードに対して自ノードがいる側を上に持ち上げる回転を行い、親ノードとその親ノードの色を逆にする。これで赤黒木の条件が回復する。

2-3-2.挿入したノードが内側にある場合(図9)

図9

親ノードの親ノードを起点としてRLの二重回転を行う。自ノードと親ノードの親ノードの色を変える。これで赤黒木の条件が回復する。

以上。実は「2-1. 親ノードの兄弟ノードがない」場合と「2-3. 親ノードの兄弟が黒」の場合は同一の操作であることがわかる。また場合分けとして挿入するノードは親ノードの親ノードから見て、右側にある場合を示したが、左側にある場合は逆の回転操作になる。

削除の場合
以降では削除について述べる。削除の場合はさらに場合分けがあり、ある場合がある場合に帰着されるなど、場合の依存がわかりにくいことが赤黒木を複雑にしている要因と思われる。
方針としては挿入の時と同様にまず、2分木の削除を行い、その後、赤黒木の条件を満たすようにノードと色の操作を行う。

2分木の削除の場合、次の図のように二つの子ノードをもつノードを削除する場合にも
一つの子ノードもしくは一つも持たない場合に帰着される。(図10)

図10

よって削除されるノードは2分木の削除なので子ノードが一つか、リーフである場合になる。場合分けとしてまずは削除されるノードの色で場合分けする。
1. 削除ノードが赤の場合

黒高さ、赤ノードに対する条件を破ることはないので、良い。

2. 削除されたノードが黒の場合

かなり場合分けが複雑となる。以下の図11 にある記号を使って、親ノード、兄弟ノード、兄弟ノードの子ノードの色の組み合わせによって場合分けを行う。

図11

上記のように X のルートの部分に取り除いたノードがあったものとする。

2-1. 親ノードが黒の場合

2-1-1. 親ノードが黒、兄弟ノードが黒の場合

2-1-1-1. 親ノードが黒、兄弟ノードが黒、兄弟ノードの子ノードが両方とも黒の場合(図12)

図12

兄弟ノードを赤にすることで取り除いた黒ノードの個数と合わせて黒高さが一定になる。ただし q 以下の黒高さは全体に比べて一つ小さくなっている。なので q 以下の部分木から一つノードを取り除いたパターンとして、また再帰的に木に操作する必要がある。ただし、元々の X の部分から見れば一つ、ルートに近いところから削除されたと見なせるので、この操作は有限回で終わる。もしも q がルートならば操作は終了。全体の黒高さが -1 されたことになる。

2-1-1-2. 親ノードが黒、兄弟ノードが黒、兄弟ノードの子のノードで内側のノードが赤、外側が黒の場合(図13)

図13

兄弟ノードで回転させて、赤の子ノードを持ち上げる回転の操作を行う。そのあと持ち上げた赤ノードと元の兄弟ノードの色を交換する。すると部分木 A,B,C の黒高さはどれも等しいので、これは次の項目で説明する「2-2-1-3. 親ノードが黒、兄弟ノードが黒、兄弟ノードの子ノードの内側のノードが黒、外側のノードが赤の場合に帰着する。

2-1-1-3. 親ノードが黒、兄弟ノードが黒、兄弟ノードの子のノードの内側のノードが黒、外側が赤の場合(図14)