Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

InuyamaAoi's blog

By InuyamaAoi, history, 4 years ago, In English,

I chose Splay tree as my Balanced Binary Search Tree if I have to implement it.

There are few reasons.

  1. It always give amortized O(lg n) time complexity. This is reason why I'm not using treap or skip list. But I think skip list is meaningful than only usage for BBST.

  2. It is easy to remember. Unlike other balanced binary tree, such as Red-black tree or AVL tree or 2-3 tree, it has same logic for searching, finding and deleting. Also, Making node as root is straight-forward.

I have implemented Red-black tree once with guidebook in IOI training camp. It took long. (maybe 2h?) But I implemented Splay tree with only 1h in my first implementation. I only saw wikipedia once to implement it just before I started to code.

My code is following.

Its major part is Splay and It is very simple! Anything other is same with just BST.

Maybe implementation of Erase is easier than other BST.

#include<cstdio>
#include<cstdlib>
struct Node{
	Node *l;
	Node *r;
	Node *p;
	int v;
};
Node *root;
void rightRotate(Node *P)
{
	Node *T=P->l;
	Node *B=T->r;
	Node *D=P->p;
	if(D)
	{
		if(D->r==P) D->r=T;
		else D->l=T;
	}
	if(B)
		B->p=P;
	T->p=D;
	T->r=P;
	
	P->p=T;
	P->l=B;
}
void leftRotate(Node *P)
{
	Node *T=P->r;
	Node *B=T->l;
	Node *D=P->p;
	if(D)
	{
		if(D->r==P) D->r=T;
		else D->l=T;
	}
	if(B)
		B->p=P;
	T->p=D;
	T->l=P;
	
	P->p=T;
	P->r=B;
}

