差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

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つまでの子を持ち、左の子は自身より小さく、右の子は大きい。
 +
 +        7
 +      /  \
 +    5      9
 +   / ​ \    /
 +  1  6  8
 +   \
 +   3
 +
 +こうすると、追加・削除を繰り返しながらも、常にソートされた状態が保たれる。
 +通常の配列にソート状態を保ちつつ追加・削除するには $O(N)$ 必要だが、平衡二分木では期待値 $O(\log{N})$ で可能になる。
 +
 +具体的には、例えば以下のことが可能になる。
 +
 +  * 左の子→自分→右の子、と通りがけ順に探索することで、小さい順に列挙
 +  * $k$ 番目に大きい要素の検索
 +  * $m$ より大きい最小の要素(upper_bound)などの検索
 +  * ある値を境に木を分割
 +  * $X$ 未満の要素と、$X$ 以上の要素からなる2つの木をマージ
 +
 +しかし、データを追加する順によっては左/​右の枝にばかりデータが伸びる。これでは検索するにも線形探索と変わらなくなってしまう。
 +
 +    1
 +     \
 +      3
 +       \
 +        5
 +         \ ...
 +
 +そこで、適宜「回転」を加えるなどのテクニックを実装して、なるべく木の高さを低く保つようにした木を、[[wpjp>​平衡二分探索木]]という。
 +
 +     7
 +    /\
 +   ​3 ​ 11
 +   /​\ ​ /\
 +  15913
 +
 +[[wpjp>​AVL木]]、[[wpjp>​赤黒木]]、[[wpjp>​AA木]]などがある。
  
  
programming_algorithm/data_structure/balancing_binary_search_tree.txt · 最終更新: 2019/11/28 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0