二叉排序树和二叉查找树有相同的特性吗？

Question

如题所述

Answer 1

不一定相同。

折半查找：必须要求记录有序，采用顺序存储，利用这个特点，所以折半查找的效率也比顺序查找高，对于数量非常大时，非常快，时间复杂度为O(logN)。

二叉查找树：若它的左子树不为空，则左子树上所有节点的值均小于根节点。若它的右子树不为空，则右子树上所有节点的值均小于根节点，它的左右子树都是二叉查找树。

所以二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系。但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足logn的。

例如一棵只有多层左子树的而叉排序树。只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。

扩展资料：

与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

二叉排序树的查找过程为：

1、若查找树为空，查找失败。

2、查找树非空，将给定值key与查找树的根结点关键码比较。

3、若相等，查找成功，结束查找过程，否则：当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。当给值key 大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。