二叉排序树的问题：性能跟输入数据的顺序有关，最好的时候是折半查找性能，最差是顺序查找性能，所以有必要对如何构建这棵树好好研究研究。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

子树a1aa1 aa2 子树c

从a2看进来，树的深度为h+2，与原来相同。

2）同理分析：在RR时，将b的右树节点上提，b变为其左节点

在RL时，还要在分解，将b的右节点的左节点上移取代b的位置。

（完）