Konijntje's blog

By Konijntje, history, 9 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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Can you add tags?

»
9 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.

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

    I agree that whole code provided by Konijntje is very long, but I can improve your code to one line in exactly the same way as you improved Konijntje'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); } }
    
  • »
    »
    9 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?

»
9 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.

»
8 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; }

  • »
    »
    8 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

»
8 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 ?

  • »
    »
    8 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

  • »
    »
    8 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.

»
8 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.

»
8 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.

  • »
    »
    8 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.

»
8 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;
}