Thread: 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

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

> 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...

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.

I've found this cool java applet http://www.ece.uc.edu/~franco/C321/h.../redblack.html