[数据结构]2.字典树 Trie

Trie简介#

Trie又称字典树，用于压缩存储字符串。

---

下面是存储了字符串"apple", "append", "file" 的 Trie

graph TB
root((root))--> 1((a))
1((a))--> 2((p))
2((p))--> 3((p))
3((p)) --> 4((l))
4((l))--> 5((e))

3((p)) --> 6((e))
6((e)) --> 7((n))
7((n)) --> 8((d))

root((root))--> f((f))
f((f)) --> i((i))
i((i)) --> l((l))
l((l)) --> e((e))

引入结束符#

如果两个单词，其中一个是另一个的前缀，应该如何表示？例如“Maria”和“Mariana”。 为了解决这个问题，几乎所有的Trie都引入一个特定的结束符来标记结束，例如"."

优点#

• 有时空间效率高：存储大量拥有相同前缀的单词。
• 高效前缀查找, 如：
  • 统计拥有"app"前缀的单词有多少个？
  • 前缀"strawber"中下一个最可能出现的字符是什么？

缺点#

• 通常空间效率低下：每个ASCII字符仅需1bytes存储空间, 连接Trie各结点的是指针 -- 64位系统下需要8bytes
• 不是标准库：鲜有语言实现了built-in Trie,需要我们自己实现

Trie C语言版实现#

NEED TO DO LATER

---

Radix Trees基数树 --- 空间优化的Trie#

Radix Trees是空间优化的Trie, 假如树中的一个节点是父节点的唯一子节点(the only child)的话，那么该子节点将会与父节点进行合并。 不像是一般的trie树，radix tree的边沿(edges)可以是一个或者多个元素。

下面是存储了字符串"apple", "append", "file" 的 Radix Trees

graph TB
root((root))--> 1((app))
1((app))--> 2((le))
1((app))--> 3((end))

root((root))--> file((file))

reference#

1.Trie Data Structure 2.Trie | (Insert and Search) 3.数据结构之Radix Tree