差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:data_structure:redblacktree [2019/11/15] – [平衡二分探索木] ikatakos | programming_algorithm:data_structure:balancing_binary_search_tree:redblacktree [2019/11/28] (現在) – ikatakos | ||
---|---|---|---|
行 2: | 行 2: | ||
=====概要===== | =====概要===== | ||
- | |||
- | ====平衡二分探索木==== | ||
- | |||
- | 値の大小を昇順に保ったまま要素を追加・削除できるデータ構造として、[[wpjp> | ||
- | 各ノードは最大2つまでの子を持ち、左の子は自身より小さく、右の子は大きい。 | ||
- | |||
- | 7 | ||
- | / \ | ||
- | 5 9 | ||
- | / | ||
- | 1 6 8 | ||
- | \ | ||
- | 3 | ||
- | |||
- | こうすると、追加・削除を繰り返しながらも、常にソートされた状態が保たれる。 | ||
- | 通常の配列にソート状態を保ちつつ追加・削除するには $O(N)$ 必要だが、平衡二分木では期待値 $O(\log{N})$ で可能になる。 | ||
- | |||
- | 具体的には、例えば以下のことが可能になる。 | ||
- | |||
- | * 左の子→自分→右の子、と通りがけ順に探索することで、小さい順に列挙 | ||
- | * $k$ 番目に大きい要素の検索 | ||
- | * $m$ より大きい最小の要素(upper_bound)などの検索 | ||
- | * ある値を境に木を分割 / ある値未満の要素と、ある値以上の要素からなる2つの木をマージ | ||
- | |||
- | しかし、データを追加する順によっては左/ | ||
- | |||
- | 1 | ||
- | \ | ||
- | 3 | ||
- | \ | ||
- | 5 | ||
- | \ ... | ||
- | |||
- | そこで、適宜「回転」を加えるなどのテクニックを実装して、なるべく木の高さを低く保つようにした木を、[[wpjp> | ||
- | |||
- | 7 | ||
- | /\ | ||
- | | ||
- | / | ||
- | 15913 | ||
- | |||
- | [[wpjp> | ||
- | |||
- | ====赤黒木==== | ||
平衡探索二分木の一種で、以下を満たすように木を保つ。 | 平衡探索二分木の一種で、以下を満たすように木を保つ。 |