平衡二叉树详解

目次
平衡二叉树的定义
平衡二叉树的基本操纵
查找
插入
AVL树的建立

平衡二叉树的定义

平衡二叉树仍然是一棵二叉查找树，只是在其底子上增加了平衡的要求，也就是其左右子树的高度之差的绝对值不超过1。
在定义树的结构时需要加入一个变量height，用来记载以当前结点为根节点的子树的高度。

1. struct node{
2.         int v,height;
3.         node *lchild,*rchild;
4. };

复制代码

在这种定义下，如果需要新建一个结点，就可以使用如下写法：

1. node* newNode(int v){
2.         node* Node=new node;
3.         Node->v=v;
4.         Node->height=1;
5.         Node->lchild=Node->rchild=NULL;
6.         return Node;
7. }

复制代码

显然，可以通过下面的函数获取结点root地点子树的当前高度：

1. int getheight(node* root){
2.         if(root==NULL){
3.                 return 0;
4.         }
5.         return root->height;
6. }

复制代码

于是根据定义，就可以通过下面的函数计算左右子树的高度差：

1. int getbalancefactor(node* root){
2.         return getheight(root->lchild)-getheight(root->rchild);
3. }

复制代码

显然，结点root地点子树的高度即是其左右子树高度的较大值加1.

1. void updateheight(node* root){
2.         root->height=max(getheight(root->lchild),getrchild(root->rchild))+1;
3. }

复制代码

平衡二叉树的基本操纵

查找

1. void search(node* root,int x){
2.         if(root==NULL){
3.                 printf("search failed\n");
4.                 return;
5.         }
6.         if(x==root->data){
7.                 printf("%d\n",root->data);
8.         }
9.         else if(x<root->data){
10.                 search(root->lchild,x);
11.         }
12.         else{
13.                 search(root->rchild,x);
14.         }
15. }

复制代码

插入

左旋的代码

1. void L(node* &root){
2.         node* temp=root->rchild;
3.         root->rchild=temp->lchild;
4.         temp->lchild=root;
5.         updataheight(root);
6.         updataheight(temp);
7.         root=temp;
8. }

复制代码

右旋的代码

1. void R(node* &root){
2.         node* temp=root->lchild;
3.         root->lchild=temp->rchild
4.         temp->rchild=root;
5.         updataheight(root);
6.         updataheight(temp);
7.         root=temp;
8. }

复制代码

对于各种树型使用的操纵如下：

 起首，AVL树的插入代码是在二叉查找树的插入代码的底子上增加平衡操纵的，因此，如果不考虑平衡操纵，代码是下面如许的：

1. void insert(node* &root,int v){
2.         if(root==NULL){
3.                 root=newNode(v);
4.                 return;
5.         }
6.         if(v<root->data){
7.                 insert(root->lchild,v);
8.         }
9.         else{
10.                 insert(root->rchild,v);
11.         }
12. }

复制代码

在这个底子上，由于需要从插入的结点开始从下往下判断结点是否失衡，因此需要在每个insert函数之后更新当前子树的高度，并在这之后根据树型是LL型、LR型、RR型、RL型之一来举行平衡操纵。

1. void insert(node* &root,int v){
2.         if(root==NULL){
3.                 root=newNode(v);
4.                 return;
5.         }
6.         if(v<root->data){
7.                 insert(root->lchild,v);
8.                 updataheight(root);
9.                 if(getbalancefactor(root)==2){
10.                         if(getbalancefactor(root->lchild)==1){//L型
11.                                 R(root);
12.                         }
13.                         else if(getbalancefactor(root->lchild)==-1){//LR型
14.                                 L(root->lchild);
15.                                 R(root);
16.                         }
17.                 }
18.         }
19.         else{
20.                 insert(root->rchild,v);
21.                 updataheight(root);
22.                 if(getbalancefactor(root)==-2){
23.                         if(getbalancefactor(root->lchild)==-1){//RR型
24.                                 L(root);
25.                         }
26.                         else if(getbalancefactor(root->rchild)==1){//RL型
27.                                 R(root->rchild);
28.                                 L(root);
29.                         }
30.                 }
31.         }
32. }

复制代码

AVL树的建立

1. node* Create(int data[],int n){
2.         node* root=NULL;
3.         for(int i=0;i<n;i++){
4.                 insert(root,data[i]);
5.         }
6.         return root;
7. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告