Notes

#include <stdio.h>
#include <stdlib.h>

typedef struct rb_node
{
enum {red, black } color;
int key;
struct rb_node *left,
*right,
*parent;
} t_rb_node;
typedef struct
{
t_rb_node *root;
} t_rb_arbore;

int make_root(t_rb_arbore *a,int key)
{
t_rb_node *root;
a->root=malloc(sizeof *root);
a->root->key=key;
a->root->left=NULL;
a->root->right=NULL;
a->root->parent=NULL;
a->root->color=black;

return a->root;
}
int create_node(int key)
{
t_rb_node *node;
node=(t_rb_arbore*)malloc(sizeof(t_rb_node));
node->key=key;
node->left=NULL;
node->right=NULL;
node->parent=NULL;
node->color=black;
return node;
}

void inorder_walk(t_rb_node *root)
{
if(root != NULL)
{
inorder_walk(root->left);
printf("%d",root->key);
if (root->color=black)
printf("[b]");
else
printf("[r]");
}
inorder_walk(root->right);
}
int tree_search(t_rb_node *n, int key)
{
if( n==NULL)
if(key=n->key)
return n;
if (key < n->key)
return tree_search(n->left, key);
else
return tree_search(n->right, key);

}


void rb_insert(t_rb_arbore *a, t_rb_node *z)
{
t_rb_node *y=NULL;
t_rb_node *x=a->root;
while(x!=NULL)
{
y=x;
if(z->key < x->key)
x=x->left;
else
x=x->right;
}
z->parent=y;
if(y=NULL)
{
a->root=z;
}
else if (z->key < y->key)
y->left=z;
else
{
y->right=z;
}


z->left=NULL;
z->right=NULL;
z->color=red;
rb_insert_fixup(a,z);




}
void rb_insert_fixup(t_rb_arbore *a,t_rb_node *z)
{ t_rb_node *y;

while((z->parent!=NULL)&&(z->parent->color==red))
{
if(z->parent==z->parent->parent->left)
{
y=z->parent->parent->right;
if((y!=NULL)&&(y->color==red))
{
z->parent->color=black;
y->color=black;
z->parent->parent->color=red;
z=z->parent->parent;
}
else
{
if(z==z->parent->right)
{
z=z->parent;
left_rotate(a,z);
}
z->parent->color=black;
z->parent->parent->color=red;
right_rotate(a,z->parent->parent);
}
}
else


{
y=z->parent->parent->left;
if((y!=NULL)&&(y->color==red))
{
z->parent->color=black;
y->color=black;
z->parent->parent->color=red;
z=z->parent->parent;
}
else
{
if(z==z->parent->left)
{
z=z->parent;
right_rotate(a,z);
}
z->parent->color=black;
z->parent->parent->color=red;
left_rotate(a,z->parent->parent);
}
}
}
a->root->color=black;
}

void left_rotate(t_rb_arbore *a, t_rb_node *x)
{
t_rb_node *y;
y=x->right;
x->right=y->left;
if(y->left != NULL)
y->left->parent=x;
y->parent=x->parent;
if(x->parent=NULL)
a->root=y;
else if(x=x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
}

int main()
{
t_rb_arbore a;
t_rb_node r;
t_rb_node n;
int x;
printf("ROOT=");
scanf("%d", &x);
make_root(&a, x);
printf("introduceti x pana la citirea lui n");
printf("x=");
scanf("%d", &x);
while(x!=0)
{
n=create_node(x);
rb_insert(&a,x);
printf("x=");
scanf("%d", &x);

}
printf("In-order walk: ");
inorder_walk(x);
printf("n");
printf("Cauta un nod cu cheia x= ");
scanf("%d", &x);
n=tree_search(&a, x);
if(n!=NULL)
printf("nodul cu cheia %(n->key) gasit");
else
printf("nodul nu a fost gasit")


return 0;

}
int main()
{

t_rb_arbore a;
t_rb_node *n;
int x;
printf("root=");
scanf("%d",&x);
make_root(&a,x);
printf("Introduceti x pana la citirea 0n");
printf("x=");
scanf("%d",&x);
while(x!=0)
{
n=create_node(x);
rb_insert(&a,n);
printf("x=");
scanf("%d",&x);
}
printf("Nodul care se insereaza este:");
scanf("%d",&x);

if(x!=0)
{
n=create_node(x);
rb_insert(&a,n);
}
return 0;
}