void Splay(Node *T)
{
	while(true)
	{
		Node *p=T->p;
		if(!p) break;
		Node *pp=p->p;
		if(!pp)//Zig
		{
			if(p->l==T)
				rightRotate(p);
			else
				leftRotate(p);
			break;
		}
		if(pp->l==p)
		{
			if(p->l==T)
			{//ZigZig
				rightRotate(pp);
				rightRotate(p);
			}
			else
			{//ZigZag
				leftRotate(p);
				rightRotate(pp);
			}
		}
		else
		{
			if(p->l==T)
			{//ZigZag
				rightRotate(p);
				leftRotate(pp);
			}
			else
			{//ZigZig
				leftRotate(pp);
				leftRotate(p);
			}
		}
	}
	root=T;
}
void Insert(int v)
{
	if(!root)
	{
		root=(Node *)malloc(sizeof(Node));
		root->l=NULL;
		root->r=NULL;
		root->p=NULL;
		root->v=v;
		return;
	}
	Node *P=root;
	while(true)
	{
		if(P->v==v) break; // not multiset
		if(v < (P->v) )
		{
			if(P->l) P=P->l;
			else
			{
				P->l=(Node *)malloc(sizeof(Node));
				P->l->p=P;
				P->l->r=NULL;
				P->l->l=NULL;
				P->l->v=v;
				P=P->l;
				break;
			}
		}
		else
		{
			if(P->r) P=P->r;
			else
			{
				P->r=(Node *)malloc(sizeof(Node));
				P->r->p=P;
				P->r->r=NULL;
				P->r->l=NULL;
				P->r->v=v;
				P=P->r;
				break;
			}
		}
	}
	Splay(P);
}
void Inorder(Node *R)
{
	if(!R) return;
	Inorder(R->l);
	printf("v: %d ",R->v);
	if(R->l) printf("l: %d ",R->l->v);
	if(R->r) printf("r: %d ",R->r->v);
	puts("");
	Inorder(R->r);
}
Node* Find(int v)
{
	if(!root) return NULL;
	Node *P=root;
	while(P)
	{
		if(P->v==v)
			break;
		if(v<(P->v))
		{
			if(P->l)
				P=P->l;
			else
				break;
		}
		else
		{
			if(P->r)
				P=P->r;
			else
				break;
		}
	}
	Splay(P);
	if(P->v==v) return P;
	else return NULL;
}
bool Erase(int v)
{
	Node *N=Find(v);
	if(!N) return false;
	Splay(N); //check once more;
	Node *P=N->l;
	if(!P)
	{
		root=N->r;
		root->p=NULL;
		free(N);
		return true;
	}
	while(P->r) P=P->r;
	if(N->r)
	{
		P->r=N->r;
		N->r->p=P;
	}
	root=N->l;
	root->p=NULL;
	free(N);
	return true;
}
int main()
{
	while(true)
	{
		int t;
		scanf("%d",&t);
		if(t!=0 && t!=-1) Insert(t);
		else if(t==0)
		{
			scanf("%d",&t);
			if(!Find(t))
				printf("Couldn't Find %d!\n",t);
			else
				printf("Found %d!\n",t);
		}
		else
		{
			scanf("%d",&t);
			if(Erase(t))
				printf("Deleted %d!\n",t);
			else
				printf("Couldn't Find %d!\n",t);
		}
		if(root) printf("root: %d\n",root->v);
		Inorder(root);
	}
}
 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by HYEA (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you add tags?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It's too long. My friend codes function splay it in only 10 lines:


void splay(Node * x) { while(x->parent != nil) { Node * y = x->parent, * z = y->parent; int dy = getDir(y, x), dz = getDir(z, y); if(z == nil) rotate(y, dy); else if(dy == dz) rotate(z, dz), rotate(y, dy); else rotate(y, dy), rotate(z, dz); } }

This is his full code: https://sites.google.com/site/kc97ble/container/splay-tree/splaytree-cpp-3

Although it supports lazy update, it is shorter much than your code.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I agree that whole code provided by HYEA is very long, but I can improve your code to one line in exactly the same way as you improved HYEA's code:

    void splay(Node * x) { while(x->parent != nil) { Node * y = x->parent, * z = y->parent; int dy = getDir(y, x), dz = getDir(z, y); if(z == nil) rotate(y, dy); else if(dy == dz) rotate(z, dz), rotate(y, dy); else rotate(y, dy), rotate(z, dz); } }
    
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I wanted intuitionistic code which made code longer.

    I can shrink my code using l, r as array. It will make code more shorter, but more difficult to understand. l, r, p is straight-forward. Isn't it?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In this case it's not just the number of lines of code, using child[0] and child[1] instead of left and right has an advantage:

    Most of the operations are symmetric between left and right, so you don't have to duplicate the code, and don't cause hard-to-debug bugs when you forget to change a left to a right.

    In particular, the code using left and right pointer must implement leftRotate and rightRotate separately, and have to handle 2 cases of "Zig", "ZigZig" and "ZigZag" each.

    Even for seemingly-asymmetric operations such as if (value > mid) goto right; else goto left; can be replaced with goto child[value > mid]; (if you find that too hard to understand, you don't have to use it)

»
4 years ago, # |
Rev. 3   Vote: I like it +23 Vote: I do not like it

You might want to consider "top-down" splay tree implementation, it's described in the original paper on page 667+.

The same amount of code is needed for it, but it's faster: you don't have to walk down the tree to find an element and then splay it, you simply splay at once and return the root.

Also, you don't have to store a pointer to parent: more memory efficiency and less code.

My set container implementation using "top-down" splay tree.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A small Bug in your code. In Erase: It should be :: if(root) if(!P) { root=N->r; if(root) root->p=NULL; free(N); return true; }

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Node *N=Find(v);
    if(!N) return false;
    

    Find returns false if !root

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this post! Can you also provide some questions where one has to code BST himself ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    With some modification, you can code OSRank, with one more function getRank(v) which returns number of elements that is less or equal than v(rank when sorted, if set has 1, 2, 5 and 7 as elements; rank of 5 is 3) I solved IOI12 Jousting Tournament with this data structure. I will reply source code as soon as I turn my PC on

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is source code. If you have question, do not hesitate to ask.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For an application of Splay Trees, you can try attempting this problem: https://www.hackerearth.com/july-clash-15/algorithm/upgrade/description/ — though, in my opinion, the level of the problem is hard, so it might be difficult to be solved, but an amazing problem nonetheless.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about such essential operations like merge and split?

All operations you implemented can be also implemented in easier way on segment tree.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't implemented both function but it can be done just splaying and (un)linking nodes.

    Segment tree can be used as replacement of BBST but it is only when elements are atomic.

»
3 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

I guess there is a minor problem in your code. When there is only one element in the entire tree, erasing that element occurs Segmentation Fault.

In order to solve it, I added the following block of code to the beginning of your Erase function.

Node *N=Find(v);
if(!N) return;
if(!(N->r) and !(N->l)){
        N->v = -1;
        Splay(N);
        return;
}
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should rather do this:

      if(!P && !(N->r))
      {
        root=NULL;
        free(N);
        return true;
      }
      if(!P)...
    
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if in tree there are only one node and when we delete that node then it is giving run time exception.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the erase() operation the same as split and merge?