for循环中加入判断条件i值是否越界

哨兵设置在下表为0的空间内,这样写可以省略for循环中的判断i值是否越界

因为从尾部向前查找,最终即使找不到也会查到下标为0的哨兵值从而正常跳出循环

将被查概率高的放到靠前位置,可以提高查找成功的效率,但对于查找失败的情况需要从头看到尾,因为无序排列,根据实际情况选择不同的方式,经常查找成功可以考虑上图方式

折半查找的查找效率,绿色节点为查找成功,紫色为查找失败,一共11个结点,每一层结点的数量*查到该层结点需要的步数的综合/11就是成功的ASL,失败同理

所以要想算出他们的查找效率,我们需要画出来对应的查找判定树(根据折半查找的思想画图)

mid对应的值为每一层的结点

因为右子树的节点数一定比左子树多1个或等于左子树的结点,所以当两个数折半查找,画出查找判断树,2结点在右子树

二叉排序树符合二叉树性质,而且是二叉排序树

块间可升序可降序

查30,20,10我们通过块间在折半查找可以找到存储区域,因为块间关键字就是他们本身

查19,18,17这些不是块间关键字的数据折半查找结束通过在low区域内查找

插入元素是为了维护索引表需要将后面的元素真题向后移,为了更好的维护索引表可以采用链式存储