type
status
date
slug
summary
tags
category
icon
password
Trie树
据不完全统计，世界上现存英语单词的数量为17万到100万不等。假设现在要你写一个词典APP，要求能够快速检索、删除、添加单词，。显然你很容易想到两种方案：
- 将所有单词按字典序排列，在按二分搜索来查询。
- 奖励首字母索引表，在各索引项表内按字典序排序单词，再在当中按二分搜索查询。 但无疑上述方案的要求略高，需要大量的连续空间来存储数据，而且不方便添加删除操作。
这时Trie树便发挥作用了，我们可以用Trie树来存储单词数据，树结构不需要大量连续的存储空间而且查询、添加结点、删除结点的操作的时间复杂度很小为。
举个例子：
假设存储
这几个单词。其逻辑结构为：
Trie树的实现
结点结构：
树的大致结构：
- 根节点的nodeChar不存储字符， 其字符表示位于指针数组中，指针数组的某元素不空则表示存在以其为首字符的单词。
添加操作
查询操作
删除操作
删除操作比较复杂，分三种情况：
1. 删除整个单词 （该单词的尾结点为叶子节点，且该单词独占一条路径）
2. 删除前缀词 （该单词的尾结点非叶子节点）
3. 删除分支单词 （该单词的尾结点为叶子节点但存在于其他单词共用的路径）
- Author:Lamyh
- URL:https://blog.ccyh.xyz/article/trie
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!