あどけない話

インターネットに関する技術的な話など

PFDS 10.3 Trie

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

Trie

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

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

Generalized Trie

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

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