Question

n个结点的二叉排序树在最坏的情况下的平均查找长度为______

是(n+1)/2吗？为什么是这个

Answer 1

n个结点的二叉排序树在最坏的情况下的平均查找长度为（n+1）/2。

二叉排序树每个结点的C（i）为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度（n+1）/2（和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 （n）成正比。

扩展资料：

二叉排序树的平均查找方式是若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。

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

Answer 2

当n=1, 只有一个根结点, 成功找到根结点只需要1次, 平均查找长度为:
ASL = (n+1)/2 = (1+1)/2 = 1

当n=2, 有两个结点, 假设是往右倾斜, 成功找到结点1需要1次,
成功找到结点2需要2次, 平均查找长度为: (1+2)/2 = 3/2
用公式计算 ASL= (2+1)/2 = 3/2

  1
   \
    2


当n=3, 有三个结点, 最坏的情况是整个二叉排序树往右倾斜(或者左倾斜),
成功找到结点1需要1次, 成功找到结点2需要2次, 成功找到结点3需要3次, 
平均查找长度为: (1+2+3)/3 = 6/3 = 2
用公式计算 ASL= (3+1)/2 = 4/2 = 2

  1
   \
    2
     \
      3


如果结点的总数量是n, 最坏的情况是整个二叉排序树往右倾斜(或者左倾斜),
成功找到结点1需要1次, 
成功找到结点2需要2次, 
成功找到结点3需要3次, 
......
成功找到结点n需要n次, 
平均查找长度为: (1+2+3+...+n) / n

上述 1+2+3+...+n 就是等差数列求和,数学公式是 (n+1)*n / 2

所以, (1+2+3+...+n) / n = (n+1)*n / 2 / n = (n+1)/2

也就是, n个结点的二叉排序树在最坏的情况下的平均查找长度为 (n+1)/2

二叉树示意图,整个二叉排序树往右倾斜,成了单向链表:

  1
   \
    2
     \
      3
       \
        .
         .
          .
           \
           n-2
             \
             n-1
               \
                n