C++中AVL树构建详解

朴灿烈づ我的快乐病毒、 2023-03-13 11:37 110阅读 0赞

#### AVL树的定义 ####

平衡二叉树由前苏联两位数学家GM.Adelse-Velskil、E.M.Landis提出，因此一般也称作AVL树。  
AVL树从本质上说仍是一颗二叉搜索树，只是在其的基础上添加了平衡要求，使得树的高度在每次插入元素后仍可以保持O（logn）的级别。  
所谓的平衡操作指的是对于AVL树的任意结点来说，其左子树和右子树的高度差的绝对值不超过1，其中左子树的高度减去右子树的高度称为该结点的**平衡因子**。  
例如，对于下面的三棵树，根结点的平衡因子分别是 -1、2、-2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]

#### 基本操作函数 ####

##### 1.结构体 #####

因为需要对每个结点计算平衡因子，所以需要在树的结构中加入一个变量**height用来记录以当前结点为根节点的子树的高度**

struct node{ 
    	int data,height;//权值和高度
    	node* l,*r;//左右孩子地址
    };

##### 2.获取当前结点root的高度 #####

空树的高度为0，叶子结点高度为1

int getheight(node* root)
    { 
    	if(root==NULL)return 0;
    	else return root->height;
    }

##### 3.求平衡因子 #####

每个结点的平衡因子是左子树高度减去右子树高度

int getbalancefactor(node* root)
    { 
    	return gethight(root->l)-getheight(root->r);
    }

##### 4.更新结点高度 #####

在插入结点或者旋转操作后树高会改变，所以在执行相应的操作时，需要实时的更新每个结点的高度

void updataheight(node* &root)
    { 
    	//当前结点的高度为左右子树中较大高度+1
    	root->height=max(getheight(root->l),getheight(root->r))+1;
    }

#### 旋转操作 ####

##### 1.左旋 #####

完成旋转一共需要三步：  
**1.让B的左子树成为A的右子树  
2.让A成为B的左子树  
3.将根节点设定为结点B**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 1]

void leftrotation(node* &root)
    { 
    	node* temp=root->r;
    	root->r=temp->l;
    	temp->l=root;
    	updateheight(root);
    	updateheight(temp);
    	root=temp;
    }

##### 2.右旋 #####

右旋和左旋是对称的过程，从本质上来看，他们互为逆操作  
相应的步骤：  
**1.让A的右子树成为B的左子树  
2.让B成为A的右子树  
3.将根节点设定为结点A**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 2]

void rightrotation(node* &root)
    { 
    	node* temp=root->l;
    	root->l=temp->r;
    	temp->r=root;
    	updateheight(root);
    	updateheight(temp);
    	root=temp;
    }

#### 插入操作 ####

每插入一个结点，一定会有结点的平衡因子发生变化，所以每插入一个结点，都需要更新一下树高，当某结点的平衡因子等于2或者-2时，以该结点为根结点的子树发生失衡，需要旋转调整。在这基础上我们还需判断其相应的子树，以确定相应的翻转操作。  
下面我们**先讨论平衡因子为2的情况**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 3]  
对于根结点A，其平衡因子都为2，但是对于A的左子树B，可以发现左边的平衡因子为1，右边的为-1；对于这两种树型，左边的称为LL型树，右边的为LR型树

<table> 
 <thead> 
  <tr> 
   <th>树型</th> 
   <th>调整方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>LL</td> 
   <td>对根结点root右旋</td> 
  </tr> 
  <tr> 
   <td>LR</td> 
   <td>先对root-&gt;l 左旋，使之变为LL型树，再对root右旋</td> 
  </tr> 
 </tbody> 
</table>

**然后看对于平衡因子为-2的情况**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 4]  
左边为RR型树，右边为RL型树

<table> 
 <thead> 
  <tr> 
   <th>树型</th> 
   <th>调整方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>RR</td> 
   <td>对根结点root左旋</td> 
  </tr> 
  <tr> 
   <td>RL</td> 
   <td>先对root-&gt;r右旋使之转为RR型树，然后对root左旋</td> 
  </tr> 
 </tbody> 
</table>

void insert(node* &root,int x)
    { 
        if(root==NULL)
        { 
            root=new node;
            root->data=x;
            root->height=1;//叶子结点高度为1
            root->l=root->r=NULL;
            return;
        }
        if(x<root->data)
        { 
            insert(root->l,x);
            updataheight(root);
            if(getbalancefactor(root)==2)
            { 
                if(getbalancefactor(root->l)==1)//LL型树
                { 
                    right_rotation(root);
                }
                else//LR型树
                { 
                    left_rotation(root->l);
                    right_rotation(root);
                }
            }
        }
        else
        { 
            insert(root->r,x);
            updataheight(root);
            if(getbalancefactor(root)==-2)
            { 
                if(getbalancefactor(root->r)==-1)//RR型树
                left_rotation(root);
                else//RL型树
                { 
                    right_rotation(root->r);
                    left_rotation(root);
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230312/d451d637b0c94a1b88d11cfce762d651.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 1]: /images/20230312/720eab299a244f598b3a54134248b614.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 2]: /images/20230312/2574e73f9a734b18b83c9e30784d3244.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200513195136131.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200513200501837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70