y总 树（二）

AVL树(AVL树的中序遍历一定是有序序列)

avl树是一种自平衡二叉搜索树
在avl树中，任何节点的两个子树的高度最多相差1个
如果某个时间，某节点的两个子树之间的高度差超过1，则将通过树旋转进行重新平衡以恢复此属性，这里的旋转有两种方式，左旋和右旋，两者组合后又有两种方式，先左旋后右旋和 先右旋后左旋，所以总共有4种操作。

四种操作

构建一颗二叉搜索树dfdafda

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n,v[N],idx,l[N],r[N];
void insert(int &u,int w){
    if(!u) u = ++idx,v[u]=w;
    else if(v[u]<w){
        insert(l[u],w);
    }
    else{
        insert(r[u],w);
    }
}
int main(){
    cin>>n;
    int root = 0;
    for(int i=0;i<n;i++){
        int w;
        cin>>w;
        insert(root,w);
    }
    cout<<v[root];
    return 0;
}

添加平衡条件

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n,v[N],idx,l[N],r[N],h[N];
void update(int u)
{
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}
void R(int& u)
{
    int p = l[u];
    l[u] = r[p], r[p] = u;
    update(u);
    u = p;
}
void L(int& u)
{
    int p = r[u];
    r[u] = l[p], l[p] = u;
    update(u);
    u = p;
}
int get_balance(int u)
{
    return h[l[u]] - h[r[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_balance(u) == 2)
        {
            if (get_balance(l[u]) == 1) R(u);
            else L(l[u]), R(u);
        }
    }
    else
    {
        insert(r[u], w);
        if (get_balance(u) == -2)
        {
            if (get_balance(r[u]) == -1) L(u);
            else R(r[u]), L(u);
        }
    }
    update(u);
}
int main(){
    cin>>n;
    int root = 0;
    for(int i=0;i<n;i++){
        int w;
        cin>>w;
        insert(root,w);
    }
    cout<<v[root];
    return 0;
}

红黑树

数据结构中有一类特殊的平衡二叉搜索树，称为红黑树
满足下面的性质

• 节点是红色或黑色
• 根节点是黑色
• 每个红色节点的两个子节点都是黑色
• 从任一节点到每个叶子的所有路径包含相同数目的黑色节点

#include<bits/stdc++.h>
using namespace std;
const int N = 40;
unordered_map <int,int> pos;
int pre[N],in[N];
bool ans;
int build(int il, int ir, int pl, int pr, int& sum)
{
    int root = pre[pl];
    int k = pos[abs(root)];
    if (k < il || k > ir)
    {
        ans = false;
        return 0;
    }
    int left = 0, right = 0, ls = 0, rs = 0;
    if (il < k) left = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, ls);
    if (k < ir) right = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr, rs);
    if (ls != rs) ans = false;
    sum = ls;
    if (root < 0)
    {
        if (left < 0 || right < 0) ans = false;
    }
    else sum ++ ;
    return root;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        pos.clear();
        for(int i=0;i<n;i++){
            cin>>pre[i];
            in[i] = abs(pre[i]);
        }
        sort(in,in+n);
        for(int i=0;i<n;i++){
            pos[in[i]] = i;
        }
        ans = true;
        int sum;
        int root = build(0,n-1,0,n-1,sum);
        if(root<0) ans = false;
        if(ans) puts("Yes");
        else puts("No");
    }
    return 0;
}