折半查找与二叉排序树最坏的情況下查找log(n)+1次而二叉查找树最坏的情况是查找n次。

跟查找树的设计有关系做成avl就很好，做成一边倒就很烂了

折半查找与二叉排序树在时間性能最坏情况下为目标结点位于最后一层叶子节点的情况，此时的查找时间为树的深度即为log₂(n+1)取上整。

而二元查找树时间性能最坏的凊况是线性查找，即树退化为一条链失去了树的优点，此时最长查找时间为目标结点位于叶子节点，即为n

一开始没反应过来二元查找树就是二叉查找树??

折半查找与二叉排序树数组长度为奇数时最多查找㏒ n次，偶数时最多查找㏒ n +1次BST最多为 n次。

查找?和输入有关，若转化为单支?，时间复杂度最大

二分查找最多找log2n+1次 ?，二分查找树最差能退化为线性表 ??

但是二元查找树为链式的情况，就需要n次查找

折半查找與二叉排序树最坏是找不到logn+1 二元树退化成只有左子树或者右子树情况下最坏实现行查找，n

做题的时候忍不住拿二叉查找树往AVL树里怼

二分查找过程可用二叉树来描述把当前查找区间的中间位置上的结点作为根，把左子表和右子表中的 结点分别作为根的左子树和右子树由此得到的二叉树称为描述二分查找的判定树（Decision Tree）或比较树（Comparison Tree）。

设内部结点的总数为n=2^h-1.则判定树是深度为h = lg（n+1）的满二叉树（深度h不计外部结點）树中第k层上的结点个数为2^(k-1) ，查找它们所需的比较次数是k因此 在等概率的假设下，二分查找的平均查找长度为：

二分查找在查找失敗时所需比较的关键字个数不超过判定树的深度在最坏的情况下查找成功的比较次数也不超过判定树的深度。即为：

从根结点依次往下找二元查找树最坏时需查找n次(数列有序，树只有左孩子或只有右孩子退化为线性表)

折半查找与②叉排序树的时间复杂度最坏也就log（2n),对于二元查找树而言，如果是单支树就是只有右结点或者只有左结点查找起来就是O(n)。索引答案是B

折半查找与二叉排序树最坏情况下也就等于线性查找了O(n),二元查找树也是啊，感觉应该是对的吧

折半查找与二叉排序树的前提序列就是有序嘚因此最坏是O（logN），而二叉树的生成是未知的最好情况就是个平衡二叉树，最坏就像一条线（一直往左或一直往右）因此最坏是O（N）

折半查找与二叉排序树要有序。。。前提

折半查找与二叉排序树查找长度为1——logn而二分查找树的查找长度为1——n。所以最坏的情況下查找长度不同选B

二叉排序树的查找性能在最好情况和折半查找与二叉排序树相同。

学号:E 专业:网络工程姓名:张芸
实验日期: 教师签字: 成绩
实验目的:实现顺序查找,折半查找与二叉排序树,二叉排序树,哈希表实验原理: