なにこれ
前回の続き
本の中で特に重要だと言われている項目のみまとめるため、6章から9章に飛んでいます。
BinarySearchTreeの問題点は、要素の追加の仕方によって木の構造がアンバランスになることです。（例えば[1,2,3,4,5]のように追加する）
そこで木の高さが要素数の対数で抑えられる二分木が赤黒木(Red-Black Tree)です。
赤黒木は、JavaのコレクションフレームワークやC++の標準テンプレートライブラリのいくつかにも実装されており、広く利用されているようです。
2-4木
赤黒木の前に背景知識となる2-4木についてまとめます。
2-4木は以下の性質があります。
- すべての葉の深さは等しい
- すべての内部ノードは2個以上4個以下の子ノードを持つ
赤黒木
2-4木をシミュレートする二分木が赤黒木であり、各ノードが赤か黒の色を持ちます。 赤か黒かの色の持ち方のルールは以下です。
- (黒の高さの性質) 葉から根への経路には、いずれも黒ノードが同じ数だけ含まれる
- (赤の辺の性質) 赤のノード同士は隣接しない
これに加えて単純化するために「根は黒のまま保つ」「外部ノードは黒にする」というルールを設けます。
（外部ノードとはu.x!=nilの場合にleftかrightの子ノードがnilの場合に持つ仮の子ノードのことです）
赤黒木と2-4木がどう繋がるかというと、「赤黒木から全ての赤ノードuを取り除き、uの2つの子を両方ともuの親に接続する」という 処理を行うと、出来上がった木は2-4木になるのです。
正直この関係性によってどうシミュレートできているか理解しきれていません。。
①葉の深さが等しい=バランスな木を作りたい-->2-4木②処理しやすい二分木がいい
①を満たしつつ②の性質を満足させるためのデータ構造が赤黒木なようです。
これによって以下の性能が担保されます。
- n個の要素を含む木の高さが2logn以下になる
- add・removeが最悪でもO(logn)の時間で実行できる