【ITニュース解説】How Insertion Works in Red-Black Trees

Red-Black Tree（レッドブラックツリー）は、データの追加や削除が行われても、常に木構造のバランスを保とうとする特別な種類の二分探索木である。通常の二分探索木では、データが特定の順序で追加されると、木が片側に偏ってしまい、データの検索や操作に時間がかかってしまうことがある。しかし、RBツリーはこのような偏りを自動的に修正する「自己平衡」の仕組みを備えている。特に、データの追加や削除が頻繁に行われるようなシステムでその真価を発揮する。

RBツリーの各ノードは、「赤」または「黒」のいずれかの色を持つ。この色のルールが、ツリーのバランスを保つための鍵となる。RBツリーには、主に二つの重要な特性がある。

一つ目の特性は「赤プロパティ」である。これは「赤いノードは赤い子ノードを持てない」というルールだ。言い換えれば、連続して二つの赤いノードが現れることは許されない。これにより、ツリーが極端に浅くなることを防ぐ。

二つ目の特性は「黒プロパティ」である。これは「任意のノードから、その子孫であるnullノード（実体のない終端ノード）までのすべての経路において、含まれる黒いノードの数が同じである」というルールだ。この特性によって、ツリーの経路の長さが極端に異なることを防ぎ、結果としてツリーが大きく偏るのを防ぐ。この二つのルールに加え、新しいノードは常に赤色で挿入され、ツリーの根（ルート）ノードは常に黒色であるという決まりもある。

これらのルールがどのように守られながら、新しいノードがツリーに追加されるのかを見ていこう。新しいノードを挿入する際、まず通常の二分探索木と同じように、適切な位置にノードを配置する。この時、新しいノードの色は常に赤とする。

もし挿入されたノードがツリーの根ノードであれば、そのノードは黒色に変更される。また、もし挿入されたノードの親ノードが黒色であれば、赤色の新しいノードがその下に挿入されても「赤プロパティ」（赤いノードは赤い子を持てない）に違反しないため、特別な調整は必要なく、そのまま挿入が完了する。

問題が発生するのは、挿入されたノードの親ノードが赤色である場合だ。この状況では、「赤プロパティ」に違反してしまう。なぜなら、親ノードが赤色で、新しく挿入された子ノードも赤色であるため、連続する二つの赤いノードができてしまうからだ。この違反を解決するために、RBツリーはノードの色を変更したり、ツリーの構造を「回転」させたりする操作を行う。

親ノードが赤色である場合、次に親ノードの兄弟ノード（「叔父」ノードとも呼ばれる）の色を確認する。

親ノードの兄弟ノードが赤色の場合 この場合、親ノードとその兄弟ノード（両方とも赤色）を黒色に変更し、祖父ノードを赤色に変更する。これにより、連続する赤ノードの違反は解消される。ただし、もし祖父ノードがツリーの根ノードであった場合は、根ノードは常に黒であるというルールに従い、赤色には変更せず黒色のままにしておく。祖父ノードが根ノードでない場合、祖父ノードが赤色になったことで、その祖父ノードの親ノード（元のひい祖父ノード）が赤色であれば、再び「赤プロパティ」の違反が発生する可能性がある。その場合は、この操作を祖父ノードを対象として再帰的に繰り返すことになる。この一連の操作は「リカラーリング」と呼ばれ、ノードの色を変更することでツリーのバランスを調整する。

親ノードの兄弟ノードが黒色の場合 このケースでは、色の変更だけではバランスを保つことが難しい。そのため、ツリーの構造を物理的に変更する「回転」という操作が必要になる。回転とは、ノードの親子関係や兄弟関係を再配置し、木の構造を調整する操作である。回転には主に4つのサブケースがある。

1. 左-左 (Left Left) ケース: これは、祖父ノードの左の子ノードの、さらに左の子ノードとして新しいノードが挿入された状況だ。親ノードが赤色で、その兄弟ノードが黒色という条件を満たす。この場合、祖父ノードに対して「右回転」を行う。右回転を行うと、元の親ノードが新しい祖父ノードの位置に来て、元の祖父ノードはその右の子ノードとなる。回転後、新しい祖父ノード（元は親ノード）と、その右の子ノード（元は祖父ノード）の色を交換する。これにより、連続する赤ノードの違反が解消され、黒ノードのパスの長さも維持される。例えば、祖父が25、親が20、新しいノードが8で、8が20の左の子として挿入された場合、25に対して右回転を行い、20が新しい根となり、20と25の色を交換する。

2. 左-右 (Left Right) ケース: これは、祖父ノードの左の子ノードの、右の子ノードとして新しいノードが挿入された状況だ。ここでも親ノードは赤色で、その兄弟ノードは黒色である。この場合、まず親ノードに対して「左回転」を行う。これにより、新しいノードが親ノードの位置に来て、親ノードがその左の子ノードとなる。この操作によって、ツリーの構造は「左-左」ケースと似た形に変換される。その後は、「左-左」ケースと同様に、祖父ノードに対して右回転を行い、新しい祖父ノード（元の新しいノード）と、その右の子ノード（元の祖父ノード）の色を交換する。例えば、祖父が25、親が20、新しいノードが21で、21が20の右の子として挿入された場合、まず20に対して左回転を行うと、21が20の親となり、次に25に対して右回転を行い、21が新しい根となり、21と25の色を交換する。

3. 右-右 (Right Right) ケース: これは、祖父ノードの右の子ノードの、さらに右の子ノードとして新しいノードが挿入された状況だ。親ノードが赤色で、その兄弟ノードが黒色である。この場合、「左-左」ケースとは逆で、祖父ノードに対して「左回転」を行う。左回転を行うと、元の親ノードが新しい祖父ノードの位置に来て、元の祖父ノードはその左の子ノードとなる。回転後、新しい祖父ノード（元は親ノード）と、その左の子ノード（元は祖父ノード）の色を交換する。例えば、祖父が25、親が28、新しいノードが30で、30が28の右の子として挿入された場合、25に対して左回転を行い、28が新しい根となり、28と25の色を交換する。

4. 右-左 (Right Left) ケース: これは、祖父ノードの右の子ノードの、左の子ノードとして新しいノードが挿入された状況だ。親ノードは赤色で、その兄弟ノードは黒色である。この場合、「左-右」ケースと同様に、まず親ノードに対して「右回転」を行う。これにより、新しいノードが親ノードの位置に来て、親ノードがその右の子ノードとなる。この操作によって、ツリーの構造は「右-右」ケースと似た形に変換される。その後は、「右-右」ケースと同様に、祖父ノードに対して左回転を行い、新しい祖父ノード（元の新しいノード）と、その左の子ノード（元の祖父ノード）の色を交換する。例えば、祖父が28、親が32、新しいノードが30で、30が32の左の子として挿入された場合、まず32に対して右回転を行うと、30が32の親となり、次に28に対して左回転を行い、30が新しい根となり、30と28の色を交換する。

これらの色変更と回転の操作を組み合わせることで、Red-Black Treeは新しいノードが挿入されても、常に「連続する赤いノードがないこと」と「すべての経路で黒ノードの数が同じであること」という二つの重要なルールを維持する。これにより、ツリーは常に効率的なバランスを保ち、データの検索や操作が高速に行える状態を自動的に維持できる。この複雑な仕組みによって、Red-Black Treeは非常に堅牢で信頼性の高いデータ構造として、多くのシステムで利用されている。