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

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

原题链接

AcWing 1552. AVL树的根

算法标签

平衡树

思路

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

平衡二叉树的基本操作

平衡二叉搜索树有两种基本操作：左旋与右旋

右旋

具体步骤

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

代码

void R(int &u){
    int p=l[u];
    l[u]=r[p],r[p]=u;
    update(u),update(p);
    u=p;
}
1
2
3
4
5
6

左旋

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

代码

void R(int &u){
    int p=r[u];
    r[u]=l[p],l[p]=u;
    update(u),update(p);
    u=p;
}
1
2
3
4
5
6

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

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

1. 左子树比右子树高2

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

2. 右子树比左子树高2

• 右子树的右子树比右子树的左子树高1(对应下图②)
• 右子树的左子树比右子树的右子树高1(对应下图④)
  
  解决方法为:

• 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
#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)
using namespace std;
typedef pair 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