第五章树 14 AcWing 1552. AVL树的根

墨蓝 2023-09-24 14:02 108阅读 0赞

## 第五章 树 14 AcWing 1552. AVL树的根 ##

### 原题链接 ###

[AcWing 1552. AVL树的根][AcWing 1552. AVL]

### 算法标签 ###

平衡树

### 思路 ###

AVL树，即平衡二叉搜索树，当一棵二叉搜索树的左右子树高度相差(平衡因子)小于等于1时，我们称其为平衡二叉搜索树。  
当一棵二叉搜索树在插入数据时平衡被打破，我们需要手动调整树的节点使其重新满足平衡二叉搜索树的性质。

#### 平衡二叉树的基本操作 ####

平衡二叉搜索树有两种基本操作：左旋与右旋![请添加图片描述][8187d12da0974da6afb837812311d74b.png]

##### 右旋 #####

###### 具体步骤 ######

使用临时变量保存根节点(即旋转节点)的左子树  
将根节点的左子树设置为左子树的右子树  
将保存的左子树的右子树设置为根节点。  
更新根节点以及该节点左子树的高度(注意顺序，由于此时根节点已经成为原左子树的右子树)。  
将根节点设置为临时保存的左子树

###### 代码 ######

void R(int &u){
        int p=l[u];
        l[u]=r[p],r[p]=u;
        update(u),update(p);
        u=p;
    }

##### 左旋 #####

使用临时变量保存根节点(即旋转节点)右子树  
将根节点的右子树设置为右子树的左子树  
将保存的右子树的左子树设置为根节点。  
更新根节点以及该节点右子树的高度(注意顺序，由于此时根节点已经成为原先右子树的左子树)。  
将根节点设置为临时保存的右子树

###### 代码 ######

void R(int &u){
        int p=r[u];
        r[u]=l[p],l[p]=u;
        update(u),update(p);
        u=p;
    }

##### 平衡二叉树的失衡情形以及对应解决方法 #####

使平衡二叉树失去平衡主要有四种情形:

1.  左子树比右子树高2

*  左子树的左子树比左子树的右子树高1(对应下图①)
 *  左子树的右子树比左子树的左子树高1(对应下图③)

1.  右子树比左子树高2

*  右子树的右子树比右子树的左子树高1(对应下图②)
 *  右子树的左子树比右子树的右子树高1(对应下图④)  
    ![请添加图片描述][74344f561cf4409b9ea3babdc382dd80.png]  
    解决方法为:

*  R(root)
 *  L(l\[root\]), R(root)

*  L(root)
 *  R(r\[root\]), L(root)

这里的root指的是左右不平衡的节点(平衡因子大于2或小于-2)

### 代码 ###

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N = 10005;
    //int t, n, m, cnt, ans; 
    // l[i]存储节点i的左节点 r[i]存储节点i的左节点 v[i]存储节点i的权值 h[i]存储节点i的高度 idx存储当前已用到的节点个数
    int l[N], r[N], v[N], h[N], idx;
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    // 计算节点u高度 即左右节点最高高度+1
    void update(int u){
        h[u]=max(h[l[u]], h[r[u]])+1;
    }
    // 对于传入的u值 也需要改变
    void R(int &u){
        int p=l[u];
        l[u]=r[p], r[p]=u;
        update(u), update(p);
        u=p;
    }
    // 左旋
    void L(int &u){
        int p=r[u];
        r[u]=l[p], l[p]=u;
        update(u), update(p);
        u=p;
    }
    // 右旋
    int get_l(int u){
        return h[l[u]]-h[r[u]];
    }
    // 子节点w插入根节点u中 
    void insert(int &u, int w){
        if(!u){
            u=++idx;
            v[u]=w;
        }else if(w<v[u]){
            insert(l[u], w);
            if(get_l(u)==2){
                if(get_l(l[u])==1){
                    R(u);
                }else{
                    L(l[u]), R(u);    
                }
            }
        }else{
            insert(r[u], w);
            if(get_l(u)==-2){
                if(get_l(r[u])==-1){
                    L(u);
                }else{
                    R(r[u]), L(u);
                }
            }
        }
        update(u);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int n=rd(), root=0;
    	rep(i, 0, n){
    	    int w=rd();
    	    insert(root, w);
    	}
    	printf("%lld", v[root]);
    	return 0;
    }

### 参考文献 ###

[AcWing 1552. AVL树的根（PAT甲级辅导课）y总视频讲解][AcWing 1552. AVL_PAT_y]  
[AcWing 1552. AVL树详解][AcWing 1552. AVL 1]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1552. AVL]: https://www.acwing.com/problem/content/1554/
[8187d12da0974da6afb837812311d74b.png]: https://img-blog.csdnimg.cn/8187d12da0974da6afb837812311d74b.png
[74344f561cf4409b9ea3babdc382dd80.png]: https://img-blog.csdnimg.cn/74344f561cf4409b9ea3babdc382dd80.png
[AcWing 1552. AVL_PAT_y]: https://www.acwing.com/video/1077/
[AcWing 1552. AVL 1]: https://www.acwing.com/solution/content/23562/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png