Question

平衡二叉树的平均查找长度log2n怎么算

Answer 1

问：平衡二叉树的平均查找长度log2n怎么算

答：平衡二叉树的平均查找长度 log2n 怎么算 你好，折半查找可以借助于一个二叉树来描述。为了简化讨论，则把这棵树近似看成满二叉树，设二叉树的高度为 h (h>1)。根据二叉树的性质，它有最大节点数 n=2^h-1，则 h=log2(n+1) (2 是底数)。那么二叉树的第 j 层节点数为：2^(j-1)。 假定每个元素的查找概率相等，则 pi=1/n (pi 为第 i 个节点的查找概率)。那么平均查找长度为 1/n*(1*2^0+2*2^1+3*2^2+……+j*2^(j-1))。 经过化简计算，得平均查找长度为：(（n+1）/n ) *log2(n+1)-1 (其中对数中的 2 为底数：即 log 以 2 为底（n+1)的对数)。注：当 n 很大时，可近似为 log2(n+1)-1。 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找。而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。