Hello again!
My hard work given me another big issue!
So, I'm doing my Insert function for my red and black Binary Search Tree. My function is: ([n] is node to insert, [y] is pointer that points the node that come first of [x], because when [x] will point the sentinel, then [y] will be the last valid node)
Code:
bool Insert(Tree *t, Node *n) {
printf("\n");
Node *y = t->sentinel;
Node *x = t->root;
while(x != t->sentinel) {
y = x;
if (x->key == n->key) {
printf("There is already a node with this key!\n");
return false;
}
else
if (n->key < x->key)
x = x->left;
else
x = x->right;
}
printf("n : %p [%d]\n", n, n->key);
printf("y : %p [%d]\n", y, y->key);
printf("y father (grandpa) : %p [%d]\n", y->father, y->father->key); <--- Error!
if (y == t->sentinel)
t->root = n;
else
if (n->key < y->key)
y->left = n;
else
y->right = n;
n->father = y;
n->left = n->right = t->sentinel;
n->color = 1;
printf("[n] father : %p [%d]\n", n->father, n->father->key);
printf("[n] grandpa : %p", n->father->father);
printf(" [%d]\n", n->father->father->key);
RB_Insert_Fixup(t, n);
return true;
}
Ok, this code doesn't work..this is output (for the root node I have another function):
The tree that I must get:
(Sorry for this horrible drawing)
I think that the problem is that, for some reason, the function "forgets" which is the "A"'s grandpa (namely "H"), but why? The address of "A" remains the same, but once time the code know her grandpa and the next time no..please help me!