平衡二叉树

定义

缩写记一下 AVL

还有下面这些，can you try？

平衡二叉树的插入

LL平衡旋转（右单旋转）

怎么理解？

首先我们可以看见啊，b图A左边和右边的不平衡的，非常的难受

于是我们可以这么做，因为A的左边比右边多，所以B和A交换位置，这样就会出现一个问题，B的左边继续写BL没问题，A的右边继续写AR没问题，那BR放哪里呢，BR放在A的左边我的朋友，因为A的左边本来就是有东西的

然后BR仍然是大于B小于A的

RR平衡旋转（左单旋转）

一样，就是哪边多，你就往相反的方向旋，这里右边多，就往左旋，

LR平衡旋转（先左后右双旋转）

这里直接看b图是怎么直接到c图的 

这里LR的意思是先左 到B 再右道 BR，这里会多一个

哪边多，你就往相反的方向旋，这里右边多，左旋

然后这里除了CLANNAD照搬不了，其他的都照搬

然后B的右边原来就是有东西的，所以再放一下CL

然后再把没用到的A先画出来

然后就左边多，就往右旋，C上去，A到右边下来

最后照搬变成书上的c图，A的右边照搬是AR，C的右边照搬是B的全部,然后原本C的CR无法照搬，而A的左边原本就应该有东西，所以CR放A左边

RL平衡旋转（先右后左双旋转）

这个也是不多说了，原理一样

最小不平衡子树

这里的意思是这里有2个节点不平衡了，也就是27和75，然后只要把最下面的调好，27这个也就自动调好了

逗你一笑小例子

然后112会插在

然后发现120和100不平衡了，然后你只要处理最下面的120就行了

然后开始做

继续

好了，就这样

最后，其他的不用变

然后就有人说了，主播有没有更简单的方法，有的兄弟有的

先往你插入的地方从上往下数3个

然后把大小是中间的数写在中间，这里就是115，然后左边是110，右边的120

然后剩下的按大小来写

然后再也不用旋了，一步到位

做题

1

 

c

2

d 

3

题目意思是 每次加一个，不平衡的话就旋转

 

d

4

这个是二叉排序树，注意

c

平衡二叉树的删除

过程

这里删的是32，删了之后就不平衡了，然后之前我们是往插入的地方走，现在就是看哪边地方大往哪边走，然后开旋

做题

1

 

a

平衡二叉树的查找

 

这个图看T3，T3左边是T1，右边是T2，所以可以看见，如果下面本就是平衡的，那只用加一个节点就可以即加深度又是平衡的，这里T4就是T2+T3+1的节点和他的四层深度

所以这个公式就不用记了，可以直接推出来

注意这里是要求最大深度，比如7个节点既可以是4层也可以是3层

做题

1

1  2  4  7  12  20 

b

2

11题 c秒，最大深度注意

12题 b秒，至少注意