hihocoder #1329 : 平衡樹·Splay

#1329 : 平衡樹·Splay

時間限制: 10000ms 單點時限: 1000ms 記憶體限制: 256MB

描述

小Ho：小Hi，上一次你跟我講了Treap，我也實作了。但是我遇到了一個關鍵的問題。

小Hi：怎麼了？

小Ho：小Hi你也知道，我平時運氣不太好。是以這也反映到了我寫的Treap上。

小Hi：你是說你随機出來的權值不太好，進而導緻結果很差麼？

小Ho：就是這樣，明明一樣的代碼，我的Treap運作結果總是不如别人。小Hi，有沒有那種沒有随機因素的平衡樹呢？

小Hi：當然有了，這次我就跟你講講一種叫做Splay的樹吧。而且Splay樹能做到的功能比Treap要更強大哦。

小Ho：那太好了，你快告訴我吧！

輸入

第1行：1個正整數n，表示操作數量，100≤n≤200,000

第2..n+1行：可能包含下面3種規則：

1個字母'I'，緊接着1個數字k，表示插入一個數字k到樹中，1≤k≤1,000,000,000，保證每個k都不相同

1個字母'Q'，緊接着1個數字k。表示詢問樹中不超過k的最大數字

1個字母'D'，緊接着2個數字a,b，表示删除樹中在區間[a,b]的數。

輸出

若幹行：每行1個整數，表示針對詢問的回答，保證一定有合法的解

樣例輸入

6
I 1
I 2
I 3
Q 4
D 2 2
Q 2

樣例輸出

3

1

第一次領略到splay tree的厲害。。

小Hi：Splay樹，中文名一般叫做伸展樹。

和Treap樹相同，作為平衡樹，它也是通過左旋和右旋來調整樹的結構。

這裡我們再複習一下左旋和右旋操作：

hihocoder #1329 : 平衡樹·Splay

若以x作為參數(注意上一講中是以p作為參數)，其對應的僞代碼分别為：

right-rotate(x):
	p = x.father
	x.father = p.father
	If (p.father is not empty) Then
		If (p.father.left == p) Then
			p.father.left = x
		Else
			p.father.right = x
		End If
	Else
		root = x
	End If
	p.left = x.right
	x.right.father = p
	x.right = p
	p.father = x
	
left-rotate(x):
	p = x.father
	x.father = p.father
	If (p.father is not empty) Then
		If (p.father.left == p) Then
			p.father.left = x
		Else
			p.father.right = x
		End If
	Else
		root = x
	End If
	p.right = x.left
	x.left.father = p
	x.left = p
	p.father = x

和Treap樹不同的是，Splay樹不再用一個随機的權值來進行平衡，而是用固定的調整方式來使得調整之後的樹會比較平衡。

在左旋右旋的基礎上，Splay樹定義了3個操作：

1. Zig

hihocoder #1329 : 平衡樹·Splay

直接根據x節點的位置，進行左旋或右旋。

該操作将x節點提升了一層。

2. Zig-Zig

hihocoder #1329 : 平衡樹·Splay

若p不是根節點，還有父親節點g，且p和x同為左兒子或右兒子，則進行Zig-Zig操作：

當x,p同為左兒子時，依次将p和x右旋；

當x,p同為右兒子時，依次将p和x左旋。

注意此處不是将x連續Zig兩次。該操作将x節點提升了兩層。

3. Zig-Zag

hihocoder #1329 : 平衡樹·Splay

若p不是根節點，則p還有父親節點g。且p和x不同為左兒子或右兒子，則進行Zig-Zag操作：

當p為左兒子，x為右兒子時，将x節點先左旋再右旋；

當p為右兒子，x為左兒子時，将x節點先右旋再左旋。

該操作将x節點提升了兩層。

進一步在Zig,Zig-Zig和Zig-Zag操作上，Splay樹定義了"Splay"操作。

對于x以及x的祖先y，splay(x, y)，表示對x節點進行調整，使得x是y的兒子節點：

splay(x, y):
	While (x.father != y)
		p = x.father
		If (p.father == y) Then
			// 因為p的父親是y，是以隻需要将x進行Zig操作
			// 就可以使得x的父親變為y
			If (p.left == x) Then
				right-rotate(x)
			Else
				left-rotate(x)
			End If
		Else
			g = p.father
			If (g.left == p) Then
				If (p.left == x) Then
					// x,p同為左兒子，Zig-Zig操作
					right-rotate(p)
					right-rotate(x)
				Else
					// p為左，x為右，Zig-Zag操作
					left-rotate(x)
					right-rotate(x)
				End If
			Else
				If (p.right == x) Then
					// x,p同為右兒子，Zig-Zig操作
					left-rotate(p)
					left-rotate(x)
				Else 
					// p為右，x為左，Zig-Zag操作
					right-rotate(x)
					left-rotate(x)
				End If
			End If
		End If
	End While

