-
平衡二叉搜索树，又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 —-来自百度百科
-
由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，所以，这也是平衡二叉树设计的初衷。那么平衡二叉树如何保持”平衡“呢？根据定义，有两个重点，一是左右两子树的高度差的绝对值不能超过1，二是左右两子树也是一颗平衡二叉树。
-
如下图所示，左图是一棵平衡二叉树，根节点10，左右两子树的高度差是1，而右图，虽然根节点左右两子树高度差是0，但是右子树15的左右子树高度差为2，不符合定义，所以右图不是一棵平衡二叉树。
由此可以看出平衡二叉树是一棵高度平衡的二叉查找树。所以，要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。
右旋
左旋
-
左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；
-
而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。
-
即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。
平衡二叉树调整方式的命名：LL、RR、LR、RL，并不是对调整过程的描述，而是对不平衡状态的藐视。如LL（Left-Left）调整，即插入节点落在最小不平衡子树根结点的左（L）孩子的左（L）子树上，对这种不平衡当时的调整称之为LL调整
右右
-
右右即为在原来平衡的二叉树上，在节点的右子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”13“，的左子树”15“，插入了节点”14“或”19“导致失衡。
-
右右只需对节点进行一次左旋即可调整平衡，如下图，对”11“节点进行左旋。
左左
- 左左即为在最小不平衡子树上，在节点的左子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”10“节点的左子树”7“，的左子树”4“，插入了节点”5“或”3“导致失衡。
-
左调整其实比较简单，只需要对节点进行右旋即可，如下图，对节点”10“进行右旋
左右
-
左右即为在原来平衡的二叉树上，在节点的左子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的左子树”7“，的右子树”9“，插入了节点”10“或”8“导致失衡。
-
左右的调整就不能像左左一样，进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋，结果图如下，右图的二叉树依然不平衡，而右图就是接下来要讲的右左，即左右跟右左互为镜像，左左跟右右也互为镜像。
-
右右跟左左一样，只需要旋转一次就能把树调整平衡，而左右跟右左也一样，都要进行旋转两次才能把树调整平衡，所以，首先上图的这种调整是错误的，正确的调整方式是，将左右进行第一次旋转，将左右先调整成左左，然后再对左左进行调整，从而使得二叉树平衡。
-
即先对上图的节点”7“进行左旋，使得二叉树变成了左左，之后再对”11“节点进行右旋，此时二叉树就调整完成，如下图
右左
- 右左即为在原来平衡的二叉树上，在节点的右子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”15“，的左子树”13“，插入了节点”12“或”14“导致失衡。
-
前面也说了，右左跟左右其实互为镜像，所以调整过程就反过来，先对节点”15“进行右旋，使得二叉树变成右右，之后再对”11“节点进行左旋，此时二叉树就调整完成，如下图：
- 节点的类型有三种：1.叶子节点；2.只有左子树或只有右子树；3.既有左子树又有右子树。
- 针对这三种节点类型，再引入判断②，所以处理思路分别是：
（1）当删除的节点是叶子节点，则将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型的失衡（左左，左右，右左，右右），然后进行调整。
（2）删除的节点只有左子树或只有右子树，这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。
（3）删除的节点既有左子树又有右子树，这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。
- 最后总结一下，平衡二叉树是一棵高度平衡的二叉树，所以查询的时间复杂度是 O(logN) 。插入的话上面也说，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，最多也只要旋转2次，所以，插入复杂度是 O(1) ，但是平衡二叉树也不是完美的，也有缺点，从上面删除处理思路中也可以看到，就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树—-红黑树。
平衡二叉树代码实现
#define LH 1
#define EH 0
#define RH -1
typedef struct BiTNode
{
int data;
int bf;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void R_Rotate(BiTree *p)
{
BiTree L;
L = (*p)->lchild;
(*p)->lchild = L->rchild;
L->rchild = (*p);
*p = L;
}
void LeftBalance(BiTree *T)
{
BiTree L, Lr;
L = (*T)->lchild;
switch(L->bf)
{
case LH:
(*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH:
Lr = L->rchild;
switch(Lr->bf)
{
case LH:
(*T)->bf = RH;
L->bf = EH;
break
case EH:
(*T)->bf = L->bf = EH;
break;
case RH:
(*T)->bf = EH;
L->bf = LH;
break;
}
Lr->bf = EH;
L_Rotate(&(*T)->lchild);
R_Rotate(T);
}
}
int InsertAVL(BiTree *T, int e, int *taller)
{
if( !*T )
{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = e;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = EH;
*taller = TRUE;
}
else
{
if(e == (*T)->data)
{
*taller = FALSE;
return FALSE;
}
if(e < (*T)->data)
{
if(!InsertAVL(&(*T)->lchild, e, taller))
{
return FALSE;
}
if(*taller)
{
switch((*T)->bf)
{
case LH:
LeftBalance(T);
*taller = FALSE;
break;
case EH:
(*T)->bf = LH;
*taller = TRUE;
break;
case RH:
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
}
else
{
if(!InsertAVL(&(*T)->rchild, e, taller))
{
return FALSE;
}
if(*taller)
{
switch((*T)->bf)
{
case LH:
(*T)->bf = EH;
*taller = FALSE;
break;
case EH:
(*T)->bf = RH;
*taller = TRUE;
break;
case RH:
RightBalance(T);
*taller = FALSE;
break;
}
}
}
}
}
网友评论