Search code examples
javared-black-tree

RedBlackTrees Structure?

I cannot manage to get my head around redbacktrees, based on this implementation http://pastebin.com/Gg3YbPUg.

/**
 * Insert into the tree.
 * @param item the item to insert.
 * @throws DuplicateItemException if item is already present.
 */
public void insert( AnyType item )
{
    current = parent = grand = header;
    nullNode.element = item;

    while( compare( item, current ) != 0 )
    {
        great = grand; grand = parent; parent = current;
        current = compare( item, current ) < 0 ?
                     current.left : current.right;

            // Check if two red children; fix if so
        if( current.left.color == RED && current.right.color == RED )
             handleReorient( item );
    }

        // Insertion fails if already present
    if( current != nullNode )
        throw new DuplicateItemException( item.toString( ) );
    current = new RedBlackNode<AnyType>( item, nullNode, nullNode );

        // Attach to parent
    if( compare( item, parent ) < 0 )
        parent.left = current;
    else
        parent.right = current;
    handleReorient( item );
}

I've just made a simple tree using the numbers 1,14,15,2,11,7,5,8

// Test program
public static void main( String [ ] args )
{
    RedBlackTree<Integer> t = new RedBlackTree<Integer>( );

    t.insert(1);
    t.insert(14);
    t.insert(15);
    t.insert(2);
    t.insert(11);
    t.insert(7);
    t.insert(5);
    t.insert(8);

    t.printTree();
}

And based off the example from http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html, My Tree should look something like...

RBT

And my console output from the printTree function

/**
 * Print all items.
 */
public void printTree( )
{
    printTree( header.right );
}

/**
 * Internal method to print a subtree in sorted order.
 * @param t the node that roots the tree.
 */
private void printTree( RedBlackNode<AnyType> t )
{
    if( t != nullNode )
    {
        printTree( t.left );
        System.out.println("main element is <" + t.element + "("+t.color+")> left <" + t.left.element +"> right <" + t.right.element + ">" );
        printTree( t.right );
    }
}

Is...

main element is <1(COLOR:RED)> left <8> right <8>
main element is <2(COLOR:BLACK)> left <1> right <5>
main element is <5(COLOR:RED)> left <8> right <8>
main element is <7(COLOR:RED)> left <2> right <14>
main element is <8(COLOR:BLACK)> left <8> right <8>
main element is <11(COLOR:RED)> left <8> right <8>
main element is <14(COLOR:BLACK)> left <11> right <15>
main element is <15(COLOR:RED)> left <8> right <8>

(for reading purposes I have renamed 0 and 1 as COLOR RED AND BLACK) From what I understand the "header" variable is the root of the tree.

If I was to do something like

 public void function(AnyType x)
 {
    RedBlackNode<AnyType> n = find(x);
    //what is the parent of n?
 }

/**
 * Find an item in the tree.
 * @param x the item to search for.
 * @return the matching item or null if not found.
 */
public RedBlackNode<AnyType> find( AnyType x )
{
    nullNode.element = x;
    current = header.right;

    for( ; ; )
    {
        if( x.compareTo( current.element ) < 0 )
            current = current.left;
        else if( x.compareTo( current.element ) > 0 ) 
            current = current.right;
        else if( current != nullNode )
            return current;
        else
            return null;
    }
}

From the above pastebin implementation of RedBlackTree how do I know what my current parent element is for n?

Solution

  • If it's a proper red-black tree, abides by the rules, then the root has to be black, so 1 cannot be the root.

    I've build a red-black tree in Java which has a much better print-out if you are interested:

    └── (Black) 8
    ├── (Black) 2
    │   ├── (Red) 1
    │   │   ├── (Black) null
    │   │   └── (Black) null
    │   └── (Red) 5
    │       ├── (Black) null
    │       └── (Black) null
    └── (Red) 15
        ├── (Black) 11
        │   ├── (Black) null
        │   └── (Red) 14
        │       ├── (Black) null
        │       └── (Black) null
        └── (Black) 17
            ├── (Black) null
            └── (Black) null

    Here is the code to the red-black tree, check out the RedBlackTreePrinter class to see how I built the console output.