扫码获取更多资源

●动态查找表

动态查找表的特点是：表结构是在查找过程中动态生成的，即如果表中存在其关键字 等于给定值的记录，则查找成功返回；否则插入给定值对应的记录。在静态查找表中，折半 查找效率最高，其时间复杂度为O（log2n）；但维护表有序性的时间复杂度为O（n）,这对于 一个大型查找表来说，效率就太低了。

动态查找表的类型定义

动态查找表的抽象数据类型定义如下：

动态查找表可以有不同的表示方法，如果要对动态查找表进行高效率查找，在本节中将 讨论以几种特殊的二叉树结构表示时的实现方法。

二叉排序树和平衡二叉树

二叉排序树(Binary Sort Tree)又称二叉査找树，它或者是一棵空的二叉树，或者是具 有下列性质的二叉树：

(1)如果其左子树不空，则左子树上所有结点的值均小于根结点的值；

(2)如果其右子树不空，则右子树上所有结点的值均大于根结点的值；

(3)其左右子树也都是二叉排序树。

从上述定义可以看岀，二叉排序树是记录之间满足一定次序关系的二叉树，中序遍历二 叉排序树可以得到一个按关键字有序的序列。例如前面讨论的折半查找判定树就是一棵二 叉排序树。

二叉排序树的査找

设在二叉排序树中査找关键字等于k的记录结点。由于二叉排序树定义的递归性，因 此可以采用递归方式完成査找。递归模型如下：

基本项：当二叉排序树是空树时，查找失败，返回空指针；当k等于根记录结点的关键 字时，查找成功，返回该结点指针。

归纳项：当k小于根记录结点的关键字时，在左子树中继续查找；否则在右子树中继 续查找。

在二叉排序树上进行查找，和折半查找类似，也是一个逐步缩小查找范围的过程。

联系我们：