Trie

前缀树或字典树,是一种有序树,其发明者 Edward Fredkin 把它读作/ˈtriː/ "tree",但更多人把它读作/ˈtraɪ/ "try"。朴素的 Trie 由于存储稀疏,存在空间利用率低下的问题。Radix tree (又被称为 radix trie、压缩前缀树、compressed trie) 将作为唯一子节点的每个节点都与其父节点合并,是一种更节省空间的前缀树,Rax 是一个 Radix tree 的 C 语言实现。

Optional readings

References