差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:data_structure:trie [2019/02/27] – ikatakos
+++ programming_algorithm:data_structure:trie [2022/05/08] (現在) – [操作] ikatakos
@@ 行 97: / 行 97: @@
         return ret
 </sxh>
+===== 逆Binary Trie =====
+ちょっと特殊だが、上位桁でなく、1の位から順に構築したTrie。\\
+管理する2進数での最大桁を $d_{max}$ として、
+  * 値の追加: $O(d_{max})$
+  * 値の削除: $O(d_{max})$
+  * 値の検索: $O(d_{max})$
+  * 全体に特定の値をXORする操作: $O(d_{max})$
+  * 大小比較はできなくなる
+  * 代わりに、全体に1を足す操作を $O(d_{max})$ でできる
+たくさんの値に、同時にXORや1を足す操作を行った後、各値がそれぞれ何になっているか、を高速に得たい場合に使える。
+==== 構造 ====
+$d_{max}$ は、「+1されて繰り上がりが発生した後」も含めての最大桁であることが望ましい。\\
+その上で、先頭の'0'も省略せず、値は全て深さ $d_{max}$ のノードで存在を管理する。
+（先頭の'0'を省略し、途中のノードに値の存在有無を持たせる実装もできるとは思うが、先頭の'0'があるかないかの二重登録の防止など、ややこしくなりそう）
+           ○
+／   ＼1
+       ○       ○
+／  \1   0/  ＼1
+    ○   ○   ○   ○
+/\1 0/\1 0/\1 0/\1
+   ⓪④ ②⑥ ①⑤ ③⑦
+  010  001  011
+  110  101  111
+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を足す前の状態
+           ○
+／   ＼1
+       ○       ○
+／  \1   1/  ＼0
+    ○   ○   ○   ○
+/\1 1/\0 0/\1 0/\1
+   ⓪④ ⑥② ③⑦ ①⑤
+を足した後の状態
+           ○
+       [1／   ＼0]         [  ] swapしたノード
+       ○       ○
+／  \1  [0/  ＼1]
+    ○   ○   ○   ○
+/\1 1/\0[1/\0]0/\1
+   ①⑤ ⑦③ ④⓪ ②⑥
+              (⑧)
+⑧に関しては、オーバーフローして⓪になっている（こういうことを防ぐため、$d_{max}$ はそれを含めての最大桁を設定した方が良い）が、他は、きちんと1ずつ足された状態が表現できていることがわかる。
+=== 最初に $a$ だった値が今何になっているか ===
+根ノードから子をたどるのは値の検索などと一緒。
+どちらの子を辿るかを、初期状態での枝に従うところが異なる。
+初期状態（下図で言うなら、左の枝が0、右の枝が1）だとして、$a=3$ なら、右、右、左と辿っていくことになる。
+           ○
+／   ＼1
+       ○       ○
+／  \1   0/  ＼1
+    ○   ○   ○   ○
+/\1 0/\1 0/\1 0/\1
+   ⓪④ ②⑥ ①⑤ ③⑦
+その上で、swapフラグを確認しながら、現在の値を復元していく。
+もし、右、右、左と辿ったところの枝が、現在は 0,1,1 となっていたら、現在の値は6となっていることがわかる。
+=== 途中で $a$ として追加した値が今何になっているか ===
+上記の応用だが、追加時に、「もし枝の値が全て初期状態だったら、何の値を表す箇所に追加したか」を記録しておく。