差分
このページの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フラグとなる。 |
+ | これに従って | ||
追加・削除も似たような感じで行える。 | 追加・削除も似たような感じで行える。 |