Thread: Help with RB BST

  1. #1
    Registered User
    Join Date
    Feb 2018
    Posts
    21

    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):
    Help with RB BST-capture-png
    The tree that I must get:
    Help with RB BST-tree-png
    (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!
    Last edited by Jacopo; 03-16-2018 at 01:31 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,429
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    3,658
    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.
    Last edited by stahta01; 03-16-2018 at 11:52 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  4. #4
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    Quote Originally Posted by stahta01 View Post
    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].

    Quote Originally Posted by Salem View Post
    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?

    Last edited by Jacopo; 03-17-2018 at 08:58 AM.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,429
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    3,658
    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.
    Last edited by stahta01; 03-17-2018 at 01:03 PM. Reason: grammar
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    Thanks for all this replies. I'll must learn to use a debugger!

Popular pages Recent additions subscribe to a feed

Tags for this Thread