[[赤黒木]]

差分

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

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

両方とも前のリビジョン 前のリビジョン
programming_algorithm:data_structure:balancing_binary_search_tree:redblacktree [2019/11/28]
ikatakos ↷ programming_algorithm:data_structure:redblacktree:balancing_binary_search_tree から programming_algorithm:data_structure:balancing_binary_search_tree:redblacktree へページの移動と名称変更しました。
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 
-    /\ 
-   ​3 ​ 11 
-   /​\ ​ /\ 
-  15913 
- 
-[[wpjp>​AVL木]]、[[wpjp>​赤黒木]]、[[wpjp>​AA木]]などがある。 
- 
-====赤黒木==== 
  
 平衡探索二分木の一種で、以下を満たすように木を保つ。 平衡探索二分木の一種で、以下を満たすように木を保つ。
programming_algorithm/data_structure/balancing_binary_search_tree/redblacktree.txt · 最終更新: 2019/11/28 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0