首页 > 代码库 > 数据结构&&AVL树原理、插入操作详解及实现
数据结构&&AVL树原理、插入操作详解及实现
AVL树的复杂程度真是比二叉搜索树高了整整一个数量级——它的原理并不难弄懂，但要把它用代码实现出来还真的有点费脑筋。下面我们来看看：
2.AVL树是什么？AVL树本质上还是一棵二叉搜索树（因此读者可以看到我后面的代码是继承自二叉搜索树的），它的特点是：
1. 本身首先是一棵二叉搜索树。
2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
例如：
5 5
/ \ / \
2 6 2 6
/ \ \ / \
1 4 7 1 4
/ /
3 3
上图中，左边的是AVL树，而右边的不是。因为左边的树的每个结点的左右子树的高度之差的绝对值都最多为1，而右边的树由于结点6没有子树，导致根结点5的平衡因子为2。
3.为什么要用AVL树
有人也许要问：为什么要有AVL树呢？它有什么作用呢？
我们先来看看二叉搜索树吧（因为AVL树本质上是一棵二叉搜索树），假设有这么一种极端的情况：二叉搜索树的结点为1、2、3、4、5，也就是：
1
\
2
\
3
\
4
\
5
聪明的你是不是发现什么了呢？呵呵，显而易见——这棵二叉搜索树其实等同于一个链表了，也就是说，它在查找上的优势已经全无了——在这种情况下，查找一个结点的时间复杂度是O(N)！
好，那么假如是AVL树（别忘了AVL树还是二叉搜索树），则会是：
2
/ \
1 4
/ \
3 5
可以看出，AVL树的查找平均时间复杂度要比二叉搜索树低——它是O(logN)，但是插入操作可能会破坏平衡性另当别论了，也正是我们下面只讨论插入操作的原因。也就是说，在大量的随机数据中AVL树的表现要好得多。
假设有一个结点的平衡因子为2（在AVL树中，最大就是2，因为结点是一个一个地插入到树中的，一旦出现不平衡的状态就会立即进行调整，因此平衡因子最大不可能超过2），那么就需要进行调整。由于任意一个结点最多只有两个儿子，所以当高度不平衡时，只可能是以下四种情况造成的：
1. 对该结点的左儿子的左子树进行了一次插入。
2. 对该结点的左儿子的右子树进行了一次插入。
3. 对该结点的右儿子的左子树进行了一次插入。
4. 对该结点的右儿子的右子树进行了一次插入。
情况1和4是关于该点的镜像对称，同样，情况2和3也是一对镜像对称。因此，理论上只有两种情况，当然了，从编程的角度来看还是四种情况。
第一种情况是插入发生在“外边”的情况（即左-左的情况或右-右的情况），该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况（即左-右的情况或右-左的情况），该情况要通过稍微复杂些的双旋转来处理。注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点展开的。
4.1. LL型
平衡二叉树某一节点的左孩子的左子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向右旋转一次即可，如图所示，原A的左孩子B变为父结点，A变为其右孩子，而原B的右子树变为A的左子树，注意旋转之后Brh是A的左子树（图上忘在A于Brh之间标实线）
//情形1
AVLTree SingleRotateWithLeft(PAVLNode k2)
{
PAVLNode k1;
k1 = k2->l;
k2->l = k1->r;
k1->r = k2;
k2->h = MAX( Height( k2->l ), Height( k2->r ) ) + 1;
k1->h = MAX( Height( k1->l ), k2->h ) + 1;
return k1; /* New root */
}
4.2. RR型
平衡二叉树某一节点的右孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向左旋转一次即可，如图所示，原A右孩子B变为父结点，A变为其左孩子，而原B的左子树Blh将变为A的右子树。
//情形2
AVLTree SingleRotateWithRight(PAVLNode k1)
{
PAVLNode k2;
k2 = k1->r;
k1->r = k2->l;
k2->l = k1;
k1->h = MAX( Height( k1->l ), Height( k1->r ) ) + 1;
k2->h = MAX( Height( k2->r ), k1->h ) + 1;
return k2; /* New root */
}
4.3. LR型
平衡二叉树某一节点的左孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时需要旋转两次，仅一次的旋转是不能够使二叉树再次平衡。如图所示，在B节点按照RR型向左旋转一次之后，二叉树在A节点仍然不能保持平衡，这时还需要再向右旋转一次。
//情形3
AVLTree DoubleRotateWithLeft( PAVLNode k3 )
{
/* Rotate between K1 and K2 */
k3->l = SingleRotateWithRight( k3->l );
/* Rotate between K3 and K2 */
return SingleRotateWithLeft(k3);
}
4.4. RL型
平衡二叉树某一节点的右孩子的左子树上插入一个新的节点，使得该节点不再平衡。同样，这时需要旋转两次，旋转方向刚好同LR型相反。
//情形4
AVLTree DoubleRotateWithRight( PAVLNode k1 )
{
/* Rotate between K3 and K2 */
k1->r = SingleRotateWithLeft( k1->r );
/* Rotate between K1 and K2 */
return SingleRotateWithRight( k1 );
}
4.插入操作插入的核心思路是通过递归找到合适的位置，插入新结点，然后看新结点是否平衡（平衡因子是否为2），如果不平衡的话，就分成三种大情况以及两种小情况：
1. 在结点的左儿子(X < T->item)
o 在左儿子的左子树 (X < T->l-> item)，“外边”，要做单旋转。
o 在左儿子的右子树 (X > T->l-> item)，“内部”，要做双旋转。
2. 在结点的右儿子(X > T->item)
o 在右儿子的左子树(X < T->r-> item)，“内部”，要做双旋转。
o 在右儿子的右子树(X > T->r-> item)，“外边”，要做单旋转。
3. (X == T->item) ，对该节点的计数进行更新。
当进行了旋转之后，必定会有结点的“父结点”是需要更新的，例如：
2
/ \
1 4
/ \
3 5
\
6
上图是调整前的，下图是调整后的：
4
/ \
2 5
/ \ \
1 3 6
可以看出，根结点2不平衡，是由于它的右儿子的右子树插入了新的结点6造成的。因此，这属于“外边”的情况，要进行一次单旋转。于是我们就把结点4调整上来作为根结点，再把结点2作为4的左儿子，最后把结点2的右儿子修改为原来的结点4的左儿子。
实现代码：
AVLTree Insert(Item X, AVLTree T )
{
if( T == NULL )
{
/* Create and return a one-node tree */
T = (PAVLNode)malloc( sizeof(AVLNode ) );
if( T == NULL )
perror("malloc failed");
else
{
T->item = X;
T->h = 0;
T->l = T->r = NULL;
T->count = 1;
}
}
else if(compare(&X,&T->item) == -1)//插入情况1
{
T->l = Insert( X, T->l );
if( Height( T->l ) - Height( T->r ) == 2 )
if(compare(&X, &T->l->item ) == -1)//左边左子树 单旋转
T = SingleRotateWithLeft( T );
else
T = DoubleRotateWithLeft( T );//左边右子树
}
else if( compare(&X,&T->item) == 1 ) //插入情况2
{
T->r = Insert( X, T->r );
if( Height( T->r ) - Height( T->l ) == 2 )
if(compare(&X , &T->r->item) == 1)//右边右子树 单旋转
T = SingleRotateWithRight( T );
else
T = DoubleRotateWithRight( T );//右边左子树
}
else//插入情况3
T->count++;
/* Else X is in the tree already; we‘ll do nothing */
T->h = MAX( Height( T->l ), Height( T->r ) ) + 1;
return T;
}
总结一下我们来看一个例子：
具体步骤如下：
⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
设有关键码序列{20, 35, 40, 15, 30, 25, 38}，图7-3给出了平衡二叉树树的构造过程，结点旁边标出的是该结点的平衡因子。
数据结构&&AVL树原理、插入操作详解及实现