平衡二叉树
定义
缩写记一下 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秒，至少注意