一、平衡二叉树的定义
平衡二叉树是由前苏联两位科学家G.M.Adelse-Velskil和E.M.Landis提出，因此一般也称作AVL树。AVL树仍然是一颗二叉查找树，只是在其基础上增加了“平衡”的要求。所谓平衡是指，对AVL树的任意结点来说，其左子树与右子树的高度之差的绝对值不超过1；其中左子树与右子树的高度之差称为该结点的平衡因子。只要能随时保证每个结点平衡因子的绝对值不超过1，AVL的高度就始终能保持O(logn)级别。由于需要对每个结点都得到平衡因子，因此需要在树的结构中加入一个变量height，用来记录以当前结点为根结点的子树的高度：
struct node{
int v, height;//v为结点的权值，height为当前子树高度
node *lchild, *rchild;//左右孩子结点地址
};
在这种定义下，如果需要新建一个结点，就可以采用如下写法:
/**********生成一个新结点，v为结点权值**********/
node* newNode(int v){
node* Node = new node; //申请一个node型变量的地址空间
Node->v = v; //结点权值为v
Node->height = 1; //结点高度初始为1
Node->lchild = Node->rchild = NULL; //初始状态没有左右孩子
return Node; //返回新建结点的地址
}
可以通过下面的函数获取结点root所在子树的当前高度：
/******获取以root为根结点的子树的当前height*******/
int getHeight(node* root){
if(root == NULL){
return 0; //空结点高度为0
}
return root->height;
}
于是根据定义，可以通过下面的函数计算平衡因子：
/*********计算结点root的平衡因子*********/
int getBanlanceFactor(node* root){
return getHeight(root->lchild) - getHeight(root->rchild); //左子树高度减右子树高度
}
结点root所在子树的height等于其左子树的height与右子树的height的较大值加1，因此可以通过下面的函数来更新height:
/******更新结点root的height*******/
void updateHeight(node* root){
root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
二、平衡二叉树的基本操作
1、查找操作/********search函数查找AVL树中数据域为x的结点*********/
void search(node* root, int x){
if(root == NULL){ //空树，查找失败
printf("search failed\n");
return;
}
if(x == root->data){ //查找成功，访问之
printf("%d\n", root->data);
}
else if(x < root->data){ //如果x比根结点的数据域小，说明x在左子树
search(root->lchild, x); //往左子树搜索x
}
else{ //如果x比根结点的数据域大，说明x在右子树
search(root->rchild, x); //往右子树上搜索x
}
}
2、插入操作
/************左旋(Left Rotation)************/
void L(node* &root){
node* temp = root->rchild; //root指向结点A,temp指向结点B
root->rchild = temp->lchild;
temp->lchild = root;
updateHeight(root); //更新结点A的高度
updateHeight(temp); //更新结点B的高度
root = temp;
}
/***********右旋(Right Rotation)*************/
void R(node* &root){
node* temp = root->lchild; //root指向结点B,temp指向结点A
root->lchild = temp->rchild;
temp->rchild = root;
updateHeight(root); //更新结点B的高度
updateHeight(temp); //更新结点A的高度
root = temp;
}
/**********插入权值为v的结点**********/
void insert(node* &root, int v){
if(root == NULL){ //到达空结点
root = newNode(v);
return;
}
if(v < root->v){ //v比根结点的权值小
insert(root->lchild, v); //往左子树插入
updateHeight(root); //更新树高
if(getBalanceFactor(root) == 2){
if(getBalanceFactor(root->lchild) == 1){ //LL型
R(root);
}
else if(getBalanceFactor(root->lchild) == -1){ //LR型
L(root->lchild);
R(root);
}
}
}
else{ //v比根结点的权值大
insert(root->rchild, v); //往右子树插入
updateHeight(root); //更新树高
if(getBalanceFactor(root) == -2){
if(getBalanceFactor(root->rchild) == -1){ //RR型
L(root);
}
else if(getBalanceFactor(root->rchild) == 1){ //RL型
R(root->rchild);
L(root);
}
}
}
}
3、AVL树的建立
/********AVL树的建立*********/
node* create(int data[], int n){
node* root = NULL; //新建空根结点root
for(int i = 0; i < n; i++){
insert(root, data[i]); //将data[0]~data[n-1]插入AVL树中
}
return root; //返回根结点
}