splay

绝地灬酷狼 2022-08-14 04:54 95阅读 0赞

类别：二叉排序树

空间效率：O(n)  
时间效率：O(log n)内完成插入、查找、删除操作

创造者：Daniel Sleator和Robert Tarjan

优点：每次查询会调整树的结构，使被查询频率高的条目更靠近树根。  
  
注：所有图片来自wiki。

http://blog.csdn.net/cyberzhg/article/details/8058208

## Tree Rotation ##

![1349877565_2986.png][]

树的旋转是splay的基础，对于二叉查找树来说，树的旋转不破坏查找树的结构。

## **Splaying** ##

Splaying是Splay Tree中的基本操作，为了让被查询的条目更接近树根，Splay Tree使用了树的旋转操作，同时保证二叉排序树的性质不变。

Splaying的操作受以下三种因素影响：

*  节点x是父节点p的左孩子还是右孩子
 *  节点p是不是根节点，如果不是
 *  节点p是父节点g的左孩子还是右孩子

同时有三种基本操作：

### **Zig Step** ###

**![1349877709_4105.png][]**

当p为根节点时，进行zip step操作。

当x是p的左孩子时，对x右旋；

当x是p的右孩子时，对x左旋。

### **Zig-Zig Step** ###

![1349877744_7090.png][]

当p不是根节点，且x和p同为左孩子或右孩子时进行Zig-Zig操作。

当x和p同为左孩子时，依次将p和x右旋；

当x和p同为右孩子时，依次将p和x左旋。

### **Zig-Zag Step** ###

![1349877779_5253.png][]

当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。

当p为左孩子，x为右孩子时，将x左旋后再右旋。

当p为右孩子，x为左孩子时，将x右旋后再左旋。

## **应用** ##

Splay Tree可以方便的解决一些区间问题，根据不同形状二叉树先序遍历结果不变的特性，可以将区间按顺序建二叉查找树。

每次自下而上的一套splay都可以将x移动到根节点的位置，利用这个特性，可以方便的利用Lazy的思想进行区间操作。

对于每个节点记录size，代表子树中节点的数目，这样就可以很方便地查找区间中的第k小或第k大元素。

对于一段要处理的区间\[x, y\]，首先splay x-1到root，再splay y+1到root的右孩子，这时root的右孩子的左孩子对应子树就是整个区间。

这样，大部分区间问题都可以很方便的解决， 操作同样也适用于一个或多个条目的添加或删除，和区间的移动。

--------------------

### POJ2764 Feed the dogs ###