在執行這個操作的時候，需要保證y節點一定是x節點祖先。

值得一提的是，大多數情況下我們希望通過splay操作将x旋轉至整棵樹的根節點。此時隻需令y=NULL即可實作。

小Ho：旋轉和Splay我懂了，但是要怎麼運用上去呢？

小Hi：Splay樹的插入和查詢操作和普通的二叉搜尋樹沒有什麼大的差別，需要注意的是每次插入和查詢結束後，需要對通路節點做一次Splay操作，将其旋轉至根。

insert(key):
	node = bst_insert(key) // 同普通的BST插入, node為目前插入的新節點
	splay(node, NULL)
	
find(key):
	node = bst_find(key) // 同普通的BST查找, node為查找到的節點
	splay(node, NULL)

同時由于Splay的特性，我們還有兩個特殊的查詢操作。在樹中查找指定數key的前一個數和後一個數。

我們先将key旋轉至根，那麼key的前一個數一定是根節點左兒子的最右子孫，同時key的後一個數一定是根節點右兒子的最左子孫。

findPrev(key):
	splay( find(key), NULL )
	node = root.left
	While (node.right)
		node = node.right
	Return node
	
	findNext(key):
	splay( find(key), NULL )
	node = root.right
	While (node.left)
		node = node.left
	Return node

splay中的删除key操作：

splay的删除可以采用和一般二叉搜尋樹相同的方法：即先找到節點key，若key沒有兒子則直接删去；若key有1個兒子，則用兒子替換掉x；若key有2個兒子，則通過找到其前(或後)一個節點來替換掉它，最後将該節點Splay到根。

同時，這裡還有另一種方法來完成删除操作：

首先我們查找到key的前一個數prev和後一個數next。将prev旋轉至根，再将next旋轉為prev的兒子。

此時key節點一定是next的左兒子。那麼直接将next的左兒子節點删去即可。

delete(key):
	prev = findPrev(key)
	next = findNext(key)
	splay(prev, NULL)
	splay(next, prev)
	next.left = NULL

這裡你可能會擔心如果key是數中最小或者是最大的數怎麼辦？

一個簡單的處理方式是手動加入一個超級大和超級小的值作為頭尾。

那麼小Ho，這裡有一個問題，假如要删除一個區間[a,b]的數該怎麼做？

小Ho：我想想...我知道了！

因為要删除[a,b]，那麼我就要想辦法把[a,b]的數旋轉到一個子樹上，再将這個子樹删掉就行了。

方法和删除一個數相同，我首先将a的前一個數prev和b的後一個數next找出來。

同樣将prev旋轉至根，再将next旋轉為prev的兒子。

那麼此時next的左子樹一定就是所有[a,b]之間的數了！

deleteInterval(a, b):
	prev = findPrev(a)
	next = findNext(b)
	splay(prev, NULL)
	splay(next, prev)
	next.left = NULL

小Hi：沒錯，那麼下一個問題！如果a,b不在樹中呢？

小Ho：這還不簡單，把a,b插入樹中，做完之後再删除不就好了！

小Hi：想不到小Ho你還蠻機智的嘛。

小Ho：那是，畢竟是我小Ho。(哼哼)

小Hi：Splay樹由于splay操作的使得其相較于Treap具有更大的靈活性，并且不再有随機性。其插入、查找和删除操作的均攤時間複雜度也都是O(logn)的，具體的複雜度分析可以參考這裡。那麼最後小Ho你能夠把Splay的實作出來麼？

小Ho：沒問題，看我的吧！

AC:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int inf = 0x3f3f3f3f;
struct Node {
	int val;
	struct Node *father;
	struct Node *left,*right;

	Node(){}
	Node(int key) {
		this->val = key;
		this->father = this->left = this->right = NULL;
	}
};
Node *root;

void left_rotate(Node *x) {
	Node *p = x->father;
	x->father = p->father;
	if(p->father != NULL) { //左旋
		if(p->father->left == p) {
			p->father->left = x;
		} else if(p->father->right == p) {
			p->father->right = x;
		}
	} else {  //說明此時的p是根節點
		root = x;
	}
	p->right = x->left;
	if(x->left != NULL)
		x->left->father = p;
	x->left = p;
	p->father = x;
}

