I chose Splay tree as my Balanced Binary Search Tree if I have to implement it.
There are few reasons.
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.
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);
}
}
Auto comment: topic has been updated by Konijntje (previous revision, new revision, compare).
Can you add tags?
added
It's too long. My friend codes function splay it in only 10 lines:
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.
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:
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?
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.
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; }
Find returns false if !root
Thanks for this post! Can you also provide some questions where one has to code BST himself ?
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
Here is source code. If you have question, do not hesitate to ask.
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.
What about such essential operations like merge and split?
All operations you implemented can be also implemented in easier way on segment tree.
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.
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.