一種で、以下を満たすように木を保つ。赤の子は黒(赤は2つ以上連続しない)根からそれぞれの葉までの経路上にある黒の個数は等しいこんなことを決めて何がいいのかと、これが満たされている木では、根から最短経路(黒黒黒......)と最長経路(黒赤黒赤......)の差は2倍を超えないので、ほどよい平衡が保たれることが保証されるデータを追加したり削除したりするとき、親子で繋がった直近3~4ノードの色のパターンを見て塗り替えることで状態を維持できるその中だけで状態を解消できないときは親に遡ることはあるが、再帰的に実装できるただ、パターン分けは結構種類があってややこしい。詳細は参考の1つめのサイトが丁寧に場合分けを説明されている。再帰関数は極力無くした実装(1箇所だけ、多重再帰にはならない箇所で使用)。しても配列アクセスは多くなるので、Pythonだと遅い。PyPyなら......速いとは言えないが、まぁまぁ。追加(実装によっては重複する値を許さないこともできる。ikatakosメディアマネージャー文書の先頭へ。