差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:redblacktree [2019/09/13] – [赤黒木] ikatakos | programming_algorithm:data_structure:redblacktree [2019/11/15] – [平衡二分探索木] ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
=====概要===== | =====概要===== | ||
- | ====二分探索木==== | + | ====平衡二分探索木==== |
値の大小を昇順に保ったまま要素を追加・削除できるデータ構造として、[[wpjp> | 値の大小を昇順に保ったまま要素を追加・削除できるデータ構造として、[[wpjp> | ||
行 16: | 行 16: | ||
3 | 3 | ||
- | こうすると、追加・削除を繰り返しながら「今、3番目に大きな数字」「今、4より大きい最小の数字」などの検索クエリに対応できる。 | + | こうすると、追加・削除を繰り返しながらも、常にソートされた状態が保たれる。 |
+ | 通常の配列にソート状態を保ちつつ追加・削除するには $O(N)$ 必要だが、平衡二分木では期待値 $O(\log{N})$ で可能になる。 | ||
- | しかし、データを追加する順によっては左/ | + | 具体的には、例えば以下のことが可能になる。 |
+ | |||
+ | * 左の子→自分→右の子、と通りがけ順に探索することで、小さい順に列挙 | ||
+ | * $k$ 番目に大きい要素の検索 | ||
+ | * $m$ より大きい最小の要素(upper_bound)などの検索 | ||
+ | * ある値を境に木を分割 / ある値未満の要素と、ある値以上の要素からなる2つの木をマージ | ||
+ | |||
+ | しかし、データを追加する順によっては左/ | ||
1 | 1 | ||
行 27: | 行 35: | ||
\ ... | \ ... | ||
- | そこで、適宜「回転」を加えるなど、なるべく木の高さを低く保つテクニックがある。 | + | そこで、適宜「回転」を加えるなどのテクニックを実装して、なるべく木の高さを低く保つようにした木を、[[wpjp> |
- | このテクニックを実装した木を、[[wpjp> | + | |
7 | 7 | ||
行 40: | 行 47: | ||
====赤黒木==== | ====赤黒木==== | ||
- | 以下を満たすように木を保つ。 | + | 平衡探索二分木の一種で、以下を満たすように木を保つ。 |
* 各ノードを赤と黒で(仮想的に)塗り分ける | * 各ノードを赤と黒で(仮想的に)塗り分ける | ||
行 47: | 行 54: | ||
* 根からそれぞれの葉までの経路上にある黒の個数は等しい | * 根からそれぞれの葉までの経路上にある黒の個数は等しい | ||
- | いろいろパターン分けがあってややこしいけど、限られた3~4ノードの色のパターンを見ることで、適切に状態を保てる。 | + | こんなことを決めて何がいいのかと、 |
+ | |||
+ | * これが満たされている木では、根から最短経路(黒黒黒……)と最長経路(黒赤黒赤……)の差は2倍を超えないので、ほどよい平衡が保たれることが保証される | ||
+ | * データを追加したり削除したりするとき、親子で繋がった直近3~4ノードの色のパターンを見て塗り替えることで状態を維持できる | ||
+ | * その中だけで状態を解消できないときは親に遡ることはあるが、再帰的に実装できる | ||
+ | |||
+ | ただ、パターン分けは結構種類があってややこしい。 | ||
詳細は参考の1つめのサイトが丁寧に場合分けを説明されている。 | 詳細は参考の1つめのサイトが丁寧に場合分けを説明されている。 | ||
行 56: | 行 69: | ||
=====実装===== | =====実装===== | ||
- | 再帰関数は極力無くした実装(1箇所だけ、多重再帰にはならない箇所で使用)。どうしても配列アクセスは多くなるので、Pythonだと遅い。PyPyならまぁまぁ。 | + | 再帰関数は極力無くした実装(1箇所だけ、多重再帰にはならない箇所で使用)。どうしても配列アクセスは多くなるので、Pythonだと遅い。PyPyなら……速いとは言えないが、まぁまぁ。 |
^関数^返値^概要^ | ^関数^返値^概要^ | ||
行 181: | 行 194: | ||
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 |