• PAT 1066 AVL树模板


    题目链接

    传送门

    题面

    在这里插入图片描述
    在这里插入图片描述

    题意

    让你建立一棵AVL树,不断的插入n个数,输出最终的根的val

    思路

    注意旋转函数和Splay的区别,Splay中的旋转函数中的p是会被提高的,而这里代码中的旋转函数,提高的是p的儿子结点;

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    其实对于LR以及RL我们将其看成两步即可,比如对于LR来说,先左旋当前点的左子树,再右旋当前点即可;

    对于RL同理;


    注意一点,这里调整是需要逐个检查路径上的所有点的平衡因子,如下图所示;

    在这里插入图片描述
    对照代码就比较容易理解了,就是一个dfs的过程;

    Code

    #include 
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 1e5 + 10;
    
    struct Tree{
        int s[2];
        int val;
    }tr[N];
    #define lc (tr[p].s[0])
    #define rc (tr[p].s[1])
    int getH(int p){
        if(!p) return 0;
        return max(getH(lc),getH(rc)) + 1;
    }
    int tot;
    void rotateR(int &p){
        int ls = lc;
        tr[p].s[0] = tr[tr[p].s[0]].s[1];
        tr[ls].s[1] = p;
        p = ls;
    }
    void rotateL(int &p){
        int rs = rc;
        tr[p].s[1] = tr[tr[p].s[1]].s[0];
        tr[rs].s[0] = p;
        p = rs;
    }
    int rt;
    void insert(int &p,int val){
        if(!p){
            p = ++tot;
            tr[p].s[0] = tr[p].s[1] = 0;
            tr[p].val = val;
            return;
        }
        if(val < tr[p].val){
            insert(lc,val);
            if(getH(lc) - getH(rc) == 2){
                if(val < tr[lc].val){
                    //LL 
                    rotateR(p);   
                }
                else{
                    //LR
                    rotateL(tr[p].s[0]);
                    rotateR(p);
                }
            }
        }
        else{
            insert(rc,val);
            if(getH(lc) - getH(rc) == -2){
                if(val > tr[rc].val){
                    //RR
                    rotateL(p);    
                }
                else{
                    //RL
                    rotateR(tr[p].s[1]);
                    rotateL(p);
                }
            }
        }
    }
    void solve(){
        int n;
        cin >> n;
        for(int i=1;i<=n;++i){
            int val;
            cin >> val;
            insert(rt,val);
        }
        cout << tr[rt].val << '\n';
    }
    signed main(){
        std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
        solve();
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
  • 相关阅读:
    leetcode 823. Binary Trees With Factors(因子二叉树)
    维度灾难 维数灾难 暂记
    搬砖神器 VScode
    【基础】Java面试题
    多表操作-外连接查询
    【C++数据结构】B树概念及其实现(详解)
    Linux下的进程控制-进程程序替换
    【Kafka】Kafka指标报告器 MetricsReporter ClusterResourceListener
    决胜未来:解锁新科技趋势的无尽可能性
    17 `bs对象.节点名h3.parent` parents 获取父节点 祖先节点
  • 原文地址:https://blog.csdn.net/weixin_45724872/article/details/126911983