差分
この文書の現在のバージョンと選択したバージョンの差分を表示します。
|
programming_algorithm:data_structure:balancing_binary_search_tree [2019/11/28] ikatakos 作成 |
programming_algorithm:data_structure:balancing_binary_search_tree [2019/11/28] (現在) ikatakos |
||
|---|---|---|---|
| ライン 2: | ライン 2: | ||
| * [[wpjp>平衡二分探索木]] | * [[wpjp>平衡二分探索木]] | ||
| + | |||
| + | |||
| + | =====概要===== | ||
| + | |||
| + | 値の大小を昇順に保ったまま要素を追加・削除できるデータ構造として、[[wpjp>二分探索木]]がある。 | ||
| + | 各ノードは最大2つまでの子を持ち、左の子は自身より小さく、右の子は大きい。 | ||
| + | |||
| + | ７ | ||
| + | ／ ＼ | ||
| + | ５ ９ | ||
| + | / \ / | ||
| + | １ ６ ８ | ||
| + | \ | ||
| + | ３ | ||
| + | |||
| + | こうすると、追加・削除を繰り返しながらも、常にソートされた状態が保たれる。 | ||
| + | 通常の配列にソート状態を保ちつつ追加・削除するには $O(N)$ 必要だが、平衡二分木では期待値 $O(\log{N})$ で可能になる。 | ||
| + | |||
| + | 具体的には、例えば以下のことが可能になる。 | ||
| + | |||
| + | * 左の子→自分→右の子、と通りがけ順に探索することで、小さい順に列挙 | ||
| + | * $k$ 番目に大きい要素の検索 | ||
| + | * $m$ より大きい最小の要素(upper_bound)などの検索 | ||
| + | * ある値を境に木を分割 | ||
| + | * $X$ 未満の要素と、$X$ 以上の要素からなる2つの木をマージ | ||
| + | |||
| + | しかし、データを追加する順によっては左/右の枝にばかりデータが伸びる。これでは検索するにも線形探索と変わらなくなってしまう。 | ||
| + | |||
| + | １ | ||
| + | ＼ | ||
| + | ３ | ||
| + | ＼ | ||
| + | ５ | ||
| + | ＼ ... | ||
| + | |||
| + | そこで、適宜「回転」を加えるなどのテクニックを実装して、なるべく木の高さを低く保つようにした木を、[[wpjp>平衡二分探索木]]という。 | ||
| + | |||
| + | ７ | ||
| + | ／＼ | ||
| + | ３ 11 | ||
| + | /\ /\ | ||
| + | １５９13 | ||
| + | |||
| + | [[wpjp>AVL木]]、[[wpjp>赤黒木]]、[[wpjp>AA木]]などがある。 | ||
