——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。
键树
键树的定义
键树又称数字查找树，是一棵度≥2的树，树中每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。
键树的构造
由给定的关键字集合构造其键树的方法是，先将关键字集合按照某种规则（对键树进行查找、插入和删除时也需根据该规则进行）根据各个关键字位逐层分割，每次使根据该规则选择的关键字位的字符相同的关键字处于同一集合，直至每个子集中只含有一个关键字，则在分割过程中形成的集合、子集和元素之间的层次关系可以用一棵树来表示（依据是树的嵌套集合表示形式），该树便为键树。
键树的逻辑结构
由从键树的根到其叶子结点的路径上各结点代表的字符依次组成的字符串表示一个关键字。
键树的数据（逻辑）结构中每个结点的最大度d和关键字的“基”有关，该最大度为关键字的“基”值加1（关键字结束字符），最大深度h取决于最长关键字中字符的个数。
为查找和插入方便，约定键树是有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符$小于任何字符。
键树的查找
查找过程
在键树中查找指定关键字的过程，就是将指定关键字中的每一位依次与键树中的相应结点进行比较的过程。
性能分析
采用不同存储结构的键树，查找成功时均走了一条从树根到叶子的路径，查找时间均与树的深度有关。
键树的插入和删除
在键树中插入或删除一个关键字，即为在键树的某个结点上插入或删除一棵单支子树。
键树的存储结构
键树中的存储结点分为分支结点和叶子结点。有两种存储结构：
(1) 使用树的孩子兄弟表示法，此时的键树称为双链树。
(2)使用树的孩子表示法，此时的键树称为Trie（retrieve检索）树。
双链树
双链树的存储结构
分支结点：
（Symbol域，存储关键字的一个字符；First域，存储指向第一棵子树的根的指针；Next域，存储指向右兄弟的指针）
叶子结点：
（Symbol域，存储关键字的一个字符（特殊字符$，即关键字字符串的结束字符）；Next域，存储指向右兄弟的指针；Infoptr域，存储指向该关键字对应的记录的指针）
双链树的查找
查找过程
给定关键字的最后一个字符为关键字结束字符。从双链树的根结点（根结点中不存储任何关键字字符）开始，顺着First域找到第一棵子树的根结点，对根结点的Symbol域和给定关键字的第一个字符进行比较，若相同，则顺着First域与给定关键字的下一字符进行比较，若不同，则顺Next域与给定关键字的当前字符进行比较；若直至“空”仍比较不同，则查找失败，若给定关键字中的字符全部比较相同，则查找成功。
性能分析
根据键树的逻辑结构分析可知，若关键字为随机的（即关键字中每一位取基内任何值的概率相同），则在双链树中查找每一位的平均查找长度为(1+d)/2，又若关键字中字符的个数相同，则在双链树中进行查找的平均长度为(1+d)h/2。
双链树的插入和删除
在双链树中插入或删除一个关键字，相当于在对应的键树中的某个结点上插入或删除一棵单支子树。
Trie树
Trie树的存储结构
每个分支结点含有b+1（b为关键字的基中字符的个数）个指针域（这也是采用该存储结构的键树称为Trie树的原因）。若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则将该路径上所有结点压缩成一个叶子结点。
分支结点：
（分支结点中共有b+1个指针域和1个数值域。Num域，指示该结点中非空指针域的个数；C0域，存储指向关键字的特殊结束字符代表的子树的根的指针；C1域，存储指向关键字的基中第一个字符引导的子树的根的指针；Ci域，存储指向关键字的基中第i个字符引导的子树的根的指针；Cb域，存储指向关键字的基中最后一个字符代表的子树的根的指针。在分支结点中不设数据域，每个分支结点所表示的字符均由其双亲结点中指向该结点的指针所在的位置决定。）
叶子结点：
（Key域，存储该叶子结点的关键字；Infoptr域，存储指向该关键字对应的记录的指针）
Trie树的查找
查找过程
从根结点出发，沿和给定关键字的当前字符相应的指针逐层向下，直至叶子结点，若叶子结点中的关键字和给定关键字相同，则查找成功；若分支结点中和给定关键字的当前字符相应的指针为空，或叶子结点中的关键字和给定关键字不相等，则查找失败。
性能分析
查找时间依赖于树的深度。减少Trie树的深度的方法有，①可以对关键字集合选择一种合适的分割规则（如先按关键字的第一个字符不同分割成不同的子集后，再按关键字的最后一个字符不同分割每个子集，再按第二个字符……，前后交叉分割），以缩减Trie树的深度（树由“高瘦”变得“矮胖”）。或②限制Trie树的深度，假设允许Trie树的最大深度为h，则所有直至h-1层皆为同义词的关键字都进入同一叶子结点（查找到该叶子结点后，再在该叶子结点内再逐个比较关键字）。
Trie树的插入和删除
在Trie树上进行插入和删除一个关键字时，在插入和删除一个叶子结点的同时可能需要相应地增加和删除一些分支结点。当分支结点中非空指针域的个数减为1时，若该分支结点的非空指针域指向的是叶子结点，便可将该分支结点删除，同时将该分支结点中非空指针域所指向的叶子结点改由该分支结点的双亲结点中指向该分支结点的指针域所指（依据为，若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则将该路径上所有结点压缩成一个叶子结点）。
文章合集：
点击下方公众号主页，关注以阅读更多文章
——可选择“【右上角···】→【在浏览器中打开】”进行横屏阅读。
