字典树（Trie），又称为前缀树或单词查找树，是一种用于检索字符串数据集中的键的树形数据结构。它是一种有序树，其中每个节点包含一个字符、一个对应该字符值的前缀，以及对其子节点的引用列表。字典树在搜索引擎、自动完成、拼写检查等场景中有着广泛的应用。
以下是字典树的一些基本特性：
- 根节点不包含任何字符，每一个节点都包含一个字符。
- 从根节点到某一节点，经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不同。
- 通常在字典树的节点中会包含一个标记，用来标识该节点是否是某个字符串的结尾。
字典树的基本操作包括： - 插入字符串：在字典树中插入一个字符串，从根节点开始，逐个字符插入。如果字符对应的子节点不存在，则创建新的节点。
- 搜索字符串：在字典树中查找一个字符串，从根节点开始，逐个字符查找。如果能够找到完整的字符串，则返回真，否则返回假。
- 前缀匹配：查找所有以特定字符串为前缀的字符串。这可以通过在字典树中搜索该前缀，并返回所有从匹配到的节点开始的子树来实现。
字典树的优点： - 提高了查找效率，特别是对于较长的字符串集合。
- 可以快速进行前缀匹配。
- 节省空间，因为公共前缀被共享。
字典树的缺点： - 相对于其他数据结构（如哈希表），字典树可能需要更多的内存空间。
- 插入和查找的时间复杂度取决于字符串的长度，对于非常短的字符串，可能不如哈希表高效。
在实际应用中，字典树可以根据需要进行调整和优化，例如通过压缩字典树节点来减少内存使用，或者通过使用平衡树（如红黑树）来优化节点子列表的查找效率。
字典树的基本操作包括：
- 插入字符串：在字典树中插入一个字符串，从根节点开始，逐个字符插入。如果字符对应的子节点不存在，则创建新的节点。
- 搜索字符串：在字典树中查找一个字符串，从根节点开始，逐个字符查找。如果能够找到完整的字符串，则返回真，否则返回假。
- 前缀匹配：查找所有以特定字符串为前缀的字符串。这可以通过在字典树中搜索该前缀，并返回所有从匹配到的节点开始的子树来实现。
字典树的优点：
- 提高了查找效率，特别是对于较长的字符串集合。
- 可以快速进行前缀匹配。
- 节省空间，因为公共前缀被共享。
字典树的缺点：
- 相对于其他数据结构（如哈希表），字典树可能需要更多的内存空间。
- 插入和查找的时间复杂度取决于字符串的长度，对于非常短的字符串，可能不如哈希表高效。
在实际应用中，字典树可以根据需要进行调整和优化，例如通过压缩字典树节点来减少内存使用，或者通过使用平衡树（如红黑树）来优化节点子列表的查找效率。
https://www.bilibili.com/video/BV1yA4y1Z74t?vd_source=f8c374aa175ff8e4f7cdde66fd1cb321