トライ (データ構造)
辞書順にキー文字列をソートする処理は次のようにトライ木で実現される:
全キーをトライ木に挿入する。
深さ優先探索のような決まった順序でトライ木から全キーを取り出す。
これは一種の基数ソートである。
トライ木を使って N 個のキーのソートを N 個のプロセッサで行うと(並列アルゴリズム)、その時間は Ω(1) となる。ただし、キーの長さはある一定の上限があるものとする。キーが共通のプレフィックスを持っていたり、同じキーが複数個あったりするので、並列処理の性能上の利点が小さくなるという問題はある。
二分トライ木(英: binary trie)やビット単位トライ木(英: bitwise trie)とは、整数を格納するトライ木で、上位ビットから 0 また 1 で左右に分岐する。
高速化のためのテクニックとして、下記の2つの方法が使える。
葉ノードは子が無く、子を指すポインタが空くので、葉ノード同士を双方向連結リストでつないでしまう。前後のノードを O(1) でたどれるようになる。
jumpポインタをノードに付け、一気に葉ノードまでジャンプする。