Question

数据结构问题

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

Answer 1

通常情况下，我们会按照结构模型把系统产生的数据分为三种类型：结构化数据、半结构化数据和非结构化数据。结构化数据，即行数据，是存储在数据库里，可以用二维表结构来逻辑表达实现的数据。最常见的就是数字数据和文本数据，它们可以某种标准格式存在于文件或记录的固定字段中。相对应的，没有固定结构不方便用数据库二维逻辑表来表现的数据即称为非结构化数据，包括所有格式的办公文档、文本、图片、XML、HTML、各类报表、图像和音频/视频信息等等。我们都知道，结构化的数据很容易被采集和存储，分析展示起来也很容易，市场上已经有很多成熟的BI…

Answer 2

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