Searching

Red-Black tree

Pinterest LinkedIn Tumblr

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.

Time Complexity

Best CaseAverage CaseWorst Case
O(log n)O(log n)O(log n)

Reference

  1. http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
  2. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
  3. http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
  4. https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-black-trees/

Write A Comment