Tree

Red Block Tree implementation

Pinterest LinkedIn Tumblr

The red-black tree is a binary search tree with color information. The color can be either red or black and it helps to balance the tree. The red-black tree has a complex implementation. The red-black binary search tree is an efficient data structure for maintaining the balanced binary search.

The red-black tree node color is either red or black. The root node is always black. Every node contains two children nodes and color can be red or black. Every leaf node colored as black. Every red node has black colored children. If the application requires more insertion or deletion, the red-black tree can be used.

Write a program to implement red-black tree?

Algorithm Explanation

The red black tree supports insert, lookup, delete and print operations.
Insert operation inset the element to the red black tree and maintain the red black properties.
It uses Binary search tree algorithm to add the node in the red-black tree, color the node and make sure the red-black tree properties
Delete operation verifies the color of the sibling to decide the red-black properties. It performs the standard binary search operation and make sure the red-black tree properties.

Source Code

package com.dsacode.DataStructre.redblocktree;
 
import sun.reflect.generics.reflectiveObjects.NotImplementedException;
 
class RedBlackNode {
    RedBlackNode( Integer theElement ) {
        this( theElement, null, null );
    }
 
    RedBlackNode( Integer theElement, RedBlackNode lt, RedBlackNode rt ) {
        element  = theElement;
        left     = lt;
        right    = rt;
        color    = RedBlackTreeImpl.BLACK;
    }
 
    Integer   element;   
    RedBlackNode left;      
    RedBlackNode right;     
    int          color;     
}
 
 
public class RedBlackTreeImpl {
    static final int BLACK = 1;   
    static final int RED   = 0;
     
    private RedBlackNode header;
    private static RedBlackNode nullNode;
     
    static{
                nullNode = new RedBlackNode( null );
                nullNode.left = nullNode.right = nullNode;
            }
 
    private static RedBlackNode current;
    private static RedBlackNode parent;
    private static RedBlackNode grand;
    private static RedBlackNode great;
 
         
    public RedBlackTreeImpl( 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 void remove( Comparable < RedBlackNode > x ) {
        throw new NotImplementedException();
    }
 
    
    public Integer findMin() {
        if( isEmpty( ) )
            return null;
 
        RedBlackNode itr = header.right;
 
        while( itr.left != nullNode )
            itr = itr.left;
 
        return itr.element;
    }
 
    
    public Integer findMax( ) {
        if( isEmpty( ) )
            return null;
 
        RedBlackNode itr = header.right;
 
        while( itr.right != nullNode )
            itr = itr.right;
 
        return itr.element;
    }
 
    public Integer find( 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 makeEmpty( )   {
        header.right = nullNode;
    }
 
    public boolean isEmpty( ) {
        return header.right == nullNode;
    }
 
     
    public void printTree( ) {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( header.right );
    }
 
    private void printTree( RedBlackNode t ) {
        if( t != nullNode )
        {
            printTree( t.left );
            System.out.print( 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;
    }
     
    public static void main(String[] args) {
        RedBlackTreeImpl t = new RedBlackTreeImpl( 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();
             
            System.out.println("Find element :"+t.find(11));
             
            System.out.println("Find Minimum :"+t.findMin());
            System.out.println("Find Maximum :"+t.findMax());
             
          
    }
 
}

Output

Insert values to Red Black Tree.
Print items from Red Black Tree: 11 23 50 67 99
Find element :11
Find Minimum :11
Find Maximum :99

Source Explanation

Red black tree inserts and print the tree values. It find the minimum element and find the maximum element from the tree.
Insert operation inserts the new node into the red black tree. It make sure the red-black tree properties.
Delete operation deletes the node and make sure the red-black tree properties.
The red black tree uses RedBlackNode which contain the left, right nodes, color value and the element value.

Complexity

OperationsBest CaseAverage Caseworst Case
SearchO(log(n))O(log(n))
InsertionO(log(n))O(log(n))
DeletionO(log(n))O(log(n))

Real Applications

  1. Process scheduler in Linux uses Red Black Trees
  2. Computational Geometry Data structures
  3. Various implementations of Associative Data structures
  4. STL implementation of Map uses a Red-Black Tree.
  5. java.util.TreeMap java.util.TreeSet

Reference

  1. https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
  2. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
  3. http://www.cs.cornell.edu/courses/cs3110/2014sp/lectures/11/red-black-trees.html
  4. http://pages.cs.wisc.edu/~skrentny/cs367-common/readings/Red-Black-Trees

Write A Comment