#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
struct node *left;
struct node *right;
struct node *p;
char color;
int key;
}node;
node *root = NULL;
struct node *new_node(int key)
{
struct node
*node1
= (struct node
*)malloc(sizeof(struct node
)); node1->key = key;
node1->left = node1->right = NULL;
node1->color='R';
return node1;
}
void insert_tree (int key) {
node *z=new_node(key);
struct node *x = root;
struct node *temp;
if ( x == NULL ){
root = z;
root->color = 'B';
return;
}
while ( x != NULL){
temp = x;
if ( z->key < x->key){
x = x->left;
}
else x = x->right;
}
z->p = temp;
if ( temp == NULL){
root = z;
}
else if( z->key < temp->key ){
temp->left = z;
}
else temp->right = z;
z->left = NULL;
z->right = NULL;
z->color = 'R';
fix_tree(z) ;
return;
} // traverse through the tree inserting element at right spot
void fix_tree(node *z)
{
struct node *y;
while ((z->p!=NULL)&&(z->p->color == 'R')){
if (z->p == z->p->p->left){
y = z->p->p->right;
if ((y!= NULL)&&(y->color == 'R')){
z->p->color = 'B';
y->color = 'B';
z->p->p->color = 'R';
z = z->p->p;
}
else {if (z == z->p->right){
z = z->p;
left_rotate(z);
}
z->p->color = 'B';
z->p->p->color = 'R';
right_rotate(z->p->p);
}
}
else {
y = z->p->p->left;
if ((y!= NULL)&&(y->color == 'R')){
z->p->color = 'B';
y->color = 'B';
z->p->p->color = 'R';
z = z->p->p;
}
else {
if (z == z->p->left){
z = z->p;
right_rotate(z);
}
z->p->color = 'B';
z->p->p->color = 'R';
left_rotate(z->p->p);
}
}
}
root->color = 'B';
}
void left_rotate( node *x ) {
node *y;
y = x->right;
x->right = y->left;
if ( y->left != NULL )
y->left->p = x;
y->p = x->p;
if ( x->p == NULL ) root = y;
else
if ( x == (x->p)->left )
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
return;
}
void right_rotate( node *x ) {
node *y;
y = x->left;
x->left = y->right;
if ( y->right != NULL )
y->right->p = x;
y->p = x->p;
if ( x->p == NULL ) root = y;
else
if ( x == (x->p)->right )
x->p->right = y;
else
x->p->left = y;
y->right = x;
x->p = y;
return;
}
void visit( node *x)
{
if(x!=NULL)
{
visit(x->left);
if(x->p==NULL)
printf( "%d %c NIL\n",x
->key
,x
->color
); else
printf( "%d %c %d\n",x
->key
,x
->color
,x
->p
->key
); visit(x->right);
}
return;
}
void prefixtour(node *p)
{
if (p==NULL)
{
return ;
}
else
visit(p);
return ;
}
int main()
{
int n;
int i,key;
for(i=0;i<n;i++)
{
insert_tree(key);
}
prefixtour(root);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IG5vZGUKewogICAgc3RydWN0IG5vZGUgKmxlZnQ7CiAgICBzdHJ1Y3Qgbm9kZSAqcmlnaHQ7CiAgICBzdHJ1Y3Qgbm9kZSAqcDsKICAgIGNoYXIgY29sb3I7CiAgICBpbnQga2V5Owp9bm9kZTsKbm9kZSAqcm9vdCA9IE5VTEw7CgpzdHJ1Y3Qgbm9kZSAqbmV3X25vZGUoaW50IGtleSkKewogICAgc3RydWN0IG5vZGUgKm5vZGUxID0gIChzdHJ1Y3Qgbm9kZSAqKW1hbGxvYyhzaXplb2Yoc3RydWN0IG5vZGUpKTsKICAgIG5vZGUxLT5rZXkgPSBrZXk7CiAgICBub2RlMS0+bGVmdCA9IG5vZGUxLT5yaWdodCA9IE5VTEw7CiAgICBub2RlMS0+Y29sb3I9J1InOwogICAgcmV0dXJuIG5vZGUxOwp9Cgp2b2lkIGluc2VydF90cmVlIChpbnQga2V5KSB7CiAgICBub2RlICp6PW5ld19ub2RlKGtleSk7CiAgICBzdHJ1Y3Qgbm9kZSAqeCA9IHJvb3Q7CiAgICBzdHJ1Y3Qgbm9kZSAqdGVtcDsKICAgIGlmICggeCA9PSBOVUxMICl7CiAgICByb290ID0gejsKICAgIHJvb3QtPmNvbG9yID0gJ0InOwogICAgcmV0dXJuOwogICAgfQogICAgd2hpbGUgKCB4ICE9IE5VTEwpewogICAgdGVtcCA9IHg7CiAgICBpZiAoIHotPmtleSA8IHgtPmtleSl7CiAgICAgICAgeCA9IHgtPmxlZnQ7CiAgICB9CiAgICBlbHNlIHggPSB4LT5yaWdodDsKICAgIH0KICAgIHotPnAgPSB0ZW1wOwogICAgaWYgKCB0ZW1wID09IE5VTEwpewogICAgcm9vdCA9IHo7CiAgICB9CiAgICBlbHNlIGlmKCB6LT5rZXkgPCB0ZW1wLT5rZXkgKXsKICAgICAgICB0ZW1wLT5sZWZ0ID0gejsKICAgIH0KICAgIGVsc2UgdGVtcC0+cmlnaHQgPSB6OwogICAgei0+bGVmdCA9IE5VTEw7CiAgICB6LT5yaWdodCA9IE5VTEw7CiAgICB6LT5jb2xvciA9ICdSJzsKIGZpeF90cmVlKHopIDsKIHJldHVybjsKfSAvLyB0cmF2ZXJzZSB0aHJvdWdoIHRoZSB0cmVlIGluc2VydGluZyBlbGVtZW50IGF0IHJpZ2h0IHNwb3QKCnZvaWQgZml4X3RyZWUobm9kZSAqeikKIHsKIHN0cnVjdCBub2RlICp5Owp3aGlsZSAoKHotPnAhPU5VTEwpJiYoei0+cC0+Y29sb3IgPT0gJ1InKSl7CiAgICBpZiAoei0+cCA9PSB6LT5wLT5wLT5sZWZ0KXsKICAgICAgICB5ID0gei0+cC0+cC0+cmlnaHQ7CiAgICAgICAgaWYgKCh5IT0gTlVMTCkmJih5LT5jb2xvciA9PSAnUicpKXsKICAgICAgICAgICAgei0+cC0+Y29sb3IgPSAnQic7CiAgICAgICAgICAgIHktPmNvbG9yID0gJ0InOwogICAgICAgICAgICB6LT5wLT5wLT5jb2xvciA9ICdSJzsKICAgICAgICAgICAgeiA9IHotPnAtPnA7CiAgICAgICAgfQogICAgICAgIGVsc2Uge2lmICh6ID09IHotPnAtPnJpZ2h0KXsKICAgICAgICAgICAgeiA9IHotPnA7CiAgICAgICAgICAgIGxlZnRfcm90YXRlKHopOwogICAgICAgIH0KICAgICAgICB6LT5wLT5jb2xvciA9ICdCJzsKICAgICAgICB6LT5wLT5wLT5jb2xvciA9ICdSJzsKICAgICAgICByaWdodF9yb3RhdGUoei0+cC0+cCk7CiAgICAgICAgfQogICAgfQogICAgZWxzZSB7CiAgICAgICAgeSA9IHotPnAtPnAtPmxlZnQ7CiAgICAgICAgaWYgKCh5IT0gTlVMTCkmJih5LT5jb2xvciA9PSAnUicpKXsKICAgICAgICAgICAgei0+cC0+Y29sb3IgPSAnQic7CiAgICAgICAgICAgIHktPmNvbG9yID0gJ0InOwogICAgICAgICAgICB6LT5wLT5wLT5jb2xvciA9ICdSJzsKICAgICAgICAgICAgeiA9IHotPnAtPnA7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBpZiAoeiA9PSB6LT5wLT5sZWZ0KXsKICAgICAgICAgICAgeiA9IHotPnA7CiAgICAgICAgICAgIHJpZ2h0X3JvdGF0ZSh6KTsKICAgICAgICB9CiAgICAgICAgei0+cC0+Y29sb3IgPSAnQic7CiAgICAgICAgei0+cC0+cC0+Y29sb3IgPSAnUic7CiAgICAgICAgbGVmdF9yb3RhdGUoei0+cC0+cCk7CiAgICB9Cn0KfQpyb290LT5jb2xvciA9ICdCJzsKfQogCiB2b2lkIGxlZnRfcm90YXRlKCBub2RlICp4ICkgewogICAgbm9kZSAqeTsKICAgIHkgPSB4LT5yaWdodDsKICAgIHgtPnJpZ2h0ID0geS0+bGVmdDsKICAgIGlmICggeS0+bGVmdCAhPSBOVUxMICkKICAgICAgICB5LT5sZWZ0LT5wID0geDsKICAgIHktPnAgPSB4LT5wOwoKICAgIGlmICggeC0+cCA9PSBOVUxMICkgcm9vdCA9IHk7CiAgICBlbHNlCiAgICAgICAgaWYgKCB4ID09ICh4LT5wKS0+bGVmdCApCiAgICAgICAgICAgICB4LT5wLT5sZWZ0ID0geTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIAogICAgICAgICAgICB4LT5wLT5yaWdodCA9IHk7CiAgICB5LT5sZWZ0ID0geDsKICAgIHgtPnAgPSB5OwogICAgcmV0dXJuOwogICAgfQoKdm9pZCByaWdodF9yb3RhdGUoIG5vZGUgKnggKSB7CiAgICBub2RlICp5OwogICAgeSA9IHgtPmxlZnQ7CiAgICB4LT5sZWZ0ID0geS0+cmlnaHQ7CiAgICBpZiAoIHktPnJpZ2h0ICE9IE5VTEwgKQogICAgICAgIHktPnJpZ2h0LT5wID0geDsKICAgICAgICB5LT5wID0geC0+cDsKICAgIGlmICggeC0+cCA9PSBOVUxMICkgcm9vdCA9IHk7CiAgICBlbHNlCiAgICAgICAgaWYgKCB4ID09ICh4LT5wKS0+cmlnaHQgKQogICAgICAgICAgICB4LT5wLT5yaWdodCA9IHk7CiAgICAgICAgZWxzZQogICAgICAgICAgICAgIHgtPnAtPmxlZnQgPSB5OwogICAgICAgICAgICAgeS0+cmlnaHQgPSB4OwogICAgICAgICAgICB4LT5wID0geTsKICAgICAgICAgICAgcmV0dXJuOwogICAgfQoKIAoKdm9pZCB2aXNpdCggbm9kZSAqeCkKewogICAgaWYoeCE9TlVMTCkKICAgIHsKCiAgICAgICAgdmlzaXQoeC0+bGVmdCk7CiAgICAgICAgaWYoeC0+cD09TlVMTCkKICAgICAgICBwcmludGYoICIlZCAlYyBOSUxcbiIseC0+a2V5LHgtPmNvbG9yKTsKICAgICAgICBlbHNlCiAgICAgICAgcHJpbnRmKCAiJWQgJWMgJWRcbiIseC0+a2V5LHgtPmNvbG9yLHgtPnAtPmtleSk7CiAgICAgICAgdmlzaXQoeC0+cmlnaHQpOwogICAgfQogICAgcmV0dXJuOwp9CnZvaWQgcHJlZml4dG91cihub2RlICpwKQp7CiAgICBpZiAocD09TlVMTCkKICAgICAgICB7CiAgICAgICAgcHJpbnRmKCJlbXB0eSB0cmVlIik7CiAgICAgICAgcmV0dXJuIDsKICAgIH0KICAgIGVsc2UKICAgICAgICB2aXNpdChwKTsKICAgIHJldHVybiA7Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgbjsKICAgIHNjYW5mKCIlZCIsJm4pOwogICAgaW50IGksa2V5OwogICAgZm9yKGk9MDtpPG47aSsrKQogICAgewogICAgICAgIHNjYW5mKCIlZCIsJmtleSk7CiAgICAgICAgaW5zZXJ0X3RyZWUoa2V5KTsKICAgIH0KICAgIHByZWZpeHRvdXIocm9vdCk7CnJldHVybiAwOwoKfQoK