平衡二分探索木

概要

値の大小を昇順に保ったまま要素を追加・削除できるデータ構造として、二分探索木がある。 各ノードは最大2つまでの子を持ち、左の子は自身より小さく、右の子は大きい。

      7
    /  \
  5      9
 /  \    /
1  6  8
 \
 3

こうすると、追加・削除を繰り返しながらも、常にソートされた状態が保たれる。 通常の配列にソート状態を保ちつつ追加・削除するには $O(N)$ 必要だが、平衡二分木では期待値 $O(\log{N})$ で可能になる。

具体的には、例えば以下のことが可能になる。

  • 左の子→自分→右の子、と通りがけ順に探索することで、小さい順に列挙
  • $k$ 番目に大きい要素の検索
  • $m$ より大きい最小の要素(upper_bound)などの検索
  • ある値を境に木を分割
  • $X$ 未満の要素と、$X$ 以上の要素からなる2つの木をマージ

しかし、データを追加する順によっては左/右の枝にばかりデータが伸びる。これでは検索するにも線形探索と変わらなくなってしまう。

  1
   \
    3
     \
      5
       \ ...

そこで、適宜「回転」を加えるなどのテクニックを実装して、なるべく木の高さを低く保つようにした木を、平衡二分探索木という。

   7
  /\
 3  11
 /\  /\
15913

AVL木赤黒木AA木などがある。

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
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