受け入れられた回答で言及されている本にアクセスできないこのスレッドを読んでいる他の人の利益のために、ここに私が受け入れられる説明的な回答になることを願っています。
回転すると、ツリーは色を変更する基準を満たす状態になります (子ノードには赤いおじがあります)。主な違いは 2 つあります。
- どのノードが「子」で、どのノードが「叔父」であるかが変更されました。
- 親と叔父を黒に、祖父母を赤に変更する代わりに、親を赤に、祖父母を黒に変更します。
子ノードに赤い叔父がいない場合、叔父ノードがすでに黒の場合、親を黒にすると、祖父母の片側だけで黒の高さが 1 増加するため、回転する必要があります。これは、赤黒木の高さ不変の性質に違反し、木のバランスを崩します。
次に、回転によってツリーがどのように変換されるかを見てみましょう。これにより、赤の叔父を持つ子ノードが作成され、色の変更を使用できるようになります。それを完全に理解するためにこれを描くことをお勧めします。
- x を赤の親を持つ現在の赤のノードとします。
- 回転前に p を x の赤の親とします (親が黒の場合は、既に完了しています)。
- y を回転前の x の黒の叔父とします (叔父が赤の場合、回転は必要ありません。親と叔父を黒に、祖父母を赤に変更するだけです)。
- 回転前の x の黒の祖父母を g とします (親が赤なので、祖父母は黒でなければなりません。そうでなければ、これはそもそも赤黒木ではありませんでした。)
- 左-左 (LL) または右-右 (RR) ケースの場合 (つまり、x が p の左の子で、p が g の左の子である、または x が p の右の子で、p が右の子である) g の子)、1 回回転した後 (LL の場合は右、RR の場合は左)、y は子になり、x はその叔父になります。x は赤いおじなので、これで色を変更できるケースができました。したがって、子の親 (子は現在 y であるため、その親は g) を赤に、子の祖父母 (現在は p) を黒に色変更します。
- LR (x が左の子、または p で p が g の右の子) または RL の場合 (x が p の右の子で、p が g の左の子) の場合、2 回回転した後 (右からLR の場合は左、RL の場合は左から右)、y は子になり、p はその叔父になります。p は赤いおじさんなので、再び色を変更できる場合があります。したがって、親 (子は現在 y であるため、その親は g) を赤に、子の祖父母 (現在は x) を黒に色変更します。
回転と色の変更の前に、A 側 (左または右) に 2 つの赤いノードと 0 つの黒いノード、B 側 (サイド A の反対側) に 0 つの赤いノードと 1 つの黒いノードを持つ黒い祖父母がありました。回転と色の変更後、A 側に 1 つの赤いノードと 0 つの黒いノードがあり、B 側に 1 つの赤いノードと 1 つの黒いノードを持つ黒い祖父母があります。サブツリーの黒の高さを増やさずに祖父母。
それが回転の魔法です。これにより、黒の高さを変更せずに余分な赤いノードを別のブランチに移動でき、二分探索木のソートされたトラバーサル プロパティを保持できます。