### conflict's blog

By conflict, history, 6 years ago,

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


• +35

 » 6 years ago, # |   0 Auto comment: topic has been updated by conflict (previous revision, new revision, compare).
 » 6 years ago, # |   +3 Can you add tags?
•  » » 6 years ago, # ^ |   +22 added
 » 6 years ago, # |   +3 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-3Although it supports lazy update, it is shorter much than your code.
•  » » 6 years ago, # ^ |   +14 I agree that whole code provided by conflict is very long, but I can improve your code to one line in exactly the same way as you improved conflict'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); } } 
•  » » 6 years ago, # ^ |   +6 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?
•  » » 23 months ago, # ^ |   0 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)
 » 6 years ago, # | ← Rev. 3 →   +23 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.
 » 5 years ago, # |   0 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; }
•  » » 5 years ago, # ^ |   0 Node *N=Find(v); if(!N) return false; Find returns false if !root
 » 5 years ago, # |   0 Thanks for this post! Can you also provide some questions where one has to code BST himself ?
•  » » 5 years ago, # ^ |   +3 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
•  » » 5 years ago, # ^ |   0 Here is source code. If you have question, do not hesitate to ask.
 » 5 years ago, # |   0 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.
 » 5 years ago, # |   0 What about such essential operations like merge and split? All operations you implemented can be also implemented in easier way on segment tree.
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # | ← Rev. 3 →   +5 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; }
•  » » 4 years ago, # ^ |   0 You should rather do this:  if(!P && !(N->r)) { root=NULL; free(N); return true; } if(!P)... 
 » 5 years ago, # |   0 if in tree there are only one node and when we delete that node then it is giving run time exception.
 » 22 months ago, # |   0 Is the erase() operation the same as split and merge?