二叉排序树的问题：性能跟输入数据的顺序有关，最好的时候是折半查找性能，最差是顺序查找性能，所以有必要对如何构建这棵树好好研究研究。AVL的诞生（为什么不是BBT，而叫AVL，不解）
定义
平衡因子BF：左子树深度减右子数深度。
AVL所有节点的平衡因子为1，0，－1的二叉排序数称为AVL。
补充定义：
问题节点：当加入一个新节点后导致的、第一个平衡因子不再符合AVL定义的节点。
理论：如果问题节点的子树深度与加入节点前的深度一样，则其上面将不会有问题节点了，这棵树已经是一个AVL了。
分析不平衡的原因：
1）原来问题节点的BF为1，现在在其左子树上加新节点，使得BF＝2
2）原来问题节点的BF为－1，现在在其右子树上加新节点，使得BF＝－2
1）的讨论
原来 现在(加节点后，还没调整)
问题节点b 问题节点b
左树a 右树c 左树a +1 右树c
设原来a深度为h+1,c深度为h，则b的深度为h+2，a必然可以再细分(h>＝0)
左树a
子树a1 子树a2
a1,a2的设定必然有一个是h（因为a的深度是h+1,a本身一个，所以其子树最大的深度为h），新节点必加入h
的子树，而且加入后，其深度变为h+1(否则子树BF不变，其上面节点的BF不会出问题)
另一个也是h，由上面分析知道另一个可能是h，或h－1(最大的是h，本身是AVL)，但如果是h-1则，新加入的
节点将使另一个子树变为h+1，则第一个不满足AVL树的节点将是a，而不是a的parent b节点。
a)考虑新加入的节点在a1中，这就是LL问题（左边的左边）。
解决很容易：将b拉入右树，a上提，a2归入b的左子树
新结构如下：
a
子树aa1 子树b
子树aa1 子树c
从a看进来，树的深度为h+2 ，与原来相同。
b)考虑新加入的节点在a2中，这就是LR问题（左边的右边）。
解决比较复杂，还需要再分析一步：则新a2的深度将会是h+1，则a2又可以仿照前面的a节点写成：
左树a2
子树aa1 子树aa2
aa1与aa2有一个深度是h，另一个h-1(分析：最大的深度是h，所以必然有一个，而且是新加入节点引起
深度增加的，所以另一个是h-1)
将b拉入右树，a2上提，a2的两棵树分别给a，以及b
新结构如下：
a2
子树a 子树b
子树a1 aa1 aa2 子树c
从a2看进来，树的深度为h+2 ，与原来相同。
2）同理分析：在RR时，将b的右树节点上提，b变为其左节点
在RL时，还要在分解，将b的右节点的左节点上移取代b的位置。
（完）
评论