**[http://poj.org/problem?id=2764][http_poj.org_problem_id_2764]  
http://blog.csdn.net/cyberzhg/article/details/8058154**

**区间不会重叠，所以不可能有首首相同或尾尾相同的情况，读入所有区间，按照右端由小到大排序。然后通过维护splay进行第k小元素的查询操作。**

[cpp] view plain copy 
        
         #include <cstdio>   #include <cstring>   #include <algorithm>   using namespace std;   const int MAXN = 100005;   const int MAXM = 50005;   const int INF = 0x7FFFFFFF;      class SplayTree   {   public:       SplayTree()       {           nil = &_nil;           _nil.value = 0;           _nil.size = 0;           _nil.parent = nil;           _nil.child[LEFT] = nil;           _nil.child[RIGHT] = nil;       }          inline void clear()       {           nodeNumber = 0;           root = nil;           insert(-INF);           insert(INF);       }          inline void insert(const int value)       {           if(root == nil)           {               root = newNode(nil, value);               return;           }           Node *x = root;           while(true)           {               int dir = x->value < value;               if(x->child[dir] == nil)               {                   x->child[dir] = newNode(x, value);                   update(x);                   splay(x->child[dir], nil);                   return;               }               else               {                   x = x->child[dir];               }           }       }          inline void remove(const int value)       {           int k = find(value);           find(k - 1, nil);           find(k + 1, root);           root->child[RIGHT]->child[LEFT] = nil;           update(root->child[RIGHT]);           update(root);       }          inline int getKth(const int k)       {           find(k + 1, nil);           return root->value;       }          inline void print()       {           printf("Splay Tree: \n");           print(root);           printf("\n");       }private:       static const int LEFT = 0;       static const int RIGHT = 1;       struct Node       {           int value, size;           Node *parent, *child[2];       } _nil, node[MAXN];       int nodeNumber;       Node *root, *nil;          inline Node *newNode(Node *parent, const int value)       {           node[nodeNumber].value = value;           node[nodeNumber].size = 1;           node[nodeNumber].parent = parent;           node[nodeNumber].child[LEFT] = nil;           node[nodeNumber].child[RIGHT] = nil;           return &node[nodeNumber++];       }          inline void update(Node *x)       {           if(x == nil)           {               return;           }           x->size = x->child[LEFT]->size + x->child[RIGHT]->size + 1;       }          inline void rotate(Node *x, const int dir)       {           Node *p = x->parent;           p->child[!dir] = x->child[dir];           p->child[!dir]->parent = p;           x->child[dir] = p;           x->parent = p->parent;           if(p->parent->child[LEFT] == p)           {               p->parent->child[LEFT] = x;           }           else           {               p->parent->child[RIGHT] = x;           }           p->parent = x;           update(p);           update(x);           if(root == p)           {               root = x;           }       }          inline void splay(Node *x, Node *y)       {           while(x->parent != y)           {               if(x->parent->parent == y)               {                   if(x->parent->child[LEFT] == x)                   {                       rotate(x, RIGHT);                   }                   else                   {                       rotate(x, LEFT);                   }               }               else if(x->parent->parent->child[LEFT] == x->parent)               {                   if(x->parent->child[LEFT] == x)                   {                       rotate(x->parent, RIGHT);                       rotate(x, RIGHT);                   }                   else                   {                       rotate(x, LEFT);                       rotate(x, RIGHT);                   }               }               else               {                   if(x->parent->child[RIGHT] == x)                   {                       rotate(x->parent, LEFT);                       rotate(x, LEFT);                   }                   else                   {                       rotate(x, RIGHT);                       rotate(x, LEFT);                   }               }               update(x);           }       }          inline void find(int k, Node *y)       {           Node *x = root;           while(k != x->child[LEFT]->size + 1)           {               if(k <= x->child[LEFT]->size)               {                   x = x->child[LEFT];               }               else               {                   k -= x->child[LEFT]->size + 1;                   x = x->child[RIGHT];               }           }           splay(x, y);       }          inline int find(const int value)       {           Node *x = root;           int count = 0;           while(true)           {               if(x->value == value)               {                   return count + x->size - x->child[RIGHT]->size;               }               else if(x->value > value)               {                   x = x->child[LEFT];               }               else               {                   count += x->size - x->child[RIGHT]->size;                   x = x->child[RIGHT];               }           }       }          inline void print(Node *x)       {           if(x == nil)           {               return;           }           printf("%d: %d %d %d\n", x->value, x->child[LEFT]->value, x->child[RIGHT]->value, x->size);           print(x->child[LEFT]);           print(x->child[RIGHT]);       }   } splay;      struct Interval   {       int a, b, k, index;       bool operator < (const Interval &interval) const       {           return b < interval.b;       }   } interval[MAXM];int pretty[MAXN];int ans[MAXM];      int main()   {       int n, m;       while(~scanf("%d%d", &n, &m))       {           for(int i=1;i<=n;++i)           {               scanf("%d", &pretty[i]);           }           for(int i=0;i<m;++i)           {               scanf("%d%d%d", &interval[i].a, &interval[i].b, &interval[i].k);               interval[i].index = i;           }           sort(interval, interval + m);           splay.clear();           int a = 1, b = 0;           for(int i=0;i<m;++i)           {               for(int j=a;j<interval[i].a && j<=b;++j)               {                   splay.remove(pretty[j]);               }               for(int j=max(interval[i].a, b+1);j<=interval[i].b;++j)               {                   splay.insert(pretty[j]);               }               a = interval[i].a;               b = interval[i].b;               ans[interval[i].index] = splay.getKth(interval[i].k);           }           for(int i=0;i<m;++i)           {               printf("%d\n", ans[i]);           }       }       return 0;   }

### POJ3580 SuperMemo ###

[http://poj.org/problem?id=3580][http_poj.org_problem_id_3580]  
http://blog.csdn.net/cyberzhg/article/details/8053293

在序列首尾加上值为INF的点。一共六种操作：

1. ADD x y D

将x到y区间加上D。

利用lazy。将x-1位置splay到root，y+1位置splay到root的右孩子，这时y+1位置的左孩子就是区间的范围。

2. REVERSE x y 反转x到y区间

和ADD类似，记录区间是否反转，在需要的时候调换左右孩子。

3. REVOLVE x y T 将x到y区间循环右移T次

DELETE和INSERT的综合，两次区间操作。

4. INSERT x P 在x位置后插入P

和ADD类似，将区间设为空，插入新的数值。

5. DELETE x 删除x位置的数

和ADD类似，将最终区间设为空。

6. MIN x y 求x到y区间中的最小值

和ADD类似，记录所有子树的min，在旋转的过程中更新。

[cpp] view plain copy 
        
         #include <cstdio>   #include <cstring>   #include <algorithm>   using namespace std;   const int MAXN = 100005;   const int MAXM = 100005;   const int INF = 0x7fffffff;      class SplayTree   {   public:       SplayTree()       {           nil.size = 0;           nil.value = INF;           nil.min = INF;           nil.lchild = &nil;           nil.rchild = &nil;           nil.parent = &nil;       }          inline void make(int array[], int n)       {           nodeNumber = 0;           int mid = (n - 1) >> 1;           root = newNode(&nil, array[mid]);           root->lchild = make(0, mid - 1, root, array);           root->rchild = make(mid + 1, n - 1, root, array);           update(root);       }          inline void ADD(int x, int y, int D)       {           find(x, &nil);           find(y + 2, root);           root->rchild->lchild->lazy += D;       }          inline void REVERSE(int x, int y)       {           find(x, &nil);           find(y + 2, root);           root->rchild->lchild->isReverse ^= true;       }          inline void REVOLVE(int x, int y, int T)       {           int len = y - x + 1;           T = ((T % len) + len) % len;           if(T)           {               find(y - T + 1, &nil);               find(y + 2, root);               SplayNode *d = root->rchild->lchild;               root->rchild->lchild = &nil;               find(x, &nil);               find(x + 1, root);               root->rchild->lchild = d;               d->parent = root->rchild;           }       }          inline void INSERT(int x, int P)       {           find(x + 1, &nil);           find(x + 2, root);           root->rchild->lchild = newNode(root->rchild, P);       }          inline void DELETE(int x)       {           find(x, &nil);           find(x + 2, root);           root->rchild->lchild = &nil;       }          inline void MIN(int x, int y)       {           find(x, &nil);           find(y + 2, root);           pushdown(root->rchild->lchild);           printf("%d\n", root->rchild->lchild->min);       }          inline void print()       {           printf("Splay Linear: \n");           print(root);           printf("\n");       }          inline void prints()       {           printf("Splay Structure: \n");           prints(root);           printf("\n");       }      private:       struct SplayNode       {           int value, size, lazy;           SplayNode *parent, *lchild, *rchild;           int min;           bool isReverse;       } nil, node[MAXN + MAXM];       int nodeNumber;       SplayNode *root;          inline SplayNode *newNode(SplayNode *parent, const int value)       {           node[nodeNumber].value = value;           node[nodeNumber].size = 1;           node[nodeNumber].lazy = 0;           node[nodeNumber].parent = parent;           node[nodeNumber].lchild = &nil;           node[nodeNumber].rchild = &nil;           node[nodeNumber].min = value;           node[nodeNumber].isReverse = false;           return &node[nodeNumber++];       }          SplayNode *make(int l, int r, SplayNode *parent, int array[])       {           if(l > r)           {               return &nil;           }           int mid = (l + r) >> 1;           SplayNode *x = newNode(parent, array[mid]);           x->lchild = make(l, mid - 1, x, array);           x->rchild = make(mid + 1, r, x, array);           update(x);           return x;       }          inline void update(SplayNode *x)       {           if(x == &nil)           {               return;           }           x->size = x->lchild->size + x->rchild->size + 1;           x->min = min(x->value, min(x->lchild->min, x->rchild->min));       }          inline void pushdown(SplayNode *x)       {           if(x == &nil)           {               return;           }           if(x->isReverse)           {               swap(x->lchild, x->rchild);               x->lchild->isReverse ^= true;               x->rchild->isReverse ^= true;               x->isReverse = false;           }           if(x->lazy)           {               x->value += x->lazy;               x->min += x->lazy;               x->lchild->lazy += x->lazy;               x->rchild->lazy += x->lazy;               x->lazy = 0;           }       }          inline void rotateLeft(SplayNode *x)       {           SplayNode *p = x->parent;           pushdown(x->lchild);           pushdown(x->rchild);           pushdown(p->lchild);           p->rchild = x->lchild;           p->rchild->parent = p;           x->lchild = p;           x->parent = p->parent;           if(p->parent->lchild == p)           {               p->parent->lchild = x;           }           else           {               p->parent->rchild = x;           }           p->parent = x;           update(p);           update(x);           if(root == p)           {               root = x;           }       }          inline void rotateRight(SplayNode *x)       {           SplayNode *p = x->parent;           pushdown(x->lchild);           pushdown(x->rchild);           pushdown(p->rchild);           p->lchild = x->rchild;           p->lchild->parent = p;           x->rchild = p;           x->parent = p->parent;           if(p->parent->lchild == p)           {               p->parent->lchild = x;           }           else           {               p->parent->rchild = x;           }           p->parent = x;           update(p);           update(x);           if(root == p)           {               root = x;           }       }          inline void splay(SplayNode *x, SplayNode *y)       {           pushdown(x);           while(x->parent != y)           {               if(x->parent->parent == y)               {                   if(x->parent->lchild == x)                   {                       rotateRight(x);                   }                   else                   {                       rotateLeft(x);                   }               }               else if(x->parent->parent->lchild == x->parent)               {                   if(x->parent->lchild == x)                   {                       rotateRight(x->parent);                       rotateRight(x);                   }                   else                   {                       rotateLeft(x);                       rotateRight(x);                   }               }               else               {                   if(x->parent->rchild == x)                   {                       rotateLeft(x->parent);                       rotateLeft(x);                   }                   else                   {                       rotateRight(x);                       rotateLeft(x);                   }               }           }           update(x);       }          inline void find(int k, SplayNode *y)       {           SplayNode *x = root;           pushdown(x);           while(k != x->lchild->size + 1)           {               if(k <= x->lchild->size)               {                   x = x->lchild;               }               else               {                   k -= x->lchild->size + 1;                   x = x->rchild;               }               pushdown(x);           }           splay(x, y);       }          inline void print(SplayNode *x)       {           if(x == &nil)           {               return;           }           pushdown(x);           print(x->lchild);           printf("%d: %d %d %d %d\n", x->value, x->min, x->parent->value, x->lchild->value, x->rchild->value);           print(x->rchild);       }          inline void prints(SplayNode *x)       {           if(x == &nil)           {               return;           }           pushdown(x);           if(x->value == INF)           {               printf("INF : ");           }           else           {               printf("%d : ", x->value);           }           if(x->lchild == &nil)           {               printf("nil ");           }           else           {               if(x->lchild->value == INF)               {                   printf("INF ");               }               else               {                   printf("%d ", x->lchild->value);               }           }           if(x->rchild == &nil)           {               printf("nil\n");           }           else           {               if(x->rchild->value == INF)               {                   printf("INF\n");               }               else               {                   printf("%d\n", x->rchild->value);               }           }           prints(x->lchild);           prints(x->rchild);       }   } splayTree;      char buffer[128];int array[MAXN];int n, m;      int main()   {       int x, y, D, T, P;       scanf("%d", &n);       for(int i=1;i<=n;++i)       {           scanf("%d", &array[i]);       }       array[0] = INF;       array[n+1] = INF;       splayTree.make(array, n + 2);       scanf("%d", &m);       while(m--)       {           scanf("%s", buffer);           switch(buffer[0])           {           case 'A':               scanf("%d%d%d", &x, &y, &D);               splayTree.ADD(x, y, D);               break;           case 'R':               if('E' == buffer[3])               {                   scanf("%d%d", &x, &y);                   splayTree.REVERSE(x, y);               }               else               {                   scanf("%d%d%d", &x, &y, &T);                   splayTree.REVOLVE(x, y, T);               }               break;           case 'I':               scanf("%d%d", &x, &P);               splayTree.INSERT(x, P);               break;           case 'D':               scanf("%d", &x);               splayTree.DELETE(x);               break;           case 'M':               scanf("%d%d", &x, &y);               splayTree.MIN(x, y);               break;           }       }       return 0;   }

[1349877565_2986.png]: https://img-my.csdn.net/uploads/201210/10/1349877565_2986.png
[1349877709_4105.png]: https://img-my.csdn.net/uploads/201210/10/1349877709_4105.png
[1349877744_7090.png]: https://img-my.csdn.net/uploads/201210/10/1349877744_7090.png
[1349877779_5253.png]: https://img-my.csdn.net/uploads/201210/10/1349877779_5253.png
[http_poj.org_problem_id_2764]: http://poj.org/problem?id=2764
[http_poj.org_problem_id_3580]: http://poj.org/problem?id=3580