PFDS 10.3 Trie

• Trie は、分岐のみで値を持たないノードを許す多分木。
• Radix tree(Patricia)は、すべてのノードに値を持つ多分木。各ノードはキーの差分を持つ。

Trie

本のコードは抽象的過ぎて分からないので、3ステップで理解する。

• 素朴に Map を使う Trie
• Map を型変数へ変えた Trie
• 同じ関数名を使う Trie(最終版)

本には、使用例が載ってないので、本当に不親切。基本となる型を FiniteMap のインスタンスにしないと動かない。

Generalized Trie

キーをリストから二分木へ拡張する。元の論文も読んでみたが、まったく動機が不明。応用例も思いつかない。

Generalizing Generalized Trie という論文も存在していて、もう頭が爆発しそう。