差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:data_structure:trie [2022/05/08] – [Binary Trie] ikatakos | programming_algorithm:data_structure:trie [2022/05/08] (現在) – [操作] ikatakos | ||
|---|---|---|---|
| 行 145: | 行 145: | ||
| 根ノードから辿り、検索したい値 $X$ の下位から照合していく。 | 根ノードから辿り、検索したい値 $X$ の下位から照合していく。 | ||
| - | 現在いるノード $i$ の、階層のswapフラグ $W_d$ と、ノード固有のswapフラグ $D_i$ をあわせたもの $W_d \oplus D_i$ が、次の子に遷移する際のswapフラグとなる。これに従って子に遷移することを繰り返し、深さ $d_{max}$ までたどれたら存在有無がわかる。 | + | 現在いるノード $i$ の、階層のswapフラグ $W_d$ と、ノード固有のswapフラグ $D_i$ をあわせたもの $W_d \oplus D_i$ が、次の子に遷移する際のswapフラグとなる。 |
| + | これに従って | ||
| 追加・削除も似たような感じで行える。 | 追加・削除も似たような感じで行える。 | ||
| 行 189: | 行 190: | ||
| 根ノードから子をたどるのは値の検索などと一緒。 | 根ノードから子をたどるのは値の検索などと一緒。 | ||
| - | どちらの子を辿るかを、$a$ に従うところが異なる。 | + | どちらの子を辿るかを、初期状態での枝に従うところが異なる。 |
| 初期状態（下図で言うなら、左の枝が0、右の枝が1）だとして、$a=3$ なら、右、右、左と辿っていくことになる。 | 初期状態（下図で言うなら、左の枝が0、右の枝が1）だとして、$a=3$ なら、右、右、左と辿っていくことになる。 | ||
