Thread: Help with RB BST

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!

So now would be a good time to figure out how to use the debugger.
Do things like
- set breakpoints
- single step lines of code
- examine variables, and even change them if they're wrong.

Can you explain line 6?
Edit3: Ignore this question you stated your logic in the first post; I have no idea if it is good logic.

Code:

y = x;

Other than assigning y a pseudo random value I see no need for it.

NOTE: I have never done Red/Black BST code.
Edit: I re-read your post and your words on why might make sense; but, since I have not done RB BST it fails to have meaning to me.
Edit2: You can ignore my post; but, the variable names X and Y make little sense to me; if they are not the normal names in the RB BST problem domain, I think it might be a good idea to change them.

Tim S.

Originally Posted by stahta01

Can you explain line 6?
Edit3: Ignore this question you stated your logic in the first post; I have no idea if it is good logic.

Code:

y = x;

Other than assigning y a pseudo random value I see no need for it.

NOTE: I have never done Red/Black BST code.
Edit: I re-read your post and your words on why might make sense; but, since I have not done RB BST it fails to have meaning to me.
Edit2: You can ignore my post; but, the variable names X and Y make little sense to me; if they are not the normal names in the RB BST problem domain, I think it might be a good idea to change them.

Tim S.

[x] and [y] are only two pointers that I use for scan the tree. I need the [y] pointer because when [x] exits from the while-loop it will be ever a sentinel node ( = null node) but I need instead the last node avaiable, that is the node previous [x], that is [y].

Originally Posted by Salem

So now would be a good time to figure out how to use the debugger.
Do things like
- set breakpoints
- single step lines of code
- examine variables, and even change them if they're wrong.

You are right, but I'm not able to use debugger tool yet. Anyway I did some tests and I understood that the problem should be the "RB_Insert_Fixup(t, n)" because removing it, the code recognises the "A"'s grandpa..

Code:

void RB_Insert_Fixup(Tree *t, Node *n) {
    Node *grandpa = n->father->father;            //[n]'s grandpa.
    Node *uncle = NULL;                           //[n]'s uncle.
    if (n->father == grandpa->left)               //if the father of [n] is a left child..
        uncle = grandpa->right;                     //..then [uncle] is a right child.
    else
        uncle = grandpa->left;                      //..then [uncle] is a left child.
    
    if(n->father->color == 1) {                 //if [n]'s father is red we have the violations!
        if (uncle->color == 0 && n == n->father->left) {  //if [uncle] is black and [n] is a left child..
            n->father = 0;                      //The [n]'s fahter become red.
            grandpa->color = 1;                   //[grandpa] become black.
            Right_Rotate(t, grandpa);
        } else if (uncle->color == 0 && n == n->father->right) { //If [uncle] is black and [n] is a right child..
            Left_Rotate(t, n->father);
            n->father = 0;                      //The [n]'s fahter become red.
            grandpa->color = 1;                   //[grandpa] become black.
            Right_Rotate(t, grandpa);
        } else if (uncle->color == 1) {           //if [uncle] is red..
            while(n != t->sentinel) {
                n->father = 0;                  //The [n]'s fahter become red.
                grandpa->color = 1;               //[grandpa] become black.
                n = n->father->father;
            }
        }
    }

}

I know that for you this is a really difficult problem to solve in this way.. but can you help me?

So when are you planning to learn how to use a debugger?
There is no point in delaying this essential step. IMO, you've already left it too late.

Even just running the code in the debugger and letting it point you to the line of code which crashes will tell you a hell of a lot more than your blind dart throwing approach.

Sorry, but sooner or later, you need to have the skills to dig yourself out of holes of your own making.

Telling you 'x' is wrong just doesn't help you in the long run.

Even I who does not use the debugger normally can use the gdb bt (backtrace) command on the command line to find where it crashes.
And, I do use the IDE gui debugger to step and check values when it exists for my platform.
I got in the habit of not using the debugger because they used to be harder to use and they were missing on most of the embedded platforms I have worked with.
Or, they added so much size, that the program stopped fitting in the embedded unit.

FYI: If the problem goes away when running in an debugger, this often means one variable/pointer is over writing another variable memory area.

Tim S.