由关键字构造二叉排序树，平均查找长度是多少？

1.由同一关键字集合构造的各棵二叉排序树的形态，平均查找长度相同吗？为什么？

对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。

在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：

①在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是(n+1)/2。

②在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn。

③插入、删除和查找算法的时间复杂度均为O(lgn)。

------

譬如：关键字：10 10 10 10

10 10

10 或 10 10 或 ...

10 10

10

------

2.由关键码10,20,30,40的四个结点能构造出多少二叉排序树，怎么计算的

二叉排序树 共16种

avl树共4种

完全二叉树共1种

图不太好画，你验证验证看看吧。