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