平衡二叉树（AVL树）
2022-08-21 本文已影响0人
lxr_
1.平衡二叉树（Self-Balancing Binary Search Tree 或者 Height-Balanced Binary Search Tree）是一种二叉排序树，其中每个结点的左子树和右子树的高度差之多等于1。
2.将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor),只可能是-1,0,1。
如下图左图中58结点的平衡因子为3，故不是平衡二叉树，经过调整后右图为平衡二叉树。
3.距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树，平衡二叉树的思想就是将不平衡消灭在最早时刻。
如下图中，插入结点37后，58,62结点的平衡因子都为2，但是以58为根结点的子树距离37结点最近，故该子树为最小不平衡子树。
最小不平衡子树
4.失衡二叉排序树的分析与调整:
平衡调整分为四种类型：LL型、LR型、RL型、RR型，通过调整原则：降低高度、保持二叉排序树的性质，当出现失衡二叉排序树时，其调整结果如下。
失衡二叉树的调整
当然，这些结点上还可能有其他结点，具体来说如下图所示：
LL型调整
RR型调整
LR型调整
RL型调整
注：实际情况不止图示的一种，新插入的结点可能位于某个结点的左孩子或者右孩子，都有可能
代码示例
AVL.h
#pragma once
#include <iostream>
using namespace std;
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
typedef struct BiTNode //平衡二叉树结点结构
{
int data; //结点数据
int bf; //结点的平衡因子
BiTNode* lchild, * rchild; //左右孩子指针
}*BiTree;
//右旋操作，顺时针
void R_Rotate(BiTNode*& p); //因为要修改指针，故需要传递二级指针（此处采用引用的方式）
//右旋操作，逆时针
void L_Rotate(BiTNode*& p);
//左平衡旋转（针对LL或者LR型）
void LeftBalance(BiTNode*& p);
//右平衡旋转（针对RR或者RL型）
void RightBalance(BiTNode*& p);
//插入平衡二叉树
bool InsertAVL(BiTree& T, int e, bool* taller);
//中序遍历
void InOrderTraverse(BiTree T);
AVL.cpp
#include "AVL.h"
//右旋操作，顺时针
void R_Rotate(BiTNode*& p)
{
BiTNode* l = p->lchild; //p的左孩子
p->lchild = l->rchild; //p的左孩子为左孩子的右孩子
l->rchild = p; //p的左孩子的右孩子为p
p = l; //p结点指向新的根结点
}
//右旋操作，逆时针
void L_Rotate(BiTNode*& p)
{
BiTNode* r = p->rchild; //p结点的右孩子
p->rchild = r->lchild;
r->lchild = p;
p = r;
}
//左平衡旋转（针对LL或者LR型）此时已经插入结点完成，需要进行平衡调整
void LeftBalance(BiTNode*& p)
{
BiTNode* l, * lr;
l = p->lchild; //p结点的左孩子
switch (l->bf) //检查左孩子的平衡度
{
case LH: //如果为左高，则为LL型
p->bf = l->bf = EH; //调整后p和l的平衡度为0
R_Rotate(p); //右旋
break;
case RH: //如果为右高，则为LR型
lr = l->rchild; //p结点左孩子的右孩子
//1.修改bf
switch (lr->bf)
{
case LH: //如果左高，说明添加在了lr的左子树上
p->bf = RH;
l->bf = EH;
break;
case EH: //如果为等高
p->bf = l->bf = EH;
break;
case RH: //如果为右高，则添加在了lr的右子树上
p->bf = EH;
l->bf = LH;
break;
default:
break;
}
//2.旋转
lr->bf = EH;
L_Rotate(p->lchild); //先左旋
R_Rotate(p); //后右旋
default:
break;
}
}
//右平衡旋转（针对RR或者RL型）
void RightBalance(BiTNode*& p)
{
BiTNode* r, * rl;
r = p->rchild;
switch (r->bf)
{
case RH: //如果为右高，则为RR型
p->bf = r->bf = EH;
L_Rotate(p);
break;
case LH: //如果为左高，则为RL型
rl = r->lchild; //p结点右孩子r的左孩子rl
//1.修改bf
switch (rl->bf)
{
case LH:
p->bf = EH;
r->bf = RH;
break;
case EH:
p->bf = r->bf = EH;
break;
case RH:
p->bf = LH;
r->bf = EH;
break;
default:
break;
}
//2.旋转
rl->bf = EH;
R_Rotate(p->rchild); //先右旋
L_Rotate(p); //后左旋
break;
default:
break;
}
}
//插入平衡二叉树
bool InsertAVL(BiTree& T, int e, bool* taller)
{
if (!T) //找到了插入位置
{
T = new BiTNode;
T->data = e;
T->lchild = T->rchild = NULL;
T->bf = EH;
*taller = true; //插入成功后，默认树长高
}
else
{
if (e == T->data) //树中已经存在和e有相同关键字的结点，则不再插入
{
*taller = false;
return false;
}
if (e < T->data) //如果插入值比根结点小，则在左子树中继续寻找
{
if (!InsertAVL(T->lchild, e, taller))
{
return false; //未插入成功
}
if (*taller) //如果插入成功，且左子树长高
{
switch (T->bf) //检查T的平衡度
{
case LH: //原本左子树比右子树高，需要左平衡处理
LeftBalance(T);
*taller = false;
break;
case EH: //原本左右子树等高，现在因左子树增高而树增高
T->bf = LH;
*taller = true;
break;
case RH:
T->bf = EH; //原本右子树比左子树高，现左右子树等高
*taller = false;
default:
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;
default:
break;
}
}
}
}
return true;
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
InOrderTraverse(T->lchild);
cout << T->data << " ";
InOrderTraverse(T->rchild);
}
main.cpp
#include "AVL.h"
#include <iostream>
using namespace std;
void test(int* p)
{
cout << "test:&p=" << &p << endl;
}
int main(int argc, char** argv)
{
int a[10] = { 3,2,1,4,5,6,7,10,9,8 };
BiTree T = NULL;
bool taller;
for (int i = 0; i < 10; i++)
{
InsertAVL(T, a[i], &taller);
}
InOrderTraverse(T);
return 0;
}
