Red Black Tree Restructure

This is a discussion on Red Black Tree Restructure within the C Programming forums, part of the General Programming Boards category; I guess this is more of a general programming question rather than a C question but since the project is ...

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    11

    Red Black Tree Restructure

    I guess this is more of a general programming question rather than a C question but since the project is in C I thought I would post it here. In a RedBlack tree when we do a removal or insertion we sometimes have to do a restructure, which calls for naming the leftmost node in the subtree of x,y,z, A as found by an inorder traversal, B would then be the next leftmost node and C would be rightmost node. Here is my question: can I just compare the keys of each of the three nodes x,y,z and label them as A,B,C the lowest being A, and so on? I cannot think of any case where this would not work so if someone knows I would sure appreciate the help.

    ie
    10
    4 14
    3 6 11 18

    Now if we have a double red between 10-4-6 we could just take A to be the lowest key of the three nodes, B would be the second and so on. This seems correct to me but I may be missing something. Thanks

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    11
    The tree came out all messed up. Sorry about that, I guess it takes out whitespace before text. Let's try this again.

    : 10
    : 4 14
    : 3 6 11 18

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,499
    > Here is my question: can I just compare the keys of each of the three nodes x,y,z and label them as A,B,C the lowest being A, and so on?
    Here's your answer
    http://www.nist.gov/dads/HTML/redblack.html

    Do some research, and try and understand the algorithms. If you really understand them, then the answer should be self-evident.

    There's no room for guessing here...

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    11
    I am using trinode restructuring to fix the tree and the link looks to use rotation instead of trinode restructuring. Either way it seems that there should be no problem with doing this. I have done extensive research, but have never really found any straight answer as to whether I can just take the lowest key and so on for trinode restructuring. I think I understand the algorithm I just wanted to be sure.

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. I need some ideas please>>
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 08-23-2002, 01:55 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21