已知一个长度为11的线性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，试回答下面问题
（1）将线性表元素依次插入一个空的平衡二叉树，画出所得平衡二叉树，如果假设每个元素查找概率相同，则平均查找长度为多少？
(1) 插入12, 这是第一个结点,是根结点.
(2) 插入24, 比12大,作为12的右分支.
12
24
(3) 插入36, 结点12的平衡因子BF变成-2(右子树过高),要左旋(逆时针旋转),
此时,结点24成为根结点.
平衡因子BF(Balance Factor)就是:
将二叉树上结点的 左子树深度 减去 右子树深度的值.
12
24 24
/
36 12 36
左旋后
(4) 插入90, 结点24的BF是-1,二叉树仍然保持平衡.
24
/
12 36
90
(5) 插入52, 结点36的BF是-2,结点90的BF是+1,两个符号不一致,结点90和52先右旋,
此时,结点52的BF是-1,结点36的BF是-2,再对结点36,52,90进行左旋.
24 24 24
/ / /
12 36 12 36 12 52
/
90 52 36 90
/
52 90
右旋后 左旋后
(6) 插入30, 结点52的BF是+1,结点24的BF是-2,两个符号不一致,
结点30,36和52先右旋,此时,结点36的BF是-1,结点24的BF是-2,
结点12,24和36进行左旋.
24 24 36
/ / /
12 52 12 36 24 52
/ / /
36 90 30 52 12 30 90
/
30 90
右旋后 左旋后
(7) 插入41, 二叉树仍然保持平衡.
36
/
24 52
/ /
12 30 41 90
(8) 插入8, 二叉树仍然保持平衡.
36
/
24 52
/ /
12 30 41 90
/
8
(9) 插入10, 结点8的BF是-1,结点12的BF是+2,结点24的BF是+2,
结点8和10先左旋,此时,结点10的BF是+1,结点12的BF是+2,
对结点10,8,12进行右旋.
36 36 36
/ / /
24 52 24 52 24 52
/ / / / / /
12 30 41 90 12 30 41 90 10 30 41 90
/ / /
8 10 8 12
/
10 8
左旋后 右旋后
(10) 插入38, 二叉树仍然保持平衡.
36
/
24 52
/ /
10 30 41 90
/ /
8 12 38
(11) 插入61, 二叉树仍然保持平衡.
36
/
24 52
/ /
10 30 41 90
/ / /
8 12 38 61
这就是最后得到的平衡二叉树
二叉树的总结点数 N=11
如果假设每个元素查找概率相同,平均查找长度是 log2(N)=log2(11),
表示以2为底,取11的对数.
0、什么是环？在图论中，环（英语：cycle）是一条只有第一个和最后一个顶点重复的非空路径。在有向图中，一个结点经过两种路线到达另一个结点，未必形成环。1、拓扑排序1.1、无向图使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：求出图中所有结点的度。将所有度 <= 1 的结点入队。（独立结点的度为 0）当队列不空时，弹出队首元...
对该问题,分为如下几种情形讨论: 情形一: 假如该树为二叉树,并且是二叉搜索树, 依据二叉搜索树是排过序的, 我们只需要从树的根结点开始,逐级往下,和两个输入的结点进行比较. 如果当前结点的值比两个结点的值都大,那么最低的公共祖先一定在当前结点的左子树中,下一步遍历当前结点的左子节点. 如果当前结点的值比两个结点的值都小,那么...
哗我看了一下好像没有很详细专门讲分治的blog？那就主要先学一下点分治吧，其他的……等我记得把C++一本通带到机房来再说吧先咕着啦 写在前面 刷题进度 入门题（0/3） 好题(0/9) 问题解决进度 Q1 Q2 正文 淀粉质 点分治 点分治就是在一棵树上，对具有某些限定条件的途径静态地进行统计的算法。 ——《算法竞赛 进阶指南》...
B树 即二叉搜索树： 1.所有非叶子结点至多拥有两个儿子（Left和Right）； 2.所有结点存储一个关键字； 3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树； 如： ...
insertAdjacentText方法与 insertAdjacentHTML方法类似，只不过是插入纯文本，参数相同 参数说明： elementDOM.insertAdjacentHTML(where,html) elementDOM：用于参照插入位置的html元素对象 where：插入位置。包括"beforeBegin"、...
1、基本思想： 已知待排序列r[1...n],先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成关键字非递减有序序列为止。 具体操作如下： （1）查找出r[i]在有序序列r[1...i-1]中的插入位置k; （2）将r[k...i-1]中所有元素全部后移一个位...
oracle创建表时，不支持在建表时同时增加字段注释。故采用以下方式： #创建表 CREATE TABLE predict_data as (id integer NOT NULL, uid varchar2(80),mid varchar2(8...
本章主要内容 一、单元格操作 二、插入批注 三、自动求和 四、填充序列 五、查找、替换 六、对齐方式 七、定位 八、插入形状及设置形状 九、页面设置 一单元格操作 1、插入 a、插入单元格 一个单元格选中状态---右击插入（单元左右移）--即可 b、插入单元行/列 c、插入多行单元行/列 选中多行---右击插入----...