Red Black tree is self-balanced binary search tree with color information. The Red-Black tree nodes can be either red or black. The color ensures tree balance. The root node and all leaves node set with black color. When inserting new item in the red-black tree, the tree balanced based on these properties. The search operation similar to the binary search tree.
source Code
package com.dsacode.Algorithm.search;
class RedBlackNode {
RedBlackNode( Integer theElement ) {
this( theElement, null, null );
}
RedBlackNode( Integer theElement, RedBlackNode lt, RedBlackNode rt ) {
element = theElement;
left = lt;
right = rt;
color = RedBlackNodeImpl.BLACK;
}
Integer element;
RedBlackNode left;
RedBlackNode right;
int color;
}
public class RedBlackNodeImpl {
public RedBlackNodeImpl( Integer negInf ) {
header = new RedBlackNode( negInf );
header.left = header.right = nullNode;
}
public void insert( Integer item ) {
current = parent = grand = header;
nullNode.element = item;
while( current.element.compareTo( item ) != 0 ) {
great = grand; grand = parent; parent = current;
current = item.compareTo( current.element ) < 0 ?
current.left : current.right;
if( current.left.color == RED && current.right.color == RED )
handleReorient( item );
}
if( current != nullNode )
return;
current = new RedBlackNode( item, nullNode, nullNode );
if( item.compareTo( parent.element ) < 0 )
parent.left = current;
else
parent.right = current;
handleReorient( item );
}
public Integer search( Integer 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.element;
else
return null;
}
}
public void printTree( ) {
if( header.right == nullNode)
System.out.println( "Empty tree" );
else
printTree( header.right );
}
private void printTree( RedBlackNode t ) {
if( t != nullNode ) {
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
private void handleReorient( Integer item ) {
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if( parent.color == RED ) {
grand.color = RED;
if( ( item.compareTo( grand.element ) < 0 ) !=
( item.compareTo( parent.element ) < 0 ) )
parent = rotate( item, grand );
current = rotate( item, great );
current.color = BLACK;
}
header.right.color = BLACK;
}
private RedBlackNode rotate( Integer item, RedBlackNode parent ) {
if( item.compareTo( parent.element ) < 0 )
return parent.left = item.compareTo( parent.left.element ) < 0 ?
rotateWithLeftChild( parent.left ) :
rotateWithRightChild( parent.left ) ;
else
return parent.right = item.compareTo( parent.right.element ) < 0 ?
rotateWithLeftChild( parent.right ) :
rotateWithRightChild( parent.right );
}
static RedBlackNode rotateWithLeftChild( RedBlackNode k2 ) {
RedBlackNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
static RedBlackNode rotateWithRightChild( RedBlackNode k1 ) {
RedBlackNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
private RedBlackNode header;
private static RedBlackNode nullNode;
static
{
nullNode = new RedBlackNode( null );
nullNode.left = nullNode.right = nullNode;
}
static final int BLACK = 1;
static final int RED = 0;
private static RedBlackNode current;
private static RedBlackNode parent;
private static RedBlackNode grand;
private static RedBlackNode great;
public static void main( String [ ] args ) {
RedBlackNodeImpl t = new RedBlackNodeImpl( new Integer( Integer.MIN_VALUE ) );
System.out.println( "Insert values to Red Black Tree." );
t.insert( new Integer( 50 ) );
t.insert( new Integer( 23 ) );
t.insert( new Integer( 11 ) );
t.insert( new Integer( 67 ) );
t.insert( new Integer( 99 ) );
System.out.print("Print items from Red Black Tree: ");
t.printTree( );
System.out.println();
if(t.search(11)==11)
System.out.println("Find element 11 in the Red black tree");
else
System.out.println("Not able to find element 11 in the Red black tree");
}
}
Output
Insert values to Red Black Tree.
Print items from Red Black Tree: 11
23
50
67
99
Find element 11 in the Red black tree
Algorithm Explanation
Check the key with current node value. If the value is equal, return the value
If the search key is less than the root node value, search in the left sub-tree. If the value is not available in left sub-tree, return null.
If the search key is greater than the root node value, search in the right subtree. If the value is not available right sub-tree, returns as null.
