差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:data_structure:trie [2019/02/27] – ikatakos | programming_algorithm:data_structure:trie [2022/05/08] (現在) – [操作] ikatakos | ||
---|---|---|---|
行 97: | 行 97: | ||
return ret | return ret | ||
</ | </ | ||
+ | |||
+ | |||
+ | ===== 逆Binary Trie ===== | ||
+ | |||
+ | ちょっと特殊だが、上位桁でなく、1の位から順に構築したTrie。\\ | ||
+ | 管理する2進数での最大桁を $d_{max}$ として、 | ||
+ | |||
+ | * 値の追加: | ||
+ | * 値の削除: | ||
+ | * 値の検索: | ||
+ | * 全体に特定の値をXORする操作: | ||
+ | * 大小比較はできなくなる | ||
+ | * 代わりに、全体に1を足す操作を $O(d_{max})$ でできる | ||
+ | |||
+ | たくさんの値に、同時にXORや1を足す操作を行った後、各値がそれぞれ何になっているか、を高速に得たい場合に使える。 | ||
+ | |||
+ | ==== 構造 ==== | ||
+ | |||
+ | $d_{max}$ は、「+1されて繰り上がりが発生した後」も含めての最大桁であることが望ましい。\\ | ||
+ | その上で、先頭の' | ||
+ | |||
+ | (先頭の' | ||
+ | |||
+ | ○ | ||
+ | 0/ \1 | ||
+ | | ||
+ | 0/ \1 | ||
+ | ○ | ||
+ | 0/\1 0/\1 0/\1 0/\1 | ||
+ | | ||
+ | 000 010 001 011 | ||
+ | | ||
+ | |||
+ | XORや1を足す操作は、既存のTrie構造を変えること無く、 | ||
+ | 各ノードから左右に伸びる辺のどちらが0でどちらが1か、をswapするだけで表現できる。 | ||
+ | |||
+ | 以下の2箇所で、0-1のswapフラグを管理する。 | ||
+ | |||
+ | * 階層に対するswap状況を管理する、長さ $d_{max}$ のbool配列 $W=(W_0~W_{dmax-1})$ | ||
+ | * ノードごとに、自身の直下の0-1のswap状況を管理するbool変数 $D_i$ | ||
+ | |||
+ | |||
+ | ==== 操作 ==== | ||
+ | |||
+ | === 値の検索 === | ||
+ | |||
+ | 根ノードから辿り、検索したい値 $X$ の下位から照合していく。 | ||
+ | |||
+ | 現在いるノード $i$ の、階層のswapフラグ $W_d$ と、ノード固有のswapフラグ $D_i$ をあわせたもの $W_d \oplus D_i$ が、次の子に遷移する際のswapフラグとなる。 | ||
+ | これに従って $X$ に対応する子に遷移することを繰り返し、深さ $d_{max}$ までたどれたら存在有無がわかる。 | ||
+ | |||
+ | 追加・削除も似たような感じで行える。 | ||
+ | |||
+ | |||
+ | === 全体にXOR === | ||
+ | |||
+ | これは単純に、$W$ にXORを反映させればよい。 | ||
+ | |||
+ | === 1を足す === | ||
+ | |||
+ | 根ノードからスタートし、$W_d \oplus D_i$ によってどちらの枝が0-1を表すかを確認しながら子を辿るのは検索と同じ。 | ||
+ | |||
+ | たとえば根ノードについては、1を足すと、0の枝は1になり、1の枝は0になった上で次の桁へ繰り上がる。\\ | ||
+ | つまり、swapされることになる。 | ||
+ | |||
+ | (足す前の)1の枝を辿り、同じことを繰り返していく。 | ||
+ | |||
+ | (例)1を足す前の状態 | ||
+ | ○ | ||
+ | 0/ \1 | ||
+ | | ||
+ | 0/ \1 | ||
+ | ○ | ||
+ | 0/\1 1/\0 0/\1 0/\1 | ||
+ | | ||
+ | | ||
+ | 1を足した後の状態 | ||
+ | ○ | ||
+ | | ||
+ | | ||
+ | 0/ \1 [0/ \1] | ||
+ | ○ | ||
+ | 0/\1 1/ | ||
+ | | ||
+ | (⑧) | ||
+ | |||
+ | ⑧に関しては、オーバーフローして⓪になっている(こういうことを防ぐため、$d_{max}$ はそれを含めての最大桁を設定した方が良い)が、他は、きちんと1ずつ足された状態が表現できていることがわかる。 | ||
+ | |||
+ | |||
+ | === 最初に $a$ だった値が今何になっているか === | ||
+ | |||
+ | 根ノードから子をたどるのは値の検索などと一緒。 | ||
+ | |||
+ | どちらの子を辿るかを、初期状態での枝に従うところが異なる。 | ||
+ | |||
+ | 初期状態(下図で言うなら、左の枝が0、右の枝が1)だとして、$a=3$ なら、右、右、左と辿っていくことになる。 | ||
+ | |||
+ | ○ | ||
+ | 0/ \1 | ||
+ | | ||
+ | 0/ \1 | ||
+ | ○ | ||
+ | 0/\1 0/\1 0/\1 0/\1 | ||
+ | | ||
+ | |||
+ | その上で、swapフラグを確認しながら、現在の値を復元していく。 | ||
+ | |||
+ | もし、右、右、左と辿ったところの枝が、現在は 0,1,1 となっていたら、現在の値は6となっていることがわかる。 | ||
+ | |||
+ | === 途中で $a$ として追加した値が今何になっているか === | ||
+ | |||
+ | 上記の応用だが、追加時に、「もし枝の値が全て初期状態だったら、何の値を表す箇所に追加したか」を記録しておく。 | ||
+ | |||
+ | |||