Splay伸展树

Splay是二叉查找树，不是一颗平衡树，但可以通过自调整达到一种近似平衡的情况。Splay在连续M次操作中均摊时间复杂度是M*logn，其中n为节点的个数，M为操作的次数。Splay的操作与特点将在以下介绍。

• 当访问一个节点时，立即把当前访问的节点旋转到根节点，让访问（插入）的节点立马成为新的根节点。
• 旋转操作与AVL很像，有两种旋转，左旋、右旋。
• Splay操作有两种不同的实现方式。一种是自底向上的旋转，需要记录当前节点的父亲节点。另外一种是自顶向上的实现方式，不需要记录父亲节点。
• 由于Splay把当前访问的节点放在根节点，很容易求出当前节点的前驱与后继。
• Splay支持merge、split、findMin、findMax、predecessor、successor、insert、remove等操作。
• 在信息学竞赛中，Splay可以实现能实现线段树的所有的功能，即pushup、pushdown维护区间信息在Splay中用的很活，但Splay又支持快速的序列分离和合并，这是线段树做不到的。
• 验证自己手写的数据结构是否正确可以去OJ写一写用到该数据结构的题。

今天按照数据结构那本书上的代码实现了Splay，并过了【HNOI2002】营业额统计，代码比较冗长，很多地方可以简化。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;

typedef int Comparable;

struct Node
{
	Node *left, *right;
	int element;
	Node(int v=0, Node *lt=0, Node *rt=0):element(v),left(lt),right(rt) {}
};

Node *null = new Node();

void rotateWithLeftChild(Node *&t)
{
	Node *k = t->left;
	t->left = k->right;
	k->right = t;
	t = k;
}

void rotateWithRightChild(Node *&t)
{
	Node *k = t->right;
	t->right = k->left;
	k->left = t;
	t = k;
}

void splay(Node *&t, const Comparable &x)
{
	Node *leftTreeMax, *rightTreeMin;
	
	static Node head;
	
	head.left = head.right = null;
	
	leftTreeMax = rightTreeMin = &head;
	null->element = x;
	
	for(;;)
	{
		if(x < t->element)
		{
			if(x < t->left->element)
				rotateWithLeftChild(t);
			if(t->left == null) break;
			
			//Link Right
			rightTreeMin->left = t;
			rightTreeMin = t;
			t = t->left;
		}
		else if(x > t->element)
		{
			if(x > t->right->element)
				rotateWithRightChild(t);
			if(t->right == null) break;
			
			//Link left
			leftTreeMax->right = t;
			leftTreeMax = t;
			t = t->right;
		}
		else break;
	}
	
	leftTreeMax->right = t->left;
	rightTreeMin->left = t->right;
	
	t->left = head.right;
	t->right = head.left;
}

int insert(Node *&root, const Comparable &x)
{
	Node* newNode = new Node(x);
	
	if(root == null)
	{
		newNode->left = newNode->right = null;
		root = newNode;
		return 0;
	}
	
	splay(root, x);
	if(x < root->element)
	{
		newNode->left = root->left;
		newNode->right = root;
		root->left = null;
		root = newNode;
	}
	else if(x > root->element)
	{
		newNode->right = root->right;
		newNode->left = root;
		root->right = null;
		root = newNode;
	}
	else return -1;
	
	newNode = NULL;
	
	return 1;
}

Node *findMin(Node *o)
{
	if(o == null) return null;
	while(o->left != null)
		o = o->left;
	return o;
}

Node *findMax(Node *o)
{
	if(o == null) return null;
	while(o->right != null)
		o = o->right;
	return o;
}

Node *predecessor(Node *o, int x)
{
	splay(o, x);
	return findMax(o->left);
}

Node *successor(Node *o, int x)
{
	splay(o, x);
	
	return findMin(o->right);
}

void printTree(Node *o)
{
	if(o != null)
	{	
		printf("%d ", o->element);
		printTree(o->left);
		printTree(o->right);
	}
}

///////////////////////
int n;

int abs2(int x) { return x >= 0? x : -x; }

int main()
{
	while(~scanf("%d", &n))
	{
		int x; 
		Node* root = null; root->left = null; root->right = null;
		
		int ans = 0;
		for(int i = 1; i <= n; i++)
		{
			if(scanf("%d", &x) == EOF) x = 0;
			
			if(i == 1)
			{
				ans = x; insert(root, x);
				continue ;
			}
			int p = insert(root, x);
			if(p == -1) continue ;
			
			Node *pre = predecessor(root, x);
			Node *next = successor(root, x);
			int t = 1000000000;
			if(pre != null) t = min(t, abs2(x-pre->element));
			if(next != null) t = min(t, abs2(x-next->element));
			//printTree(root), puts("");
			ans += t;
		}
		printf("%d\n", ans);
	}
	return 0;
}