void right_rotate(Node *x) {
	Node *p = x->father;
	x->father = p->father;
	if(p->father != NULL) { //右旋
		if(p->father->left == p) {
			p->father->left = x;
		} else if(p->father->right == p) {
			p->father->right = x;
		}
	} else {  //說明此時的p是根節點
		root = x;
	}
	p->left = x->right;
	if(x->right != NULL)
		x->right->father = p;
	x->right = p;
	p->father = x;
}

void Splay(Node *x,Node *y) { //表示對x節點進行調整，使得x是y的兒子節點
	while(x->father != y) {
		Node *p = x->father;
		if(p->father == y) {
			// 因為p的父親是y，是以隻需要将x進行Zig操作
			// 就可以使得x的父親變為y
			if(p->left == x) {
				right_rotate(x);
			} else {
				left_rotate(x);
			}
		} else {
			Node *g = p->father;
			if(p == g->left) {
				if(x == p->left) {  
					// x,p同為左兒子，Zig-Zig操作
					//當x,p同為左兒子時，依次将p和x右旋
					//當x,p同為右兒子時，依次将p和x左旋
					right_rotate(p);
					right_rotate(x);
				} else { 
					// p為左，x為右，Zig-Zag操作
					//當p為左兒子，x為右兒子時，将x節點先左旋再右旋
					//當p為右兒子，x為左兒子時，将x節點先右旋再左旋
					left_rotate(x);
					right_rotate(x);
				}
			} else {
				if(x == p->right) {
					// x,p同為右兒子，Zig-Zig操作
					left_rotate(p);
					left_rotate(x);
				} else {
					// p為右，x為左，Zig-Zag操作
					right_rotate(x);
					left_rotate(x);
				}
			}
		}
	}
}

Node *bst_insert(int key) { //類似平衡二叉樹先插入節點
	Node *p = new Node(key);
	if(root == NULL) {
		root = p;
		return root;
	}
	Node *t = root;
	while(true) {
		if(key > t->val) { //右枝走
			if(t->right == NULL) {
				t->right = p;
				p->father = t;
				break;
			}
			t = t->right;
		} else if(key < t->val) {  //左枝走
			if(t->left == NULL) {
				t->left = p;
				p->father = t;
				break;
			}
			t = t->left;
		} else return t; //說明有重複元素
	}
	return p;
}

Node *bst_find(int key) {  //普通的平衡二叉樹的查找
	Node *t = root;
	while(t->val != key) {
		if(key > t->val) {
			if(t->right != NULL) { 
				t = t->right;
			} else return NULL; 
		} else {
			if(t->left != NULL) {
				t = t->left;
			} else return NULL;
		}
	}
	return t;
}

void insert(int key) {
	Node *p = bst_insert(key);
	Splay(p,NULL);
}

Node *find(int key) {
	Node *p = bst_find(key);
	if(p != NULL) {
		Splay(p,NULL);
	}
	return p;
}

Node *findPre(int key) {  //查找指定數key的前一個數
	Node *p = find(key);
	if(p == NULL) return NULL;
	Splay(p,NULL);
	Node *t = root->left;
	if(t == NULL) return root;
	while(t->right) {
		t = t->right;
	}
	return t;
}

Node *findNext(int key) {
	Node *p = find(key);
	if(p == NULL) return NULL;
	Splay(p,NULL);
	Node *t = root->right;
	if(t == NULL) return root;
	while(t->left) {
		t = t->left;
	}
	return t;
}

void Delete(int key) {
	Node *pre = findPre(key);
	Node *next = findNext(key);
	if(pre != NULL && next != NULL) {
		Splay(pre,NULL);
		Splay(next,pre);
		next->left = NULL;
	}
}

void deleteInterval(int a,int b) {
	insert(a);
	insert(b);
	Node *pre = findPre(a);
	Node *next = findNext(b);
	Splay(pre,NULL);
	Splay(next,pre);
	next->left = NULL;
	Delete(a);
	Delete(b);
}

int main()
{
	int n,k,a,b;
	char op[2];
	while(scanf("%d",&n)!=EOF) {
		root = NULL;
		insert(-1);
		insert(inf);
		while(n--) {
			scanf("%s",op);
			if(op[0] == 'I') {
				scanf("%d",&k);
				insert(k);
			} else if(op[0] == 'Q') {
				scanf("%d",&k);
				Node *p = find(k);
				if(p != NULL) {
					printf("%d\n",k);
				} else {
					insert(k);
					p = findPre(k);
					Delete(k);
					printf("%d\n",p->val);
				}
			} else {
				scanf("%d %d",&a,&b);
				deleteInterval(a,b);
			}
		}
	}
	return 0;
}