当前位置：首页 > news >正文

平衡树Splay - AC

news 2025/9/29 8:30:29

平衡树\(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){//找到xSplay(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";}
}