首页 > 代码库 > 平衡二叉树（AVL）的介绍及基本操作
平衡二叉树（AVL）的介绍及基本操作
平衡二叉树又称为AVL树，它或者是一颗空树，或者是具有下列性质的二叉树:
（1）它的左子树和右子树都是平衡二叉树。
（2）左子树和右子树的深度之差的绝对值不超过1。
平衡二叉树中有一个重要的概念，平衡因子BF（Balance Factor）定义为该结点的左子树深度减去它的右子树的深度，根据平衡二叉树的性质可知，平衡因子只可能是-1、0和1。
AVL树是在二叉排序树的基础上进行定义的，因为AVL树上任何结点的左右子树深度之差不超过1，则可证明它的深度和logn是同数量级的，因此它的平均查找长度也和logn同数量级。
一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为A（即A是离插入节点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律可归纳为如下4种情况，分别为LL型、LR型、RR型和RL型，如下图：
（1）单向右旋处理：由于在A的左子树根结点的左子结点插入结点，A的平衡因子由1增至2，致使A为根的子树失去平衡，则需进行一次向右顺时针旋转操作，如上图（a）所示：
（2）单向左旋处理：由于在A的右子树根结点的右子节点插入结点，A的平衡因子由-1变为-2，致使以A为根结点子树失去平衡，则需进行一次向左逆时针旋转操作，如图（c）所示：
（3）双向旋转处理（先左后右）：由于在A的左子树根节点的右子树上插入结点，A的平衡因子由1增至为2，致使以A为根结点的子树失去平衡，则需要进行两次旋转操作（先左旋后右旋）。如上图（b）所示：第一次是以根节点A的左子结点B进行左旋，结果如上图（b）中间的图，接着是以对A结点进行右旋。
（4）双向旋转处理（先右后左）：由于在A的右子树根节点的左子树上插入结点，A的平衡因子由-1变为-2，致使以A为根结点的子树失去平衡，则需要进行两次旋转操作（先右旋后左旋）。如上图（b）所示：第一次是以根节点A的右子结点B进行左旋，结果如上图（d）中间的图，接着是以对A结点进行左旋。
在平衡二叉树进行插入一个元素e的新结点递归算法可以描述为如下：
（1）若AVL树为空，则插入一个元素进去作为树的根结点，树的深度增加1。
（2）若e的关键字与根节点相等，则不进行插入。
（3）若e的关键字小于根结点的关键字，则将e插入到根结点的左子树中，并且插入后左子树的深度增加1。分别有下列不同的情况处理：
a：如果当前的AVL树的根结点的平衡因子为-1，则把根结点的平衡因子改为0，AVL树的深度不变；
b：如果当前的AVL树的根节点的平衡因子为0，则把根结点的平衡因子改为1，AVL树的深度增加1；
c：如果当前的AVL树的根结点的平衡因子为1，若AVL树的左子树的根结点的平衡因子为1，需要进行单向右旋处理，并且右旋处理后，将根节点和其右子树结点上的平衡因子改为0，树的深度不变。
若AVL树的左子树的根结点的平衡因子为-1，则需要先向左后向右作旋转平衡处理，并且在旋转处理后，修改根结点和其左、右子树的根结点的平衡因子，树的深度保持不变。
（4）若e的关键字大于根结点的关键字，则将e插入到跟结点的右子树中，并且插入后右子树的深度增加1，分别针对不同情况进行处理，如上面对称。
针对以上分析，平衡二叉树的插入过程算法如下：
<span style="font-size:18px;"><span style="font-size:18px;">typedef struct AVLTNode
{
short data;
int bf; //结点的平衡因子;
struct AVLTNode* lchild,*rchild; //结点的左右子结点;
} AVLTNode,*AVLTree;
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
#define NULL 0
/*********************
*对结点作右旋处理;
******************************************/
void R_Rotate(AVLTree &p)
{
AVLTNode* q=p->lchild; //q为根结点p的左子树结点;
p->lchild=q->rchild; //p的左结点指向q的右结点;
q->rchild=p;
p=q; //改变返回的根节点;
}
/*********************
*对结点作左旋处理;
******************************************/
void L_Rotate(AVLTree &p)
{
AVLTNode* q=p->rchild;
p->rchild=q->lchild;
q->lchild=p;
p=q;
}
/**************
* 左平衡处理;
* 对T进行平衡度调整;
****************************************/
void LeftBalance(AVLTree &T)
{
AVLTNode* lc,*rd;
lc=T->lchild; // 获得T的左子树根结点;
switch (lc->bf) // 对做子节点的平衡度进行判断;
{
case LH: // 如果lc的平衡度为1,需要对T进行右旋处理;
T->bf=lc->bf=EH; // 右旋处理后,T与lc的平衡度都为0;
R_Rotate(T);
break;
case RH: // 如果lc的平衡度为-1;
rd=lc->rchild; // rd 指向T结点左节点的右子节点;
switch (rd->bf)
{
case LH:
T->bf = RH;
lc->bf = EH;
break;
case EH:
T->bf = lc->bf = EH;
break;
case RH:
T->bf = EH;
lc->bf =LH;
break;
}
rd->bf = EH;
L_Rotate(T->lchild); //对T的左子结点进行左旋处理;
R_Rotate(T); //再把T结点进行右旋处理;
}
}
/**************
* 右平衡处理;
* 对T进行平衡度调整;
****************************************/
void RightBalance(AVLTree& T)
{
AVLTNode* lc,*rd;
lc= T->rchild;
switch (lc->bf)
{
case RH:
T->bf = lc->bf = EH;
L_Rotate(T);
break;
case LH:
rd = lc->lchild;
switch(rd->bf)
{
case LH:
T->bf = EH;
lc->bf = RH;
break;
case EH:
T->bf = lc->bf = EH;
break;
case RH:
T->bf = EH;
lc->bf = LH;
break;
}
rd->bf = EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}
}
/******************
* taller 为true时标志树长高了，需要判断插入后树是否还保持平衡;
* 若在平衡二叉树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点。
* 并返回1，否则返回0。若因插入结点使得二叉排序树失去平衡，则作平衡旋转处理。
* 布尔变量taller反应T长高与否;
***********************************/
int InsertAVL(AVLTree& T,short e,bool& taller)
{
if(T==NULL) //如果T为空，插入新的结点，并标志树长高，置taller为TRUE;
{
T=(AVLTNode*)malloc(sizeof(AVLTNode));
T->bf=EH;
T->data=http://www.mamicode.com/e;>
综上所述：针对平衡二叉树的插入主要是使用递归算法，采用递归算法可以快速得出离插入结点最近的失衡结点A，从而采用上述四种类型来进行调整。最后，希望读者多多指教。
平衡二叉树（AVL）的介绍及基本操作