看过那么多次的调整平衡的策略,感觉都是假的,自己写(chao)一遍就懂了。
置简单说下思路:
数据结构:比二叉树多了一个平衡因子的参数。
程序利用递归自顶向下查找到要插入的点,以插入根节点的左节点为例,找到了就返回,返回的时候注意地检查平衡因子,若平衡因子显示右高,而我们插入的是左边,那么高度没有增加,从此结束;若平衡因子是左高,我们插入的是左边,那么这个时候就有可能是左左或者左右的情况了,要进行对应的调整,调整完就结束了;若平衡因子是平衡的,左边插入一个节点,高度增加1,但是还是保持平衡,高度增加1,继续向上检查。
参考文档:
1.平衡二叉树【注释无敌版】
2.Balancing a binary search tree
- 节点的插入
///////////////////////////////////平衡二叉树
static bool BecomeTaller;
typedef enum
{
LEFT_HIGH,
RIGHT_HIGH,
EQUALITY
}BF;
typedef struct AVLNode{
ElemType data;
struct AVLNode *lchild,*rchild;
BF BalanceFactor;
}AVLNode,*AVLTree;
//向右旋转
void R_Rotate(AVLTree *Tree)
{
AVLTree L=(*Tree)->lchild;
(*Tree)->lchild = L->rchild;
L->rchild = (*Tree);
(*Tree) = L;
}
//向左旋转
void L_Rotate(AVLTree *Tree)
{
AVLTree R = (*Tree)->rchild;
(*Tree)->rchild = R->lchild;
R->lchild = (*Tree);
(*Tree) = R;
}
//左树的平衡因子为2
void BalanceLeft(AVLTree *Tree)
{
AVLTree L = (*Tree)->lchild,Lr = L->rchild;
switch(L->BalanceFactor)
{
//左左
case LEFT_HIGH:
(*Tree)->BalanceFactor = EQUALITY;
(*Tree)->lchild->BalanceFactor = EQUALITY;
R_Rotate(Tree);
break;
//左右
case RIGHT_HIGH:
//要理解下面这段,需要画出来慢慢分析对,似乎没有办法怎么理解
switch(Lr->BalanceFactor)
{
case LEFT_HIGH:
(*Tree)->BalanceFactor = RIGHT_HIGH;
L->BalanceFactor = EQUALITY;
break;
case EQUALITY:
(*Tree)->BalanceFactor = L->BalanceFactor =EQUALITY;
break;
case RIGHT_HIGH:
(*Tree)->BalanceFactor = EQUALITY;
L->BalanceFactor = LEFT_HIGH;
break;
}
Lr->BalanceFactor = EQUALITY;
L_Rotate(&L);
R_Rotate(Tree);
break;
case EQUALITY:
(*Tree)->BalanceFactor = LEFT_HIGH;
BecomeTaller = true;
break;
}
}
void BalanceRight(AVLTree *Tree){
AVLTree Lr= (*Tree)->rchild,L;
switch(Lr->BalanceFactor)
{
case EQUALITY:
BecomeTaller = true;
(*Tree)->BalanceFactor = RIGHT_HIGH;
break;
case RIGHT_HIGH:
(*Tree)->BalanceFactor=Lr->BalanceFactor=EQUALITY;
L_Rotate(Tree);
break;
case LEFT_HIGH:
L = Lr->lchild;
switch(L->BalanceFactor)
{
case EQUALITY:
(*Tree)->BalanceFactor = Lr->BalanceFactor = EQUALITY;
break;
case RIGHT_HIGH:
Lr->BalanceFactor= EQUALITY;
(*Tree)->BalanceFactor = LEFT_HIGH;
break;
case LEFT_HIGH:
(*Tree)->BalanceFactor = LEFT_HIGH;
Lr->BalanceFactor = EQUALITY;
break;
}
L->BalanceFactor = EQUALITY;
R_Rotate(&Lr);
L_Rotate(Tree);
}
}
//AVL树插入
//向下插入,向上调整,递归刚刚好
//如果插入的时候没有相同的数字,返回true,否则返回false
bool AVL_Insert(AVLTree *Tree,ElemType Num,bool *BecomeTaller)
{
//插入新节点
if((*Tree)==NULL)
{
(*Tree) = (AVLNode*)malloc(sizeof(AVLNode));
(*Tree)->lchild = (*Tree)->rchild = NULL;
(*Tree)->data = Num;
(*Tree)->BalanceFactor = EQUALITY;
(*BecomeTaller) = true;
return true;
}
if (Num<((*Tree)->data))
{
if(!AVL_Insert(&((*Tree)->lchild),Num,BecomeTaller))
{
//还没有插入
return false;
}
else
{
//插入成功,且子树长高了,要进行调整
if (BecomeTaller)
{
switch ((*Tree)->BalanceFactor)
{
//如果树是右高,左侧插入了节点,平衡因子变为EQUALITY
case RIGHT_HIGH:
(*Tree)->BalanceFactor = EQUALITY;
(*BecomeTaller) = false;
break;
//左树高,还往左树插入新节点,属于左左类型,要调整
case LEFT_HIGH:
//这里的*Tree是新插入节点的爷爷!!!!!,不是爸爸,爸爸是不会到这里来的,
//所以问题简单多了,不用再找爷爷了;同时注意Tree就是左旋最上面的绳子。
//先调整树的平衡因子
BalanceLeft(Tree);
(*BecomeTaller) = false;
break;
case EQUALITY:
(*Tree)->BalanceFactor = LEFT_HIGH;
(*BecomeTaller) = true;
break;
}//switch ((*Tree)->BalanceFactor)
}//if (BecomeTaller)
return true;
}
}
else if(Num>((*Tree)->data))
{
if(!AVL_Insert(&((*Tree)->rchild),Num,BecomeTaller))
{
return false;
}
else
{
if ((*BecomeTaller)==true)
{
switch((*Tree)->BalanceFactor)
{
case EQUALITY:
(*Tree)->BalanceFactor = RIGHT_HIGH;
*BecomeTaller = true;
break;
case LEFT_HIGH:
(*Tree)->BalanceFactor =EQUALITY;
(*BecomeTaller) = false;
break;
case RIGHT_HIGH:
BalanceRight(Tree);
(*BecomeTaller) = false;
break;
}
}
return true;
}
}
else
{
return false;
}
}
创建
void AVL_Create(AVLTree *Tree,ElemType Buff[],int len)
{
for (int i=0;i<len;i++)
{
AVL_Insert(Tree,Buff[i],&BecomeTaller);
}
}