二叉排序树的不成功的平均查找长度怎么求?

作者: 知名大学士 | 来源:发表于2020-03-05 22:40 被阅读0次

二叉排序树的不成功的平均查找长度怎么求?
查找
HashMap的树化门槛为什么是8
平均查找长度
平衡二叉树（AVL树）
查找|有序表折半查找判定树|二叉排序树|3阶B-树
第9章查找
查找算法以及hash基础
查找算法
自己动手写数据结构之平衡二叉树

比如：

             62
            /   \
          30     74
        /    \
     15       56
    /
  48

找到所有的外结点，也就是查找失败的点，然后计算ASL
就你的BST，结果如下：

15的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15一共3次
48的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15、48一共4次
56的右子树为空，也就是右子树是外结点，失败时需要比较62、30、56一共3次
74的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、74一共2次

因此外结点总数为2 *3 + 1 = 7 （其实这个数量一定是关键字个数加1）
所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3

二叉排序树的不成功的平均查找长度怎么求?
比如：找到所有的外结点，也就是查找失败的点，然后计算ASL就你的BST，结果如下： 15的左右子树都为空，也就是...
查找
静态查找顺序查找折半查找散列查找动态查找二叉排序树散列查找 ASL(平均查找长度) - 衡量查找算法效率的...
HashMap的树化门槛为什么是8
网上主流的答案：红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长...
平均查找长度
平衡二叉树（AVL树）
一、概念平衡二叉树建立在二叉排序树的基础上，目的是使二叉排序树的平均查找长度更小，即让各结点的深度尽可能小，因此...
查找|有序表折半查找判定树|二叉排序树|3阶B-树
1 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。首先，长度为n的有序表折...
第9章查找
9.1 静态查找表查找操作的性能分析平均查找长度（Average Search Length）。其中为查找表中第...
查找算法以及hash基础
查找查找算法性能的最主要评价标准是平均查找长度（Average Search Length,ASL），即查找过程...
查找算法
ASL 由于查找算法的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数(平均查找长度)作为衡量一...
自己动手写数据结构之平衡二叉树
平衡二叉树我们知道，对于二叉查找树，树的层数越少，查找数据的平均查找时间就会越少。二叉排序树在很多情况下都不能保...