Trie木 (Binary Trie)

文字列リストを管理するとき、メモリ・検索速度的に優れたデータ構造。

辺に文字を対応させた根付き木で、根からのパスで通った辺によって単語を表現する。

前方一致検索が出来る
辞書順最小・最大の検索、$k$ 番目の検索が素早くできる（各ノードに自身の部分木に含まれる単語数を持たせる）
ある単語の直前・直後の単語検索ができる
互いに似ている多数の短い文字列の管理に特に向く
- 少数の長い文字列の管理もできるが、パフォーマンスは落ちる。それにはパトリシア木などを用いる
辞書的順序が変化しても最大最小や $k$ 番目を検索できる

一方、二分探索木やBinaryIndexedTreeのようにindexと親子関係を綺麗に対応させることはできないので、データ全体を1次元配列で持つのはできない。 Nodeクラスを量産して各インスタンスに親子関係を持たせるタイプの実装となる。

Pythonではクラスは読みやすいコードにはなるが生成コストが重い（と思う、要確認だが）ので、速度を気にするなら配列や辞書をインスタンス替わりに使う実装となる。

目的によって、ノードに持たせる値や実装方法は変化する。

Binary Trie

Trie木の辺の値を文字でなく0/1に限定し、非負整数を2進数で管理できるようにしたのがBinary Trie（二分トライ木）。

処理できるクエリと計算量は、管理する値の2進数での最大桁数を $d$ として、

値の挿入: $O(d)$
値の削除: $O(d)$
値の各種検索: だいたい $O(d)$

整数の大小比較に用いるには桁数を固定する（足りない桁は先頭をゼロで埋める）必要がある。競技プログラミング的には長さを固定せずに「0と1だけから成る文字列の辞書的順序」の管理も出来る、一応。

$最大桁数 \times 値の個数$ 個のNodeインスタンスが最悪作られるので、2秒程度の処理で済ませるには、それが $10^6～10^7$ に収まっていればよい。実際は、根に近い方のNodeはほぼ共有されるので、もうちょっと少なくなる。

最大や最小の管理や、ある値以下の最大の値検索(lower_bound)など、単独のクエリだけならheapqやbisectなどで事足りる。

使い道としては、それらの複合クエリを処理したいときか、またはビット演算と相性がいいのでそれと組み合わせた最大/最小を取得したいときになる。

最大値、最小値クエリ
ある値以下の最大値、ある値以上の最小値クエリ
整数 $X$ のビット演算（andやxor）を取った後での最大値/最小値クエリ

特に全体にxorをかける操作は、即座にも、遅延評価でも行える。（'1'が立っているビットの左右の子を入れ替えればよい）

また、高速化としては、行き先がもはや1つに決まった枝は、葉までスキップできるようにしておく方法がある。全ての値をinsertしてからクエリが来る場合は、insert後に1回探索してショートカットを貼ればよい。 insert,deleteとクエリが順不同に来る場合は、若干処理が面倒になるが、まぁ頑張れば出来る。（ほんとか？）

class BinaryTrie:

    def __init__(self, bit_depth):
        self.root = [None, None, 0]  # [0-child, 1-child, count]
        self.bit_start = 1 << (bit_depth - 1)
        self.xor_mask = 0

    def insert(self, x):
        """xを格納"""
        b = self.bit_start
        node = self.root
        node[2] += 1
        while b:
            i = bool(x & b)
            if node[i] is None:
                node[i] = [None, None, 1]
            else:
                node[i][2] += 1
            node = node[i]
            b >>= 1

    def pop_min(self):
        """xor_mask適用後の最小値を、適用前の値で取得し、木からは削除"""
        b = self.bit_start
        node = self.root
        m = self.xor_mask
        ret = 0
        node[2] -= 1
        while b:
            i = bool(m & b)
            if node[i] is None:
                i ^= 1
            ret = (ret << 1) + i

            if node[i][2] > 1:
                node[i][2] -= 1
                node = node[i]
            else:
                tmp = node[i]
                node[i] = None
                node = tmp
            b >>= 1
        return ret

目次

Trie木 (Binary Trie)

Binary Trie