平衡树Splay
平衡树\(Splay\)前言
个人见解不代表我讲的一定正确，请参考其它文献阅读
（就当我瞎扯淡就行）
前置知识
二叉搜索树
简单叙述一下，具体操作请转至其它博客或oi.wiki
二叉搜索树，也称也称二叉排序树或二叉查找树，是一种基于二叉树的树形结构，满足该树为二叉树且中序遍历有序的性质
简单解释一下就是：对于每个结点至多有两个子节点，并且左子树内任意一个结点的大小小于结点，右节点内任意一个子节点都大于该结点。同时，二叉搜索树的任意一个子树也是二叉搜索树。
Splay
由上面可知，根据二叉搜索树的性质，在随机数据下，我们可以构造一个期望为\(log(n)\)深度的二叉树，以此达到\(log(n)\)时间复杂度的查询，修改操作，但是如果在特殊数据下，二叉搜索树会退化成一条链，例如插入的数字顺序为有序，则时间复杂度退化为\(O(N)\)，二平衡树都是基于二叉搜索树进行修改，以达到一种平衡使得树高尽可能小
\(Splay\)树的核心思想是利用旋转操作让常使用结点上移并且降低树高，降低时间复杂度。
我先会给出具体的操作流程然后简单说明原理。
具体操作
对于任何插入，删除，查询操作，都将目标数字进行一个\(Splay\)操作将目标结点旋转到根节点进行操作
[*]旋转：将指定结点向上移动至其父亲并保证BST（即二叉搜索树）性质成立
[*]查询：利用BST的性质，访问到一个结点时，如果其对应数字num，当x即查询数小于num是，说明x在左子树内，反之在右子树内
[*]插入：在树中查找是否存在指定数x，如果存在，数量加一，不存在则在对应叶子节点位置插入新的叶子节点，并将这个新加入的结点旋转到根
[*]删除，查询到x的位置，将其旋转到根结点，然后将其左子树的根设为根，右子树的根的父为现在的根
示例代码：（注释瞎看看得了，瞎写的，我自己也看不懂了）
#includeusing namespace std;typedef long long ll;const int N = 1e5+10;struct Node{ ll val,cnt,size; Node *ch, *fa; Node(ll v,Node* f = nullptr) : val(v) , cnt(1), size(1), fa(f){ ch=ch=nullptr; } void push_up(){ size = cnt+(ch?ch->size:0)+(ch?ch->size:0); }};class SplayTree{private: Node* root = nullptr; ll get_dir(Node* p){//即判断所传入的节点p是其父亲节点的左子树还是右子树 return p->fa->ch==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==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==p) == (p->ch==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;//由于BST的性质满足左子树小于根，所以如果查找的值小于目前的值就往左子树找，反之往右子树找 else x=x->ch; } return x; } Node* get_kth(Node* x,ll k){ while(x){//查询第k小 ll left = x->ch?x->ch->size:0;//获取x左子树的大小 if(kch; } else if(kcnt){//找到x Splay(x); return x; } else{ k -= left + x->cnt; x = x->ch;//没有找到往右子树找 } } return nullptr; } Node* get_pre(Node* x){ x=x->ch; while(x->ch){ x=x->ch; } return x; } Node* get_suc(Node* x){ x=x->ch; while(x->ch)x=x->ch; 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; } //当在数中没有找到指定值时，在叶子节点上新建一个点 Node* x = new Node(val,p); p->ch = 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){//此时说明x的左子树不存在，可以直接把右子树作为根 root = x->ch; if(root)root->fa=nullptr;//这里要判断root是否存在，以免访问到空指针 } else{//此时说明左子树存在 Node* pre = get_pre(x);//找到x在左子树中最大的数 Splay(pre);//将pre提升到根 pre->ch = x->ch; if(x->ch)x->ch->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; } else{ res+=(cur->ch?cur->ch->size:0); if(val == cur->val){ Splay(cur); return res+1; } res+=cur->cnt; cur=cur->ch; } } 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
页:
[1]