Red black treeによるRopeの実装を考えてみる。

値をRopeに追加するときに木の高さが2つ増えるときがある。その場合を考えると平衡化の場合分けはこんな感じかしら。ごちゃごちゃして見えるけれども、処理は二重回転、一重回転、色変えの3種類だけなので実装はこの場合分けの見た目ほどには複雑にならないはず。



ロープを切り出すときにノードを結合する処理が必要になる。
木の一番上のノードをルートと呼ぶことにして、木の一番下のノードをリーフと呼ぶことにする。
ルートからあるノードまでの距離を深さと呼ぶことにして、リーフからあるノードまでの距離を高さと呼ぶことにする。



ルートからあるノードまでに存在する黒ノードの数を黒の深さと呼ぶことにする。
Red black treeの結合はこの黒の深さを算出して、結合するノード同士の黒の深さを合わせることによってできるんじゃないかしらとそんなことを考えているのだけれども、どうだろ。