Splay tree and its implementation.

Revision en2, by conflict, 2015-06-10 18:46:42

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);
}
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en2 conflict 2015-06-10 18:46:42 65
en1 conflict 2015-06-10 18:36:46 3999 Initial revision (published)