转载 查找算法 二叉排序树.doc
版权申诉
59 浏览量
2022-05-08
14:09:41
上传
评论
收藏 40KB DOC 举报
转载 查找算法 二叉排序树
[转载]查找算法--二叉排序树 2007-09-21 15：08 当用线性表作为表的组织形式
时，可以有三种查找法。其中以二分查找效率最高。但由于二分查找要求表中结
点按关键字有序，且不能用链表作存储结构，因此，当表的插入或删除操作频繁
时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外
时间开销，就会抵消二分查找的优点。也就是说，二分查找只适用于静态查找表。
若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树
作为表的组织形式。不妨将它们统称为树表。下面将分别讨论在这些树表上进行
查找和修改操作的方法。
二叉排序树
1、二叉排序树的定义
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。
其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
① 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
② 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③ 左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST 性质)，故二叉排序树实际上是满足 BST 性质
的二叉树。
2、二叉排序树的特点
由 BST 性质可得：
(1)二叉排序树中任一结点 x，其左(右)子树中任一结点 y(若存在)的关键字必小
(大)于 x 的关键字。
(2)二叉排序树中，各结点关键字是惟一的。
注意：
实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二
叉排序树定义中 BST 性质(1)里的"小于"改为"大于等于"，或将 BST 性质(2)里
的"大于"改为"小于等于"，甚至可同时修改这两个性质。
资源评论
