平衡树Splay如何为？

平衡树\(Splay\) 前言 个人见解不代表我讲的一定正确，请参考其它文献阅读 （就当我瞎扯淡就行） 前置知识 二叉搜索树 简单叙述一下，具体操作请转至其它博客或oi.wiki 二叉搜索树，也称也称二叉排序树或二叉查找树，是一种基于二叉树的树形结构，满足该树为二叉树且中序遍历有序的性质 简单解释一下就是：对于每个结点至多有两个子节点，并且左子树内任意一个结点的大小小于结点，右节点内任意一个子节点都大于该结点。同时，二叉搜索树的任意一个子树也是二叉搜索树。 Splay 由上面可知，根据二叉搜索树的性质，在随机数据下，我们可以构造一个期望为\(log(n)\)深度的二叉树，以此达到\(log(n)\)时间复杂度的查询，修改操作，但是如果在特殊数据下，二叉搜索树会退化成一条链，例如插入的数字顺序为有序，则时间复杂度退化为\(O(N)\)，二平衡树都是基于二叉搜索树进行修改，以达到一种平衡使得树高尽可能小 \(Splay\)树的核心思想是利用旋转操作让常使用结点上移并且降低树高，降低时间复杂度。 我先会给出具体的操作流程然后简单说明原理。 具体操作 对于任何插入，删除，查询操作，都将目标数字进行一个\(Splay\)操作将目标结点旋转到根节点进行操作 旋转：将指定结点向上移动至其父亲并保证BST（即二叉搜索树）性质成立 查询：利用BST的性质，访问到一个结点时，如果其对应数字num，当x即查询数小于num是，说明x在左子树内，反之在右子树内 插入：在树中查找是否存在指定数x，如果存在，数量加一，不存在则在对应叶子节点位置插入新的叶子节点，并将这个新加入的结点旋转到根 删除，查询到x的位置，将其旋转到根结点，然后将其左子树的根设为根，右子树的根的父为现在的根 示例代码：（注释瞎看看得了，瞎写的，我自己也看不懂了） #include<bits/stdc++.h> using 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，在操作之前可以得到A<x<B<p这一基本关系 //操作：使p的左子树为B，x的右子树的父亲为p，B的父为p，x的右子树为p，p的父亲为x，x的父亲是g，g的原先p的左右子树位置为x //根据以上操作可以得到：B<p,B_fa=p,P>x，A<x则A<x<B<P，说明无误 p->ch[d] = x->ch[d^1]; if(x->ch[d^1])x->ch[d^1]->fa=p; x->ch[d^1]=p; p->fa=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(k<=left){ x=x->ch[0]; } else if(k<=left+x->cnt){//找到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<<tree.get_rank(x)<<"\n"; if(opt==4)cout<<tree.get_val_rank(x)<<"\n"; if(opt==5)cout<<tree.get_predecessor(x)<<"\n"; if(opt==6)cout<<tree.get_successor(x)<<"\n"; } } 旋转的具体实现 旋转主要就分为左旋，右旋和双旋。 右旋： g / p / \ x C / \ A B 对于以上这个最基本的右旋图，操作结点为x，由BST可得A<x<B<P<C<g 现在进行右旋，将x移动到原本P的位置，为了使得BST性质满足，且其它结点尽量不比x浅，将p移动到x的右子树的位置，C依旧是p的右子树，同时A也还是x的左子树，但是由于x的右子树已经是p了，同时为了保证BST性质，将B设为P的左子树 最终状态如下： g / x / \ A p / \ B C 由图可以发现该子树任然满足原图中我们得到的关系：A<x<B<P<C<g 所以这种旋转方式是对的。 由上面这个证明过程，相信你也能轻易证明左旋和双旋的过程正确性(qwq) 算了左旋还是说一下吧 左旋： p \ x / \ A B 由图可知：p<A<x<B 旋转一下，让x代替P的位置，P成为x的左子节点，A成为P的左子节点 最终状态如下： x / \ p B / A 可得：A<p<x<B，完毕 那么为什么有双旋，双旋就是简单的旋转两次，有必要吗？——有~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~但是，我不会证明，对的，\(Splay\)的时间复杂度证明机器复杂，对于大部分OIer来说，会用就行。