#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
char colour;
struct node* parent;
struct node* leftChild;
struct node* rightChild;
} ;
void leftRotate( struct node* root, struct node* l) //left rotate
{
struct node * y;
y = l-> rightChild;
l-> rightChild = y-> leftChild;
if ( y-> leftChild != NULL)
{
y-> leftChild-> parent = l;
}
y-> parent = l-> parent;
if ( l-> parent == NULL)
{
root = y;
}
else if ( l-> data == l-> parent-> leftChild-> data)
{
l-> parent-> leftChild = y;
}
else
l-> parent-> rightChild = y;
y-> leftChild = l;
l-> parent = y;
return ;
}
void rightRotate( struct node* root, struct node* r) //right rotate
{
struct node * x;
x = r-> leftChild;
r-> leftChild = x-> rightChild;
if ( x-> rightChild != NULL)
{
x-> rightChild-> parent = r;
}
x-> parent = r-> parent;
if ( r-> parent == NULL)
{
root = x;
}
else if ( r-> data == r-> parent-> leftChild-> data)
{
r-> parent-> leftChild = x;
}
else
r-> parent-> rightChild = x;
x-> rightChild = r;
r-> parent = x;
return ;
}
struct node* fix( struct node * root, struct node * f) //fixing new node inserted
{
struct node * y;
if ( ( f-> parent) && ( f-> parent-> color== 'B' ) ) return ;
while ( f-> parent && ( f-> parent-> colour == 'R' ) )
{
if ( f-> parent-> data == f-> parent-> parent-> leftChild-> data)
{
y = f-> parent-> parent-> rightChild;
if ( y && ( y-> colour == 'R' ) )
{
f-> parent-> colour = 'B' ;
y-> colour = 'B' ;
f-> parent-> parent-> colour = 'R' ;
f = f-> parent-> parent;
}
else {
if ( f-> data == f-> parent-> rightChild-> data)
{
f = f-> parent;
leftRotate( root, f) ;
}
f-> parent-> colour = 'B' ;
f-> parent-> parent-> colour = 'R' ;
rightRotate( root, f-> parent-> parent) ;
}
}
else
{
y = f-> parent-> parent-> leftChild;
if ( ( y!= NULL) && ( y-> colour == 'R' ) ) {
f-> parent-> colour = 'B' ;
y-> colour = 'B' ;
f-> parent-> parent-> colour = 'R' ;
f = f-> parent-> parent;
}
else {
if ( f-> data == f-> parent-> leftChild-> data) {
f = f-> parent;
rightRotate( root, f) ;
}
f-> parent-> colour = 'B' ;
f-> parent-> parent-> colour = 'R' ;
leftRotate( root, f-> parent-> parent) ;
}
}
}
root-> colour = 'B' ;
return root;
}
struct node * newnode( struct node * root, int val) //inserting new node
{
struct node* p;
p
= ( struct node
* ) calloc ( 1 , sizeof ( struct node
) ) ; p-> data= val;
p-> colour= 'R' ;
if ( root== NULL)
{
root= p;
root-> colour= 'B' ;
return root;
}
struct node* x= root;
struct node* y;
while ( x!= NULL)
{
y= x;
if ( p-> data < x-> data)
{
x= x-> leftChild;
}
else
x= x-> rightChild;
}
p-> parent= y;
if ( y== NULL)
{
root= p;
}
else if ( p-> data < y-> data)
{
y-> leftChild= p;
}
else
{
y-> rightChild= p;
}
fix ( root, p) ;
return root;
}
void visit( struct node* x)
{
if ( x != NULL)
{
visit( x-> leftChild) ;
if ( x-> parent) {
printf ( "%d\n " , x
-> parent
-> data
) ; }
visit( x-> rightChild) ;
}
}
void pre_fix_tour( struct node* root) {
if ( root == NULL)
else
visit( root) ;
}
int main( )
{
int n;
int a[ n] , i;
struct node* root= NULL ;
for ( i= 0 ; i<= n- 1 ; i++ ) {
root = newnode( root, a[ i] ) ;
}
pre_fix_tour( root) ;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KIApzdHJ1Y3Qgbm9kZQp7CglpbnQgZGF0YTsKICAgIGNoYXIgY29sb3VyOwoJc3RydWN0IG5vZGUqIHBhcmVudDsKCXN0cnVjdCBub2RlKiBsZWZ0Q2hpbGQ7CglzdHJ1Y3Qgbm9kZSogcmlnaHRDaGlsZDsKIAp9OwoKIAp2b2lkIGxlZnRSb3RhdGUoc3RydWN0IG5vZGUqIHJvb3QsIHN0cnVjdCBub2RlKiBsKSAgLy9sZWZ0IHJvdGF0ZQp7CiAgICAgc3RydWN0IG5vZGUgKnk7CiAgICAgeSA9IGwtPnJpZ2h0Q2hpbGQ7ICAKICAgICBsLT5yaWdodENoaWxkID0geS0+bGVmdENoaWxkOyAKICAgICBpZiggeS0+bGVmdENoaWxkICE9IE5VTEwpCiAgICAgewogICAgICAgICB5LT5sZWZ0Q2hpbGQtPnBhcmVudCA9IGw7IAogICAgICB9CiAgICAgeS0+cGFyZW50ID0gbC0+cGFyZW50OyAKICAgICBpZiggbC0+cGFyZW50ID09IE5VTEwpCiAgICAgewogICAgICAgICByb290ID0geTsKICAgICB9CiAgICAgZWxzZSBpZiggbC0+ZGF0YSA9PSBsLT5wYXJlbnQtPmxlZnRDaGlsZC0+ZGF0YSkKICAgICB7CiAgICAgICAgIGwtPnBhcmVudC0+bGVmdENoaWxkID0geTsgCiAgICAgfQogICAgIGVsc2UKICAgICAgICAgbC0+cGFyZW50LT5yaWdodENoaWxkID0geTsKIAogICAgIHktPmxlZnRDaGlsZCA9IGw7IAogICAgIGwtPnBhcmVudCA9IHk7IAogCiAgICAgcmV0dXJuOwp9CiAKIAp2b2lkIHJpZ2h0Um90YXRlKHN0cnVjdCBub2RlKiByb290LCBzdHJ1Y3Qgbm9kZSogcikgIC8vcmlnaHQgcm90YXRlCnsKICAgIHN0cnVjdCBub2RlICp4OwogICAgeCA9IHItPmxlZnRDaGlsZDsgCiAgICByLT5sZWZ0Q2hpbGQgPSB4LT5yaWdodENoaWxkOyAKICAgIGlmICggeC0+cmlnaHRDaGlsZCAhPSBOVUxMKQogICAgewogICAgICAgIHgtPnJpZ2h0Q2hpbGQtPnBhcmVudCA9IHI7CiAgICB9CiAgICB4LT5wYXJlbnQgPSByLT5wYXJlbnQ7IAogICAgaWYoIHItPnBhcmVudCA9PSBOVUxMKQogICAgewogICAgICAgIHJvb3QgPSB4OwogICAgfSAKICAgIGVsc2UgaWYoIHItPmRhdGEgPT0gci0+cGFyZW50LT5sZWZ0Q2hpbGQtPmRhdGEpCiAgICB7CiAgICAgICAgci0+cGFyZW50LT5sZWZ0Q2hpbGQgPSB4OyAKICAgIH0KICAgIGVsc2UgCiAgICAJci0+cGFyZW50LT5yaWdodENoaWxkID0geDsKIAogICAgeC0+cmlnaHRDaGlsZCA9IHI7IAogICAgci0+cGFyZW50ID0geDsgCiAKICAgICByZXR1cm47Cn0KIApzdHJ1Y3Qgbm9kZSogZml4KHN0cnVjdCBub2RlICpyb290LHN0cnVjdCBub2RlICpmKSAvL2ZpeGluZyBuZXcgbm9kZSBpbnNlcnRlZAp7CnN0cnVjdCBub2RlICp5OwppZiAoKGYtPnBhcmVudCkmJihmLT5wYXJlbnQtPmNvbG9yPT0nQicpKSByZXR1cm47CndoaWxlIChmLT5wYXJlbnQgJiYgKGYtPnBhcmVudC0+Y29sb3VyID09ICdSJykpCnsKICAgIGlmIChmLT5wYXJlbnQtPmRhdGEgPT0gZi0+cGFyZW50LT5wYXJlbnQtPmxlZnRDaGlsZC0+ZGF0YSkKICAgIHsKICAgICAgICB5ID0gZi0+cGFyZW50LT5wYXJlbnQtPnJpZ2h0Q2hpbGQ7CiAgICAgICAgaWYgKHkgJiYgKHktPmNvbG91ciA9PSAnUicpKQogICAgICAgIHsKICAgICAgICAgICAgZi0+cGFyZW50LT5jb2xvdXIgPSAnQic7CiAgICAgICAgICAgIHktPmNvbG91ciA9ICdCJzsKICAgICAgICAgICAgZi0+cGFyZW50LT5wYXJlbnQtPmNvbG91ciA9ICdSJzsKICAgICAgICAgICAgZiA9IGYtPnBhcmVudC0+cGFyZW50OwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAJaWYgKGYtPmRhdGEgPT0gZi0+cGFyZW50LT5yaWdodENoaWxkLT5kYXRhKQogICAgICAgIAl7CiAgICAgICAgICAgCQlmID0gZi0+cGFyZW50OwogICAgICAgICAgICAJbGVmdFJvdGF0ZShyb290LGYpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGYtPnBhcmVudC0+Y29sb3VyID0gJ0InOwogICAgICAgIAkgIGYtPnBhcmVudC0+cGFyZW50LT5jb2xvdXIgPSAnUic7CiAgICAgICAgCXJpZ2h0Um90YXRlKHJvb3QsZi0+cGFyZW50LT5wYXJlbnQpOwogICAgICAgIH0KIAogICAgfQogICAgZWxzZQogICAgIHsKICAgICAgICB5ID0gZi0+cGFyZW50LT5wYXJlbnQtPmxlZnRDaGlsZDsKICAgICAgICBpZiAoKHkhPU5VTEwpICYmICh5LT5jb2xvdXIgPT0gJ1InKSl7CiAgICAgICAgICAgIGYtPnBhcmVudC0+Y29sb3VyID0gJ0InOwogICAgICAgICAgICB5LT5jb2xvdXIgPSAnQic7CiAgICAgICAgICAgIGYtPnBhcmVudC0+cGFyZW50LT5jb2xvdXIgPSAnUic7CiAgICAgICAgICAgIGYgPSBmLT5wYXJlbnQtPnBhcmVudDsKICAgICAgICB9CiAgICAgICAgZWxzZSB7CiAKICAgICAgICAJaWYgKGYtPmRhdGEgPT0gZi0+cGFyZW50LT5sZWZ0Q2hpbGQtPmRhdGEpewogICAgICAgICAgICAJZiA9IGYtPnBhcmVudDsKICAgICAgICAgICAgCXJpZ2h0Um90YXRlKHJvb3QsZik7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZi0+cGFyZW50LT5jb2xvdXIgPSAnQic7CiAgICAgICAgCSAgZi0+cGFyZW50LT5wYXJlbnQtPmNvbG91ciA9ICdSJzsKICAgICAgICAJICBsZWZ0Um90YXRlKHJvb3QsZi0+cGFyZW50LT5wYXJlbnQpOwogICAgICAgIH0KIAogICAgfQp9CnJvb3QtPmNvbG91ciA9ICdCJzsKcmV0dXJuIHJvb3Q7Cn0KIApzdHJ1Y3Qgbm9kZSAqbmV3bm9kZShzdHJ1Y3Qgbm9kZSAqcm9vdCwgaW50IHZhbCkgICAvL2luc2VydGluZyBuZXcgbm9kZQp7CiAgICBzdHJ1Y3Qgbm9kZSogcDsKICAgIHAgPSAoc3RydWN0IG5vZGUqKWNhbGxvYygxLHNpemVvZihzdHJ1Y3Qgbm9kZSkpOwogICAgcC0+ZGF0YT12YWw7CiAgICBwLT5jb2xvdXI9J1InOwogCiAgICBpZiAocm9vdD09TlVMTCkKICAgIHsKICAgIAlyb290PXA7CiAgICAJcm9vdC0+Y29sb3VyPSdCJzsKICAgICAgICByZXR1cm4gcm9vdDsKICAgIH0KICAgIHN0cnVjdCBub2RlKng9cm9vdDsKICAgIHN0cnVjdCBub2RlKnk7CiAgICB3aGlsZSAoeCE9TlVMTCkKICAgIHsKICAgIAl5PXg7CiAgICAJaWYocC0+ZGF0YSA8IHgtPmRhdGEpCiAgICAJewogICAgCQl4PXgtPmxlZnRDaGlsZDsKICAgIAl9CiAgICAgICAgZWxzZQogICAgICAgIAl4PXgtPnJpZ2h0Q2hpbGQ7CiAgICB9CiAgICBwLT5wYXJlbnQ9eTsKICAgIGlmKHk9PU5VTEwpCiAgICB7CiAgICAJcm9vdD1wOwogICAgfQogICAgZWxzZSBpZihwLT5kYXRhIDwgeS0+ZGF0YSkKICAgIHsKICAgIAl5LT5sZWZ0Q2hpbGQ9cDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgIAl5LT5yaWdodENoaWxkPXA7CiAgICB9CiAgICBmaXggKHJvb3QscCk7CiAgICByZXR1cm4gcm9vdDsKfQogCnZvaWQgdmlzaXQoc3RydWN0IG5vZGUqIHgpCnsKICAgIGlmICh4ICE9IE5VTEwpIAogICAgewogICAgICAgIHZpc2l0KHgtPmxlZnRDaGlsZCk7CiAgICAgICAgcHJpbnRmKCIlZCAiLHgtPmRhdGEpOwogICAgICAgIHByaW50ZigiJWMgIix4LT5jb2xvdXIpOwogICAgICAgIGlmKHgtPnBhcmVudCl7CiAgICAgICAJICAgIHByaW50ZigiJWRcbiIseC0+cGFyZW50LT5kYXRhKTsKICAgICAgIAl9CiAgICAgICAJZWxzZSBwcmludGYoIk5JTFxuIik7CiAgICAgICAgdmlzaXQoeC0+cmlnaHRDaGlsZCk7CiAgICB9Cn0gICAgCnZvaWQgcHJlX2ZpeF90b3VyKHN0cnVjdCBub2RlKiByb290KXsKCWlmIChyb290ID09IE5VTEwpCiAgICAgIHByaW50ZigiZW1wdHkgdHJlZSIpOwogICAgZWxzZQogICAgICB2aXNpdChyb290KTsKfQogCmludCBtYWluKCkKewoJaW50IG47CglzY2FuZigiJWQiLCZuKTsKCWludCBhW25dLGk7CgkJCiAgICBzdHJ1Y3Qgbm9kZSogcm9vdD1OVUxMIDsKICAgIGZvcihpPTA7aTw9bi0xO2krKyl7CiAgICAJc2NhbmYoIiVkIiwmYVtpXSk7CgkgICAgcm9vdCA9IG5ld25vZGUocm9vdCxhW2ldKTsKICAgIH0KCXByZV9maXhfdG91cihyb290KTsgCn0KCgo=
compilation info
prog.c: In function ‘fix’:
prog.c:73:28: error: ‘struct node’ has no member named ‘color’; did you mean ‘colour’?
if ((f->parent)&&(f->parent->color=='B')) return;
^~
prog.c:73:43: warning: ‘return’ with no value, in function returning non-void
if ((f->parent)&&(f->parent->color=='B')) return;
^~~~~~
prog.c:70:14: note: declared here
struct node* fix(struct node *root,struct node *f) //fixing new node inserted
^~~
stdout