平衡树\(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来说，会用就行。
来源链接：https://www.cnblogs.com/ac-wyr/p/19011526
没有回复内容