文字描述

键树定义

　　键树又叫数字查找树，它是一棵度大于或等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。例如，若关键字是数值，则结点中只包含一个数位；若关键字是单词，则结点中只包含一个字母字符。从根到叶子结点的字符组成的字符串表示一个关键字，叶子结点中的特殊符号$表示字符串的结束。在叶子结点中还含有指向该关键字记录的指针。

　　为了查找和插入方便，可以约定键树是有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定$小于任何字符。

键树存储结构

(1)双链树

　　以树的孩子兄弟链表示键树，每个分支结点包含3个信息：symbol, 存储关键字的一个字符；first，存储指向第一颗子树根的指针；next，存储指向右兄弟的指针。同时，叶子结点的infoptr存储指向该关键字记录的指针。此时的键树又称为双链树。

　　双链树的查找：假设给定值K.ch(0,…,num-1)，其中K.ch[0]至K.ch[num-2]表示待查关键字中num-1个字符，K.ch[num-1]为结束符$,从双链树的根指针出发，顺着根指针的first指针找到第一个子树的根结点，以K.ch[0]和此结点的symbol值比较，若相等，则顺first再比较下一个字符；若不相等，沿next顺序查找。若直至”空”仍比较不等，则查找不成功。

　　双链树的查找分析： 键树中每个结点的最大度d和关键字的“基”有关，若关键字是单词，则d=27；若关键字是数值，则d=11。键树的深度h则取决于关键字中字符或数位的个数。假设关键字为随机的(即关键字中每一位取基内任何值的概率相同)，则在双链树中查找每一位的平均查找长度为(1+d)/2。又假设关键字中字符(或数位)的个数都相等，则在双链树中进行查找的平均查找长度为[h*(1+d)]/2

　　双链树的插入或删除： 双链树的插入或删除一个关键字，相当于在树中某个结点上插入或删除一颗子树。

(2)Trie树(trie这个词是从retrieve[检索]中取中间四个字符而来的)

　　以树的多重链表表示键树，则树的每个结点中应含有d个指针域，此时的键树又称Trie树。若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则可将该路径上所有结点压缩成一个“叶子结点”，且在该叶子结点中存储关键字及指向记录的指针等信息。由此，在Trie树中只有两种结点：分支结点(含有d个指针域和一个指示该结点中非空指针域的个数的整数域)和叶子结点(含有关键字域和指向记录的指针域)。在分支结点中不设数据域，每个分支结点所表示的字符均由其双亲结点中(指向该结点)的指针所在位置决定。

　　Trie树的查找： 从根结点出发，沿和给定值相应的指针逐层向下，直到叶子结点，若叶子结点中的关键字和给定值相等，则查找成功，若分支结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不相等，则查找不成功。

　　Trie树的查找分析：从上述查找过程可知，在查找时走了一条从根到叶子结点的路径。由此，查找的时间依赖于树的深度。

示意图

算法分析

略

代码实现

略