什么是字典树
字典树（Trie），又称前缀树或键树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值。
字典树的应用场景
- 搜索引擎：当用户输入关键词时，搜索引擎会提供相关的搜索建议。这些搜索建议通常基于用户之前输入的内容。通过使用字典树，搜索引擎可以快速地找到相关的搜索建议。
- 自动补全：字典树是实现自动补全功能的一种常见方法。用户在输入框中输入字符时，程序可以通过查询字典树来提供可能的单词列表。
- 拼写检查器：通过将词典中的所有单词插入到字典树中，拼写检查器可以快速地识别输入文本中的拼写错误。
- IP路由表：路由器使用字典树来存储IP地址前缀，以便快速转发数据包。
字典树的基本结构
节点设计
字典树的每个节点都包含以下属性：
children：子节点的集合，可以是一个对象或哈希表，键为字符，值为子节点。value：节点的值，如果该节点表示一个完整的单词，则存储单词的含义；如果该节点不表示完整的单词，则值为空。isEndOfWord：布尔值，标记该节点是否为一个单词的结束节点。
class TrieNode {
constructor() {
this.children = {};
this.value = null;
this.isEndOfWord = false;
}
}根节点
根节点是字典树的起始点，其 children 属性用于存储所有可能的字符作为子节点。
class Trie {
constructor() {
this.root = new TrieNode();
}
}字典树的操作
插入操作
向字典树中插入单词时，从根节点开始，逐个字符地遍历并创建相应的子节点，直到单词的所有字符都被处理完。最后，设置最后一个节点的 isEndOfWord 属性为 true，以标识这是一个完整的单词。
-- -------------------- ---- -------
------------ ------ -
--- ---- - ----------
--- ---- ---- -- ----- -
-- ---------------------- -
------------------- - --- -----------
-
---- - --------------------
-
---------- - ------
---------------- - -----
-查找操作
查找操作是从根节点开始，逐个字符地遍历字典树，直到单词的最后一个字符。如果找到完整的单词，则返回其 value，否则返回 null。
-- -------------------- ---- -------
------------ -
--- ---- - ----------
--- ---- ---- -- ----- -
-- ---------------------- -
------ -----
-
---- - --------------------
-
------ ---------------- - ---------- - -----
-删除操作
删除操作较为复杂，需要考虑多种情况：
- 如果单词不存在于字典树中，直接返回。
- 如果单词存在，但不是最后一个节点，只需将
isEndOfWord属性设为false。 - 如果单词是最后一个节点，需要递归地删除空节点，直到遇到一个非空节点或者根节点。
-- -------------------- ---- -------
------------ -
----- ------- - ------ ------ -- -
-- ------ --- ------------ -
-- ------------------- ------ ------
---------------- - ------
------ --------------------------------- --- --
-
----- ---- - ------------
----- ----------------------- - ---------------------------- ----- - ---
-- ------------------------- -
------ --------------------
------ --------------------------------- --- --
-
------ ------
--
------------------ ---
-前缀匹配
前缀匹配是指找出所有以指定前缀开头的单词。这可以通过从根节点开始，逐个字符地遍历字典树来实现。
-- -------------------- ---- -------
------------------ -
--- ---- - ----------
--- ---- ---- -- ------- -
-- ---------------------- -
------ ---
-
---- - --------------------
-
------ ---------------------------------
-
--------------------------- -
--- ----- - ---
-- ------------------ -
-----------------------
-
--- ---- ---- -- -------------- -
----- - --------------------------------------------------------------
-
------ ------
-总结
字典树是一种非常强大的数据结构，适用于各种需要高效前缀匹配和字符串搜索的场景。通过合理设计和实现字典树的插入、查找、删除和前缀匹配等操作，可以有效地提高应用程序的性能和用户体验。