AVL–平衡二叉树的一些操作,杂记
//AVL--平衡二叉树的一些操作,杂记
//平衡二叉树的定义
//首先,AVL树仍然是一颗二叉查找树
//AVL树的数据结构
struct node{
int v,height; //v为结点权值,height为当前子树高度
node *lchild,*rchild;
};
//新建一个结点
//生成一个新结点,v为结点权值
node* new_node(int v)
{
node* Node=new node;
Node->v=v;
Node->height=1;
Node->lchild = Node->rchild = NULL;
return Node;
}
//获取根结点root的子树的当前height
int get_height(node* root)
{
if(root==NULL)
{
return 0;
}
return root->height;
}
//计算结点root的平衡因子
int get_balance(node* root)
{
return get_height(root->lchild)-get_height(root->rchild);
}
//更新结点root的height
void update_height(node* root)
{
//max(左孩子的height,右孩子的height)+1
root->height=max(get_height(root->lchild),get_height(root->rchild))+1;
}
//AVL 的基本操作
//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)
{
search(root->lchild,x);
}
else
{
search(root->rchild,x);
}
}
//2.插入操作
//左旋
void L(node* &root)
{
node* temp =root->rchild;
root->rchild=temp->lchild;
temp->lchild=root;
update_height(root);
update_height(temp);
root=temp;
}
//右旋
void R(node* &root)
{
node* temp=root->lchild;
root->lchild=temp->rchild;
temp->rchild=root;
update_height(root);
update_height(temp);
root=temp;
}
//不考虑 平衡操作 的insert函数
void insert(node* &root,int v)
{
if(root==NULL)
{
root=new_node(v);
return;
}
if(v<root->v)
{
insert(root->lchild,v);
}
else
{
insert(root->rchild,v);
}
}
//考虑加入 平衡操作的 insert函数
//插入权值为v的结点
void insert(node* &root,int v)
{
if(root==NULL)
{
root=new_node(v);
return;
}
if(v < root->v) //v比根结点的权值小
{
insert(root->lchild,v); //往左子树插入
update_height(root); //更新树高
if(get_balance(root) == 2 )
{
if(get_balance(root->lchild ==1)) //LL型
{
R(root);
}
else if(get_balance(root->lchild)== -1) //LRxing
{
L(root->lchild);
R(root);
}
}
}
else //v比根结点的权值大
{
insert(root->rchild,v);
update_height(root); //更新树高
if(get_balance(root)==2)
{
if(get_balance(root->rchild)== -1) //RR型
{
L(root);
}
else if(get_balance(root->rchild)==1) //RL型
{
R(root->rchild);
L(root);
}
}
}
}
//AVL 树的 建立
node* create(int data[] ,int n ) { node* root=NULL; for(int i=0;i<n;i++) { insert(root,data[i]); } return root; //返回根结点 }