平衡树Splay

平衡树\(Splay\)

前言

个人见解不代表我讲的一定正确，请参考其它文献阅读
（就当我瞎扯淡就行）
前置知识

二叉搜索树

简单叙述一下，具体操作请转至其它博客或oi.wiki
二叉搜索树，也称也称二叉排序树或二叉查找树，是一种基于二叉树的树形结构，满足该树为二叉树且中序遍历有序的性质
简单解释一下就是：对于每个结点至多有两个子节点，并且左子树内任意一个结点的大小小于结点，右节点内任意一个子节点都大于该结点。同时，二叉搜索树的任意一个子树也是二叉搜索树。
Splay

由上面可知，根据二叉搜索树的性质，在随机数据下，我们可以构造一个期望为\(log(n)\)深度的二叉树，以此达到\(log(n)\)时间复杂度的查询，修改操作，但是如果在特殊数据下，二叉搜索树会退化成一条链，例如插入的数字顺序为有序，则时间复杂度退化为\(O(N)\)，二平衡树都是基于二叉搜索树进行修改，以达到一种平衡使得树高尽可能小
\(Splay\)树的核心思想是利用旋转操作让常使用结点上移并且降低树高，降低时间复杂度。
我先会给出具体的操作流程然后简单说明原理。
具体操作

对于任何插入，删除，查询操作，都将目标数字进行一个\(Splay\)操作将目标结点旋转到根节点进行操作

• 旋转：将指定结点向上移动至其父亲并保证BST（即二叉搜索树）性质成立
  
• 查询：利用BST的性质，访问到一个结点时，如果其对应数字num，当x即查询数小于num是，说明x在左子树内，反之在右子树内
  
• 插入：在树中查找是否存在指定数x，如果存在，数量加一，不存在则在对应叶子节点位置插入新的叶子节点，并将这个新加入的结点旋转到根
  
• 删除，查询到x的位置，将其旋转到根结点，然后将其左子树的根设为根，右子树的根的父为现在的根
  

示例代码：（注释瞎看看得了，瞎写的，我自己也看不懂了）
[code]#includeusing namespace std;typedef long long ll;const int N = 1e5+10;struct Node{    ll val,cnt,size;    Node *ch[2], *fa;    Node(ll v,Node* f = nullptr) : val(v) , cnt(1), size(1), fa(f){        ch[0]=ch[1]=nullptr;    }    void push_up(){        size = cnt+(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0);    }};class SplayTree{private:    Node* root = nullptr;    ll get_dir(Node* p){//即判断所传入的节点p是其父亲节点的左子树还是右子树        return p->fa->ch[1]==p;    }        void rotate(Node* x){        Node* p = x->fa;//x的父亲        Node* g = p->fa;//x的爷爷        ll d=get_dir(x);//获取x是其父亲p的左还是右儿子        //开始进行旋转        //我们的目的是将x尽可能地往上移动，也就是将x移动到其父亲p的位置        //那么为了保证BST的正确性并且不让整棵树向上移        //考虑右旋：即x是p的左子树，令p的左子树为x的右子树，        //令x的左子树为A，右子树为B，在操作之前可以得到Afa=x;        x->fa=g;        if(g)g->ch[g->ch[1]==p]=x;        p->push_up();        x->push_up();    }    void Splay(Node* x,Node* to = nullptr){        while(x->fa != to){//将x移动到to的位置，默认为根            Node* p = x->fa;            Node* g = p->fa;            if(g != to){                if((g->ch[0]==p) == (p->ch[0]==x)){//当满足x的父亲与爷爷在同一方向时，x可向上旋转两次                    rotate(p);                }                else rotate(x);            }            rotate(x);        }        if(!to)root=x;    }    Node* find(Node* x,ll val){        while(x && x->val!=val){//当x这个点存在以及没找到对应值时往下寻找            if(val < x->val)x=x->ch[0];//由于BST的性质满足左子树小于根，所以如果查找的值小于目前的值就往左子树找，反之往右子树找            else x=x->ch[1];        }        return x;    }    Node* get_kth(Node* x,ll k){        while(x){//查询第k小            ll left = x->ch[0]?x->ch[0]->size:0;//获取x左子树的大小            if(kch[0];            }            else if(kcnt){//找到x                Splay(x);                return x;            }            else{                k -= left + x->cnt;                x = x->ch[1];//没有找到往右子树找            }        }        return nullptr;    }    Node* get_pre(Node* x){        x=x->ch[0];        while(x->ch[1]){            x=x->ch[1];        }        return x;    }    Node* get_suc(Node* x){        x=x->ch[1];        while(x->ch[0])x=x->ch[0];        return x;    }public:    void insert(ll val){        if(!root){//当根节点不存在时，即树内不存在数，将新插入的数设置为根            root = new Node (val);            return;        }        Node* cur = root;        Node* p = nullptr;        while(cur){            p = cur;//p在这里不断更新能够保证p是cur的根            if(val == cur -> val){//当在树中查找到指定数时，将这个数数量加一，并更新其子树，并且进行splay操作让val上调                cur->cnt++;                cur->push_up();                Splay(cur);//同时在查找时不断将cur提升到根                return;            }            cur = cur->ch[val > cur->val];        }        //当在数中没有找到指定值时，在叶子节点上新建一个点        Node* x = new Node(val,p);        p->ch[val > p->val] = x;        Splay(x);    }    void erase(ll val){        Node* x = find(root,val);        if(!x)return;//找到xde位置，如果不存在直接退出即可        Splay(x);        if(x->cnt>1){//当x的数量大于1时，直接减一即可，对树的结构没有影响            x->cnt--;            x->push_up();            return;        }        //此时说明x只有一个，考虑删除它对其左右子树的影响，进行分讨        if(!x->ch[0]){//此时说明x的左子树不存在，可以直接把右子树作为根            root = x->ch[1];            if(root)root->fa=nullptr;//这里要判断root是否存在，以免访问到空指针        }        else{//此时说明左子树存在            Node* pre = get_pre(x);//找到x在左子树中最大的数            Splay(pre);//将pre提升到根            pre->ch[1] = x->ch[1];            if(x->ch[1])x->ch[1]->fa =pre;            pre->push_up();            root = pre;            pre -> fa = nullptr;        }        delete x;    }    ll get_rank(ll val){        ll res=0;        Node* cur = root;        while(cur){            if(val < cur->val){                cur = cur->ch[0];            }            else{                res+=(cur->ch[0]?cur->ch[0]->size:0);                if(val == cur->val){                    Splay(cur);                    return res+1;                }                res+=cur->cnt;                cur=cur->ch[1];            }        }        return res+1;    }    ll get_val_rank(ll k){        Node* x = get_kth(root,k);        return x?x->val:-1;    }    ll get_predecessor(ll val){        insert(val);        Node* x = get_pre(root);        ll res = x?x->val:-1;        erase(val);        return res;    }    ll get_successor(ll val){        insert(val);        Node* x = get_suc(root);        ll res = x?x->val:-1;        erase(val);        return res;    }};SplayTree tree;int main(){    ios::sync_with_stdio(0);    cin.tie(0);    ll n,opt,x;    cin>>n;    while(n--){        cin>>opt>>x;        if(opt==1)tree.insert(x);        if(opt==2)tree.erase(x);        if(opt==3)cout