Thread: Red-Black tree ranking question

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    117

    Red-Black tree ranking question

    Hello all, so I am doing an assignment that requires me to insert new keys into a Red-Black tree. During this my professor wants us to also update the "odd subtree root ranks" of each node.

    The odd subtree root ranks are the number of odd keys in the subtree to the left.

    So each time I insert a new number I need to balance the tree and then find/update the odd subtree ranks.
    I have already fixed and checked the code for my insertion and balancing and this is working fine.

    The thing I'm stuck on is updating the odd subtree ranks.

    So I am providing some code that I have come up with that I hope is not too confusing that seems to work from the testing I have done so far for one node. After *test* is ran, I update odd into the spot I have saved in that node which is the easy part.

    So, (if this code is working right), my question is how do I do this for the whole tree and not just one node since I need to update it with each insertion?
    I'm confused on this because the only thing I can think of is adding another recursion on top of this which is killing my brain to think of recursion inside of recursion lol.

    Any help/ideas would be appreciated. Thanks


    Code:
    /* h is the head, v is the Key to start with, and odd is a pointer to update until I find the odd rank of that particular node */
    Item test(link h, Key v, int *odd){
         Key t = key(h->item); 
         if (h == z) 
            return NULLitem;
         test(h->l, v, odd);
         if (t < v && t%2 != 0)
            (*odd)++;
         test(h->r, v, odd); 
    }

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You could run the odd count up the tree from the newly-added node something like this:
    Code:
    void updateOdds(Tree *t) {
        if (t && t->p && t->p->lf == t) {
            // t is left child of p
            t->p->odd++;
    	updateOdds(t->p);
        }
    }
    And you'd have to add code to the rotations to update the odd count there too.

    EDIT: Now that I reread your post, I may have misunderstood exactly what you're trying to do. But it does occur to me that it would be optimal if the updating of the odd counts could just be part of the rotations and not need a separate function.
    Last edited by oogabooga; 07-30-2013 at 05:50 PM.

  3. #3
    Registered User
    Join Date
    May 2012
    Posts
    405
    Quote Originally Posted by mgracecar View Post
    Hello all, so I am doing an assignment that requires me to insert new keys into a Red-Black tree. During this my professor wants us to also update the "odd subtree root ranks" of each node.
    Red black trees are nightmarish. I wrote a chapter on them in my book Basic Algorithms.
    Basically you've got to get the idea of rotating nodes left and right to keep the tree in balance. Because a red black tree can only be unbalanced by one following an insert, the number of rotations you have to do is limited. But you still need to go "up" a level to make it work.
    Deleting nodes is where it really gets difficult, because nodes as well as leaves hold data.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  4. #4
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by Malcolm McLean View Post
    Red black trees are nightmarish.
    They're not that bad. (BTW, your signature link does not work.)

    Quote Originally Posted by Malcolm McLean View Post
    Basically you've got to get the idea of rotating nodes left and right to keep the tree in balance.
    Fully agreed: understanding the idea of the tree rotations, and how they keep the tree in balance, is absolutely the key.

    This also applies to other tree types that rely on balancing, like AVL and splay trees. Because splay trees are simpler to implement (although rarely seen in practical applications), they're often explained prior to red-black or AVL trees.

    For me, systematically drawing all the cases -- either using pen and paper, or with something like Dia --, and keeping them and the related operations in order, helps tremendously.

    Basically, I draw all the cases like the case 3 in the insertion chapter in the Wikipedia article on red-black trees, placing the resulting images (usually as PDF) into my personal documentation "article" (be it LaTeX, HTML, OpenDocument or something else). I've learned that simply because I can grok something right now, does not mean I grok it a month from now; better make sure, and document the path I took into understanding the thing.

    (I tried to look for any such set of images on the web, including McLean's homepage, but couldn't find any. There are lots of good resources like course notes, but I didn't find any complete set of images for all the rotations. I didn't spend more than two minutes on it, though.)

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    His problem is not in implementing the red-black tree, though. It's with maintaining a count in each node of the number of odd nodes in it's left subtree.

    Of course, maybe he's finished it by now.

  6. #6
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by oogabooga View Post
    His problem is not in implementing the red-black tree, though.
    But, if you do understand each case on insertion, it should be pretty clear how to maintain the the count of odd subtree root ranks (number of odd keys in the left subtree; I'll just shorten in to "rank" in this post).

    I mean, it's not difficult to find working C code for red-black trees without bothering to understand the underlying logic. I'm not saying it is the case here, but I am saying that adding the ranking code to such implementation without understanding the logic behind the implementation is quite, quite hard. Considering doing the rank updates for the entire tree is a red flag to me, no pun intended.

    The logic itself isn't that complicated, is it? Whenever the left child of a node changes, the rank for that node, and the rank for any parent nodes that descend towards that node on the left side, have to be updated. Also, if the new node is inserted as the left child, then the ranks of all parents that descend towards this node on the left side have to be updated too. Neither of these require recursion, as a simple loop suffices. The key is to realize that prior to the insertion, each left subtree in the tree has their ranks correctly recorded, and how the rotations affect them. To me it looks like the update should be the easiest part to implement.

    I think this extra requirement is a smart move by the professor, culling out those who manage to "copy" working red-black tree code from somewhere, without actually getting any of the deep understanding of how red-black trees work. But, you cannot really fully solve this exercise without understanding something fundamental about how the tree rotations work.

    (However, it is quite possible that my brain is wired completely wrong. In that case, I apologize; no offense was meant. I just wanted to highlight how important I believe (in general, and in particular for this exercise) it is to understand the logic when implementing red-black trees; just constructing a working red-black tree implementation is not sufficient.)

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Nominal Animal View Post
    I think this extra requirement is a smart move by the professor, culling out those who manage to "copy" working red-black tree code from somewhere, without actually getting any of the deep understanding of how red-black trees work. But, you cannot really fully solve this exercise without understanding something fundamental about how the tree rotations work.
    I see. That is clever. I think you're exactly right.

  8. #8
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Hah, I got caught by the very thing I was warning against.

    Now that I actually checked, I realized that the logic I explained above is insufficient: you actually have to keep two ranks in each node: the number of odd values in the left subtree, and the number of odd values in the right subtree. This is because the number of odd values in the left subtree includes the number of odd values in the right subtree of the left child. Recomputing the counts is simple:
    Code:
        if (node->child_left)
            node->odds_left = (node->child_left->value & 1)
                            +  node->child_left->odds_left
                            +  node->child_left->odds_right;
        else
            node->left_odds = 0;
    
        if (node->child_right)
            node->odds_right = (node->child_right->value & 1)
                             +  node->child_right->odds_left
                             +  node->child_right->odds_right;
        else
            node->odds_right = 0;
    When tree rotations are done, the above must be applied to each node that was rotated. (If current and grandparent nodes are rotated to the same depth, then the above has to be applied to the parent node, too.)

    Note that the order in which the above is applied is important: it should be applied depth first (deepest nodes first, considering the after-rotation positions).

    After the tree structure is fixed (following an insertion), the above must also be applied to the parent of the inserted node; ascending towards the root node for as long as the counts change or until root itself is updated.

    This is not recursion, only a single loop done after everything else (plus constant additional work when rotating the tree). Since that single loop is at most O(log N), the insertion will stay O(log N).

    I think this is a darn good exercise on part of the lecturer, especially if they look at the results considering which students to keep an eye on. Clever!
    Last edited by Nominal Animal; 08-01-2013 at 12:28 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with red black tree
    By franciscobom in forum C Programming
    Replies: 2
    Last Post: 04-26-2011, 01:28 AM
  2. Question about red-black tree and little code fragment.
    By mindvera in forum C++ Programming
    Replies: 0
    Last Post: 07-05-2010, 11:42 AM
  3. Help with red black tree
    By jabajaba in forum C++ Programming
    Replies: 2
    Last Post: 11-24-2009, 12:36 AM
  4. Red Black Tree
    By nomes in forum C Programming
    Replies: 2
    Last Post: 10-08-2003, 08:05 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM