7.9、平衡二叉树(Balanced Binary Tree)
简称平衡树(AVL树)—— 树上任一结点的左子树和右子树的高度只差不会超过1
结点的平衡因子 = 左子树高度 - 右子树高度
得到:平衡二叉树的结点的平衡因子只能为\(-1、0、1\)
最小不平衡树(LL)
最小不平衡树(RR)
最小不平衡树(LR)
最小不平衡树(RL)
左旋和右旋操作
代码实现
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define boolean int
#define true 1
#define false 0
//建立一个平衡二叉树的结构体
typedef struct AVLNode{
ElemType data;//数据
int heigth;//高度
struct AVLNode *lchild,*rchild;
}AVLNode ,*AVLTree;
int GetHeight(AVLNode *node){
return node == NULL ? 0:node->heigth;
}
int GetMax(int a,int b){
return a > b ? a : b;
}
//右旋操作
void llRotation(AVLNode *node,AVLNode **root){
AVLNode *p = node->lchild;
node->lchild = p->rchild;
p->rchild = node;
node->heigth = GetMax(GetHeight(node->lchild),GetHeight(node->rchild)) + 1;
p->heigth = GetMax(GetHeight(p->lchild),GetHeight(p->rchild)) + 1;
*root = p;
}
//左旋操作
void rrRotation(AVLNode *node,AVLNode **root){
AVLNode *p = node->rchild;
node->rchild = p->lchild;
p->lchild = node;
node->heigth = GetMax(GetHeight(node->lchild),GetHeight(node->rchild))+1;
p->heigth = GetMax(GetHeight(p->lchild),GetHeight(p->rchild))+1;
*root = p;
}
//建立一颗平衡二叉树
boolean AVL_Insert(AVLTree *T,ElemType e){
if(*T == NULL){
*T = (AVLTree)malloc(sizeof(AVLNode));
if(*T == NULL) return false;
(*T)->data = e;
(*T)->rchild = (*T)->lchild = NULL;
(*T)->heigth = 0;
}else if((*T)->data > e){
//小于往左走
AVL_Insert(&(*T)->lchild,e);
//拿到当前左右子树的高度
int lHeight = GetHeight((*T)->lchild);//左子树高度
int rHeight = GetHeight((*T)->rchild);//右子树高度
//判断高度差
if(lHeight - rHeight == 2){
//当前结点插入到该结点的左边;只有两种情况LL,LR
if((*T)->lchild->data > e){//插入到左边
//LL
llRotation(*T,T);//右旋
}else{
//LR
rrRotation((*T)->lchild,&(*T)->lchild);//左孩子的右孩子左旋
llRotation(*T,T);//左孩子右旋
}
}
}else if((*T)->data < e){
//大于往右走
AVL_Insert(&(*T)->rchild,e);
//拿到当前左右子树的高度
int lHeight = GetHeight((*T)->lchild);//左子树高度
int rHeight = GetHeight((*T)->rchild);//右子树高度
//判断高度差
if(rHeight - lHeight == 2){
//当前结点插入到该结点的右边;只有两种情况RR,RL
if((*T)->rchild->data < e){//插入到左边
//RR
rrRotation(*T,T);//左旋
}else{
//RL
llRotation((*T)->rchild,&(*T)->rchild);//右孩子的左孩子右旋
rrRotation(*T,T);//右孩子左旋
}
}
}else{
//等于返回插入失败
printf("插入的结点的值存在,插入失败\n");
return false;
}
//修改结点的高度
(*T)->heigth = GetMax(GetHeight((*T)->lchild),GetHeight((*T)->rchild)) + 1;
return true;
}
//访问结点
void Vist(AVLNode *node){
printf("%d , ",node->data);
}
//先序遍历
void PreOrder(AVLTree T){
if(T != NULL){
Vist(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
int main(){
AVLTree T = NULL;
int nums[5] = {5,4,3,2,1};
for(int i = 0;i < 5;i++){
AVL_Insert(&T,nums[i]);
}
PreOrder(T);
return 0;
}
//结果:
4 , 2 , 1 , 3 , 5 ,
标签:node,lchild,int,AVLNode,代码,GetHeight,二叉树,rchild,数据结构
From: https://www.cnblogs.com/shuisanya/p/16849432.html