Splay（伸展樹）實現可分裂與合并的序列

對于BST，除了Treap樹之外，還有一種Splay的伸展樹，他能快速的分裂與合并。

?

重要的操作是伸展操作，將一個指定的結點 x 旋轉到根的過程。

分三種情況，一次單旋，兩次同向單旋，兩次反向旋轉。可以手動模擬一下這個過程。

?

到這里，問題常常是將序列的第 k 個元素旋轉到根。

首先，要知道的是伸展樹里面v存的是什么，是節點的編號（下標）。這樣才能像 Treap實現名次樹那樣，很方便的找到左邊第 k 個元素。

//將序列左數第k個元素選擇到根 void splay(Node* &o,int k) { ? o->pushdown(); ? int d = o->cmp(k); ? if(d==1) k-=o->ch[0]->s + 1; ? if(d!=-1) { ? ? ? Node* p = o->ch[d]; ? ? ? ? p->pushdown(); ? ? ? int d2 = p->cmp(k); ? ? ? int k2 = (d2==0 ? k : k - p->ch[0]->s - 1); ? ? ? if(d2!=-1) { ? ? ? ? ? splay(p->ch[d2],k2); ? ? ? ? ? if(d==d2) rotate(o,d^1); ? ? ? ? ? else rotate(o->ch[d],d); ? ? ? } ? ? ? rotate(o,d^1); ? } }

?

分裂與合并：

分裂：從序列從左第 k 個元素分裂，就是將序列的 o 的第 K 小元素伸展到根，斷開樹根與右子節點。

合并：將left部分最大的元素旋轉到根，將right作為 left的右子樹。（保證right>left所有元素）。

// 合并操作。假定left所有元素小于 right Node* merge(Node* left,Node* right) { ? splay(left,left->s); ? left->ch[1] = right; ? left->maintain(); ? return left; } ? //把 o 前 k 個小結點放到left里面，其他放到ritht里面，如果不夠right = null void split(Node* o,int k,Node* &left,Node* &right) { ? splay(o,k); ? left = o; ? right = o->ch[1]; ? o->ch[1] = null; ? left->maintain(); }

?

有時，對于序列有反轉操作，這時，利用 線段樹的 lazy標記，標記某一段是否反轉。

對于，數據結構的定義：用一個Node數組，和一個Node 的 root指針，指向這個數組的元素。

?

?

#include <bits/stdc++.h>using namespace std;struct Node {Node *ch[2];int s;int flip;int v;int cmp(int k) const {int d = k - ch[0]->s;if(d==1) return -1; //序列第 k 個找到return d <=0 ? 0 : 1;}void maintain() {s = ch[0]->s + ch[1]->s + 1;}void pushdown() {if(flip) {flip = 0;swap(ch[0],ch[1]);ch[0]->flip = !ch[0]->flip;ch[1]->flip = !ch[1]->flip;}} };Node *null = new Node();// d = 0 左旋 void rotate(Node* &o,int d) {Node* k = o->ch[d^1];o->ch[d^1] = k->ch[d];k->ch[d] = o;o->maintain();k->maintain();o = k; }//將序列左數第k個元素選擇到根 void splay(Node* &o,int k) {o->pushdown();int d = o->cmp(k);if(d==1) k-=o->ch[0]->s + 1;if(d!=-1) {Node* p = o->ch[d];p->pushdown();int d2 = p->cmp(k);int k2 = (d2==0 ? k : k - p->ch[0]->s - 1);if(d2!=-1) {splay(p->ch[d2],k2);if(d==d2) rotate(o,d^1);else rotate(o->ch[d],d);}rotate(o,d^1);} }// 合并操作。假定left所有元素小于 right Node* merge(Node* left,Node* right) {splay(left,left->s);left->ch[1] = right;left->maintain();return left; }//把 o 前 k 個小結點放到left里面，其他放到ritht里面，如果不夠right = null void split(Node* o,int k,Node* &left,Node* &right) {splay(o,k);left = o;right = o->ch[1];o->ch[1] = null;left->maintain(); }const int maxn = 1e5+10; struct SplaySequence {int n;Node seq[maxn];Node *root;Node* build(int sz) {if(!sz) return null;Node* L = build(sz/2);Node* o = &seq[++n];o->v = n;o->ch[0] = L;o->ch[1] = build(sz-sz/2-1);o->flip = o ->s = 0;o->maintain();return o;}void init(int sz) {n = 0;null->s = 0;root = build(sz);for(int i = 0; i < sz; i++)printf("%d ",seq[i].v);puts("");}};vector<int> ans; void print(Node* o) {if(o!=null) {o->pushdown();print(o->ch[0]);ans.push_back(o->v);print(o->ch[1]);} }void debug(Node* o) {if(o!=null) {o->pushdown();debug(o->ch[0]);printf("%d \n",o->v -1);debug(o->ch[1]);} }SplaySequence ss;int main() {int n,m;scanf("%d%d",&n,&m);ss.init(n+1);debug(ss.root);for(int i = 0; i < m; i++) {int a,b;scanf("%d%d",&a,&b);Node* left,*mid,*right,*o;split(ss.root,a,left,o);split(o,b-a+1,mid,right);mid->flip ^=1;ss.root = merge(merge(left,right),mid);}print(ss.root);for(int i = 1; i < (int)ans.size(); i++)printf("%d\n",ans[i]-1);return 0; }

?

轉載于:https://www.cnblogs.com/TreeDream/p/7554716.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Uva 11922 Splay的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。