平衡二叉树
平衡二叉树,任意结点深度差满足|deepDiff|<2
左高右低不平衡
图一处于平衡
图二新增节点N
此时左深右浅。需要右旋转。
右旋转,根节点P需要降,L需要升,将L与P之间的元素即,LR放置到P节点。
- 右旋转,P降级,因为不平衡,就需需要此消彼长形成平衡,也就是leftdeep-1,rightdeep+1.
- L上升,出现了问题LR的归处,LR存放着所有大于(平衡有序二叉树)L节点的数据,且下雨P的数据。而P因为失去了左子树L且左子树的右子树满足,L<LR<P,所以拿LR替代L称为P的新的左子树。
- P下降,P下降造成左子树遗失,刚好用L节点的右子树形成局部平衡二叉树,以此维护整个树的平衡。
右高左低不平衡
与前面的相反的操作。
插入操作可能会因为符号不统一,称为双旋转。
如图所示,新增节点后,对于P,不平衡因子为2,对于L不平衡银子为-2,所以需要先统一符号
- L左旋转,统一平衡符号
- P右旋转,形成新的平衡。
- 右旋转封装成方法
void R_Rotate(BiTree *P) { BiTree PL; //用来存放PL PL = (*P)->lchild; //赋值 (*P)->lchild = PL->rchild; //PL降级,将PL与P之间的数据PL->rchild挂到P的左子树上, //因为P降级的时候失去了P->lchild(PL),而PL->rchild的所有数据PLRData满足PL<PLRData<P //因此使用PL->rchild作为P的左子树。 PL->rchild = (*P); //P降级为PL的右节点 *P = PL; //新的P节点由原PL代替。 }
结合第一张图理解,讲解右旋转。
- 声明一个临时变量PL
- 存储P的左子树PL到变量变量PL
- 将P的左子树接为P的左子树
- 将PL的右子树变为原来的P。
- 新的P节点变成了原来的PL。
- 完结撒花。
- 左平衡(左边不平衡就会右旋转)
void LeftBalance(BiTree *P) { //开始维护平衡 BiTree PL, PLr; PL = (*P)->lchild; //定义PL switch (PL->bf) { case LH: //此时符号一致只需要进行简单右旋转就可以了。 (*P)->bf = PL->bf = EH; R_Rotate(P); break; case RH: //插入在右边,也就造成了符号不一致的问题。 //需要先对符号进行一致操作。 PLr = PL->rchild; switch (PLr->bf) { case LH: (*P)->bf = RH; PL->bf = EH; break; case EH: (*P)->bf = PL->bf = EH; break; case RH: (*P)->bf = EH; PL->bf = LH; break; } PLr->bf = EH; L_Rotate(&(*P)->lchild); R_Rotate(P); } }
-
如果是LH,即符号一致,只需要简单右旋转。根据图一的执行结果可以看出P->bf和PL->bf打成了平衡。
-
LH
-
EH
-
RH
-
源码
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
typedef struct BiTNode
{
int data; //数据
int bf; //平衡标志
struct BiTNode *lchild, *rchild;//左右子树
} BiTNode, *BiTree;
void R_Rotate(BiTree *P)
{
BiTree PL; //用来存放PL
PL = (*P)->lchild; //赋值
(*P)->lchild = PL->rchild;
//PL降级,将PL与P之间的数据PL->rchild挂到P的左子树上,
//因为P降级的时候失去了P->lchild(PL),而PL->rchild的所有数据PLRData满足PL<PLRData<P
//因此使用PL->rchild作为P的左子树。
PL->rchild = (*P);
//P降级为PL的右节点
*P = PL;
//新的P节点由原PL代替。
}
void L_Rotate(BiTree *P)
{
BiTree PR;
PR = (*P)->rchild;
(*P)->rchild = PR->lchild;
PR->lchild = (*P);
*P = PR;
}
#define LH + 1
#define EH 0
#define RH - 1
void LeftBalance(BiTree *P)
{
//开始维护平衡
BiTree PL, PLr;
PL = (*P)->lchild;
//定义PL
switch (PL->bf)
{
case LH:
//此时符号一致只需要进行简单右旋转就可以了。
(*P)->bf = PL->bf = EH;
R_Rotate(P);
break;
case RH:
//插入在右边,也就造成了符号不一致的问题。
//需要先对符号进行一致操作。
PLr = PL->rchild;
switch (PLr->bf)
{
case LH:
(*P)->bf = RH;
PL->bf = EH;
break;
case EH:
(*P)->bf = PL->bf = EH;
break;
case RH:
(*P)->bf = EH;
PL->bf = LH;
break;
}
PLr->bf = EH;
L_Rotate(&(*P)->lchild);
R_Rotate(P);
}
}
void RightBalance(BiTree *P)
{
BiTree PR, Rl;
PR = (*P)->rchild;
switch (PR->bf)
{
case RH:
(*P)->bf = PR->bf = EH;
L_Rotate(P);
break;
case LH:
Rl = PR->lchild;
switch (Rl->bf)
{
case RH: (*P)->bf = LH;
PR->bf = EH;
break;
case EH: (*P)->bf = PR->bf = EH;
break;
case LH: (*P)->bf = EH;
PR->bf = RH;
break;
}
Rl->bf = EH;
R_Rotate(&(*P)->rchild);
L_Rotate(P);
}
}
// P 根节点
// e 是数据
// tasller 用来做变高回溯,方便判断是否需要旋转。
Status InsertAVL(BiTree *P, int e, Status *taller)
{
if (!*P)
{
*P = (BiTree)malloc(sizeof(BiTNode));
(*P)->data = e;
(*P)->lchild = (*P)->rchild = NULL;
(*P)->bf = EH;
*taller = TRUE;
//新增几点处于平衡,新增节点同时也可能造成了失衡。
}
else
{
if (e == (*P)->data)
{
*taller = FALSE;
return FALSE;
}
if (e < (*P)->data)
{
if (!InsertAVL(&(*P)->lchild, e, taller))
{//没变高说明找到重复数据
return FALSE;
}
if (*taller)
{//变高了说明插入到左节点成功,但是可能形成不平衡
switch ((*P)->bf)
{
case LH:
//原本就是左边高,此时左边更高,需要维护平衡。
LeftBalance(P);
*taller = FALSE;
break;
case EH:
(*P)->bf = LH;
*taller = TRUE;
break;
case RH:
(*P)->bf = EH;
*taller = FALSE;
break;
}
}
}
else
{
if (!InsertAVL(&(*P)->rchild, e, taller))
{
return FALSE;
}
if (*taller)
{
switch ((*P)->bf)
{
case LH:
(*P)->bf = EH;
*taller = FALSE;
break;
case EH:
(*P)->bf = RH;
*taller = TRUE;
break;
case RH:
RightBalance(P);
*taller = FALSE;
break;
}
}
}
}
return TRUE;
}
int main(void)
{
int i;
int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
BiTree P = NULL;
Status taller;
for (i = 0; i < 10; i++)
{
InsertAVL(&P, a[i], &taller);
}
return 0;
}