差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:redblacktree [2019/09/13] – [平衡二分探索木] ikatakos | programming_algorithm:data_structure:redblacktree [2019/09/19] – ikatakos | ||
---|---|---|---|
行 39: | 行 39: | ||
====赤黒木==== | ====赤黒木==== | ||
- | 以下を満たすように木を保つ。 | + | 平衡探索二分木の一種で、以下を満たすように木を保つ。 |
* 各ノードを赤と黒で(仮想的に)塗り分ける | * 各ノードを赤と黒で(仮想的に)塗り分ける | ||
行 46: | 行 46: | ||
* 根からそれぞれの葉までの経路上にある黒の個数は等しい | * 根からそれぞれの葉までの経路上にある黒の個数は等しい | ||
- | いろいろパターン分けがあってややこしいけど、平衡が崩れても、限られた3~4ノードの色のパターンを見ることで適切に状態を保てる。 | + | こんなことを決めて何がいいのかと、 |
+ | |||
+ | * これが満たされている木では、根から最短経路(黒黒黒……)と最長経路(黒赤黒赤……)の差は2倍を超えないので、ほどよい平衡が保たれることが保証される | ||
+ | * データを追加したり削除したりするとき、親子で繋がった直近3~4ノードの色のパターンを見て塗り替えることで状態を維持できる | ||
+ | * その中だけで状態を解消できないときは親に遡ることはあるが、再帰的に実装できる | ||
+ | |||
+ | ただ、パターン分けは結構種類があってややこしい。 | ||
詳細は参考の1つめのサイトが丁寧に場合分けを説明されている。 | 詳細は参考の1つめのサイトが丁寧に場合分けを説明されている。 | ||