差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:redblacktree [2019/09/19] – ikatakos | programming_algorithm:data_structure:redblacktree [2019/11/15] – [平衡二分探索木] ikatakos | ||
|---|---|---|---|
| 行 16: | 行 16: | ||
| ３ | ３ | ||
| - | こうすると、追加・削除を繰り返しながら「今、3番目に大きな数字」「今、4より大きい最小の数字」などの検索クエリに対応できる。 | + | こうすると、追加・削除を繰り返しながらも、常にソートされた状態が保たれる。 |
| + | 通常の配列にソート状態を保ちつつ追加・削除するには $O(N)$ 必要だが、平衡二分木では期待値 $O(\log{N})$ で可能になる。 | ||
| - | しかし、データを追加する順によっては左/ | + | 具体的には、例えば以下のことが可能になる。 |
| + | |||
| + | * 左の子→自分→右の子、と通りがけ順に探索することで、小さい順に列挙 | ||
| + | * $k$ 番目に大きい数字の検索 | ||
| + | * $m$ より大きい最小の数字(upper_bound)などの検索 | ||
| + | * ある値を境に木を分割 / ある値未満とある値以上からなる木をマージ | ||
| + | |||
| + | しかし、データを追加する順によっては左/ | ||
| １ | １ | ||
| 行 186: | 行 194: | ||
| node[2] = min_node[2] | node[2] = min_node[2] | ||
| node = min_node | node = min_node | ||
| + | |||
| + | # Delete node is root | ||
| + | if not stack: | ||
| + | if node[0][2] == self.EOT: | ||
| + | self.root = node[1] | ||
| + | else: | ||
| + | self.root = node[0] | ||
| + | self.root[3] = 0 | ||
| + | return | ||
| # Decrease count | # Decrease count | ||
