差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:data_structure:redblacktree [2019/09/13] – [平衡二分探索木] ikatakos | programming_algorithm:data_structure:balancing_binary_search_tree:redblacktree [2019/11/28] (現在) – ikatakos | ||
|---|---|---|---|
| 行 3: | 行 3: | ||
| =====概要===== | =====概要===== | ||
| - | ====平衡二分探索木==== | + | 平衡探索二分木の一種で、以下を満たすように木を保つ。 |
| - | + | ||
| - | 値の大小を昇順に保ったまま要素を追加・削除できるデータ構造として、[[wpjp> | + | |
| - | 各ノードは最大2つまでの子を持ち、左の子は自身より小さく、右の子は大きい。 | + | |
| - | + | ||
| - | ７ | + | |
| - | ／ ＼ | + | |
| - | ５ ９ | + | |
| - | / | + | |
| - | １ ６ ８ | + | |
| - | \ | + | |
| - | ３ | + | |
| - | + | ||
| - | こうすると、追加・削除を繰り返しながら「今、3番目に大きな数字」「今、4より大きい最小の数字」などの検索クエリに対応できる。 | + | |
| - | + | ||
| - | しかし、データを追加する順によっては左/ | + | |
| - | + | ||
| - | １ | + | |
| - | ＼ | + | |
| - | ３ | + | |
| - | ＼ | + | |
| - | ５ | + | |
| - | ＼ ... | + | |
| - | + | ||
| - | そこで、適宜「回転」を加えるなどのテクニックを実装して、なるべく木の高さを低く保つようにした木を、[[wpjp> | + | |
| - | + | ||
| - | ７ | + | |
| - | ／＼ | + | |
| - | | + | |
| - | / | + | |
| - | １５９13 | + | |
| - | + | ||
| - | [[wpjp> | + | |
| - | + | ||
| - | ====赤黒木==== | + | |
| - | + | ||
| - | 以下を満たすように木を保つ。 | + | |
| * 各ノードを赤と黒で（仮想的に）塗り分ける | * 各ノードを赤と黒で（仮想的に）塗り分ける | ||
| 行 46: | 行 10: | ||
| * 根からそれぞれの葉までの経路上にある黒の個数は等しい | * 根からそれぞれの葉までの経路上にある黒の個数は等しい | ||
| - | いろいろパターン分けがあってややこしいけど、平衡が崩れても、限られた3～4ノードの色のパターンを見ることで適切に状態を保てる。 | + | こんなことを決めて何がいいのかと、 |
| + | |||
| + | * これが満たされている木では、根から最短経路（黒黒黒……）と最長経路（黒赤黒赤……）の差は2倍を超えないので、ほどよい平衡が保たれることが保証される | ||
| + | * データを追加したり削除したりするとき、親子で繋がった直近3～4ノードの色のパターンを見て塗り替えることで状態を維持できる | ||
| + | * その中だけで状態を解消できないときは親に遡ることはあるが、再帰的に実装できる | ||
| + | |||
| + | ただ、パターン分けは結構種類があってややこしい。 | ||
| 詳細は参考の1つめのサイトが丁寧に場合分けを説明されている。 | 詳細は参考の1つめのサイトが丁寧に場合分けを説明されている。 | ||
| 行 180: | 行 150: | ||
| node[2] = min_node[2] | node[2] = min_node[2] | ||
| node = min_node | node = min_node | ||
| + | |||
| + | # Delete node is root | ||
| + | if not stack: | ||
| + | if node[0][2] == self.EOT: | ||
| + | self.root = node[1] | ||
| + | else: | ||
| + | self.root = node[0] | ||
| + | self.root[3] = 0 | ||
| + | return | ||
| # Decrease count | # Decrease count | ||
