差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:data_structure:redblacktree [2019/10/06] – [実装] ikatakos | programming_algorithm:data_structure:balancing_binary_search_tree:redblacktree [2019/11/28] (現在) – ikatakos | ||
|---|---|---|---|
| 行 2: | 行 2: | ||
| =====概要===== | =====概要===== | ||
| - | |||
| - | ====平衡二分探索木==== | ||
| - | |||
| - | 値の大小を昇順に保ったまま要素を追加・削除できるデータ構造として、[[wpjp> | ||
| - | 各ノードは最大2つまでの子を持ち、左の子は自身より小さく、右の子は大きい。 | ||
| - | |||
| - | ７ | ||
| - | ／ ＼ | ||
| - | ５ ９ | ||
| - | / | ||
| - | １ ６ ８ | ||
| - | \ | ||
| - | ３ | ||
| - | |||
| - | こうすると、追加・削除を繰り返しながら「今、3番目に大きな数字」「今、4より大きい最小の数字」などの検索クエリに対応できる。 | ||
| - | |||
| - | しかし、データを追加する順によっては左/ | ||
| - | |||
| - | １ | ||
| - | ＼ | ||
| - | ３ | ||
| - | ＼ | ||
| - | ５ | ||
| - | ＼ ... | ||
| - | |||
| - | そこで、適宜「回転」を加えるなどのテクニックを実装して、なるべく木の高さを低く保つようにした木を、[[wpjp> | ||
| - | |||
| - | ７ | ||
| - | ／＼ | ||
| - | | ||
| - | / | ||
| - | １５９13 | ||
| - | |||
| - | [[wpjp> | ||
| - | |||
| - | ====赤黒木==== | ||
| 平衡探索二分木の一種で、以下を満たすように木を保つ。 | 平衡探索二分木の一種で、以下を満たすように木を保つ。 | ||
