Question

数据结构问题

由同一关键字集合构造的各棵二叉排序树的形态，平均查找长度相同吗？为什么？ 由关键码10,20,30,40的四个结点能构造出多少二叉排序树，怎么计算的
在线等

Answer 1

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种
图不太好画，你验证验证看看吧。