redblacktreetesterproject

Class RedBlackTree

java.lang.Object

redblacktreetesterproject.RedBlackTree

public class RedBlackTree
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
RedBlackTree() Notes from CLR "Introduction To Algorithms" Reb Black Trees A red-black tree is a binary search tree with an extra bit of storage per node.

Method Summary

Modifier and Type	Method and Description
java.lang.String	closeBy(java.lang.String v) The method closeBy(v) returns a value close to v in the tree.
boolean	contains(java.lang.String v) The boolean contains() returns true if the String v is in the RedBlackTree and false otherwise.
int	getRecentCompares()
int	getSize()
int	height() This method calls the recursive method.
int	height(RedBlackNode t) This a recursive routine that is used to compute the height of the red black tree.
void	inOrderTraversal() The no argument inOrderTraversal() method calls the recursive inOrderTraversal(RedBlackNode) - passing the root.
void	inOrderTraversal(RedBlackNode t) Perfrom an inorder traversal of the tree.
void	insert(java.lang.String value) The insert() method places a data item into the tree.
void	leftRotate(RedBlackNode x) leftRotate() performs a single left rotation.
void	levelOrderTraversal() This method displays the RedBlackTree in level order.
static void	main(java.lang.String[] args) Test the RedBlack tree.
void	RBInsertFixup(RedBlackNode z) Fixing up the tree so that Red Black Properties are preserved.
void	reverseOrderTraversal() The no argument reverseOrderTraversal() method calls the recursive reverseOrderTraversal(RedBlackNode) - passing the root.
void	reverseOrderTraversal(RedBlackNode t) Perform a reverseOrder traversal of the tree.
void	rightRotate(RedBlackNode x) rightRotate() performs a single right rotation This would normally be a private method.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RedBlackTree

public RedBlackTree()

 Notes from CLR "Introduction To Algorithms"

 Reb Black Trees
 A red-black tree is a binary search tree with an extra bit of storage per node.
 The extra bit represents the color of the node. It's either red or black.
 Each node contains the fields: color, key, left, right, and p. Any nil
 pointers are regarded as pointers to external nodes (leaves) and key bearing
 nodes are considered as internal nodes of the tree.

 Red-black tree properties:
 1. Every node is either red or black.
 2. The root is black.
 3. Every leaf (nil) is black.
 4. If a node is red then both of its children are black.
 5. For each node, all paths from the node to descendant leaves contain the
    same number of black nodes.

 From these properties, it can be shown (by an iduction proof) that
 the tree has a height no more than 2 * Lg(n + 1).

 In the implementation of the tree, we use a single node to represent all
 of the external nulls. Its color will always be black. The parent pointer (p)
 in the root will point to this node and so will all the internal nodes
 that would normally contain a left or right value of null. In other words,
 instead of containing a null pointer as a left child or a null pointer as a
 right child, these internal nodes will point to the one node that represents
 the external nulls.

 This constructor creates an empty RedBlackTree.
 It creates a RedBlackNode that represents null.
 It sets the internal variable tree to point to this
 node. This node that an empty tree points to will be 
 used as a sentinel node. That is, all pointers in the 
 tree that would normally contain the value null, will instead
 point to this sentinel node.
 

Method Detail

getSize

public int getSize()

Returns:

number of values inserted into the tree.

inOrderTraversal

public void inOrderTraversal(RedBlackNode t)

Perfrom an inorder traversal of the tree. The inOrderTraversal(RedBlackNode) method is recursive and displays the content of the tree. It makes calls on System.out.println(). This method would normally be private.

Parameters:

t - the root of the tree on the first call.

inOrderTraversal

public void inOrderTraversal()

The no argument inOrderTraversal() method calls the recursive inOrderTraversal(RedBlackNode) - passing the root.

reverseOrderTraversal

public void reverseOrderTraversal(RedBlackNode t)

Perform a reverseOrder traversal of the tree. The reverseOrderTraversal(RedBlackNode) method is recursive and displays the content of the tree in reverse order. This method would normally be private.

Parameters:

t - the root of the tree on the first call.

reverseOrderTraversal

public void reverseOrderTraversal()

The no argument reverseOrderTraversal() method calls the recursive reverseOrderTraversal(RedBlackNode) - passing the root.

insert

public void insert(java.lang.String value)

The insert() method places a data item into the tree. It executes the following algorithm from CLR:

 Insertions
 pseudocode for
 RB-Insert(T,z)
    y = nil[T]
    x = root[T]
    while x != nil[T]
         y = x
         if key[z] < key[x] then
             x = left[x]
         else
             x = right[x]
    p[z] = y
    if y = nil[T]
         root[T] = z
    else
       if key[z] < key[y] then
          left[y] = z
       else
          right[y] = z
    left[z] = nil[T]
    right[z] = nil[T]
    color[z] = RED
    RB-Insert-fixup(T,z)

 

Parameters:

value - is an integer to be inserted

Pre-condition:

memory is available for insertion

leftRotate

public void leftRotate(RedBlackNode x)

leftRotate() performs a single left rotation. This would normally be a private method. It executes the following algorithm from CLR.

 pseudocode for left rotations
 pre: right[x] != nil[T]
 pre: root's parent is nill[T]

 Left-Rotate(T,x)
    y = right[x]
    right[x] = left[y]
    p[left[y]] = x
    p[y] = p[x]


    if p[x] == nil[T] then root[T] = y
    else
       if x == left[p[x]] then left[p[x]] = y
       else
          right[p[x]] = y
    left[y] = x
    p[x] = y
    

rightRotate

public void rightRotate(RedBlackNode x)

rightRotate() performs a single right rotation This would normally be a private method. It executes the following algorithm from CLR.

 pseudocode for right rotation
 pre: left[x] != nil[T]
 pre: root's parent is nill[T]
 Right-Rotate(T,x)
    y = left[x]           // y now points to node to left of x
    left[x] = right[y]    // y's right subtree becomes x's left subtree
    p[right[y]] = x       // right subtree of y gets a new parent
    p[y] = p[x]           // y's parent is now x's parent

    // if x is at root then y becomes new root
    if p[x] == nil[T] then root[T] = y
    else
        // if x is a left child then adjust x's parent's left child or...

         if x == left[p[x]] then left[p[x]] = y
         else
         // adjust x's parent's right child
            right[p[x]] = y
    // the right child of y is now x
    right[y] = x
    // the parent of x is now y
    p[x] = y
 

RBInsertFixup

public void RBInsertFixup(RedBlackNode z)

Fixing up the tree so that Red Black Properties are preserved. This would normally be a private method.

  Here, I will outline two pseudocode descriptions.
  The first will be for understanding and the second
  will be closer to an implemenatation.

 Fixing up the tree so that Red Black Properties
 are preserved.
  Tracing-level Pseudo-code for RB-Insert-fixup
  When writing code, it's probably better to work from the
  more low-level pseudo-code below.

  RB-Insert-fixup(T,z) {
  while(z's parent is Red) {
      set y to be z's uncle
      if uncle y is Red {
               color parent and uncle black
               color grandparent red
               set z to grandparent
      }
      else {  // the uncle is black
              if (zig zag) { // make it a zig zig
                             set z to parent
                             rotate to zig zig
                           }
              // rotate the zig zig and finish
              color parent of z black
              color grandparent of z red
              rotate grand parent of z
           }
   } // end while
  color root black
 }




  Low-level Pseudo-code for RB-Insert-fixup
  RB-Insert-fixup(T,z)
  while color[p[z]] = RED {
    if p[z] == left[p[p[z]]] {
         y = right[p[p[z]]]
         if color[y] = RED {
             color[p[z]] = BLACK
             color[y] = BLACK
             color[p[p[z]]] = RED
             z = p[p[z]]
         }
         else {
             if z = right[p[z]] {
                  z = p[z]
                  LEFT-Rotate(T,z)
             }
             color[p[z]] = BLACK
             color[p[p[z]]] = RED
             RIGHT-Rotate(T,p[p[z]])
         }
    }
    else {
         y = left[p[p[z]]]
         if color[y] = RED {
             color[p[z]] = BLACK
             color[y] = BLACK
             color[p[p[z]]] = RED
             z = p[p[z]]
         }
         else
             {
             if z = left[p[z]] {
                  z = p[z]
                  RIGHT-Rotate(T,z)
             }
             color[p[z]] = BLACK
             color[p[p[z]]] = RED
             LEFT-Rotate(T,p[p[z]])
         } // end else
    } // end else
    
  } // end while
  color[root[T]] = BLACK
  

Parameters:

z - is the new node

contains

public boolean contains(java.lang.String v)

The boolean contains() returns true if the String v is in the RedBlackTree and false otherwise. It counts each comparison it makes in the variable recentCompares.

Parameters:

x - the value to search for

Returns:

true if v is in the tree, false otherwise;

getRecentCompares

public int getRecentCompares()

Returns:

number of comparisons made in last call on the contains method.

closeBy

public java.lang.String closeBy(java.lang.String v)

The method closeBy(v) returns a value close to v in the tree. If v is found in the tree it returns v.

Parameters:

v - the value to search close by for.

height

public int height(RedBlackNode t)

This a recursive routine that is used to compute the height of the red black tree. It is called by the height() method. The height() method passes the root of the tree to this method. This method would normally be private.

Parameters:

t - a pointer to a node in the tree.

Returns:

the height of node t

height

public int height()

This method calls the recursive method.

Returns:

the height of the red black tree.

levelOrderTraversal

public void levelOrderTraversal()

This method displays the RedBlackTree in level order. It first displays the root. Then it displays all children of the root. Then it displays all nodes on level 3 and so on. It is not recursive. It uses a queue.

main

public static void main(java.lang.String[] args)

Test the RedBlack tree.

 For a quick test of your solution, run the following main routine.
 You should get output very similar to mine.

 
  public static void main(String[] args) {

        RedBlackTree rbt = new RedBlackTree();

        for(int j = 1; j <= 5; j++) rbt.insert(""+j);
        
        // after 1..5 are inserted
        System.out.println("RBT in order");
        rbt.inOrderTraversal();
        System.out.println("RBT level order");
        rbt.levelOrderTraversal();
        
       // is 3 in the tree
        
        if(rbt.contains(""+3)) System.out.println("Found 3");
        else System.out.println("No 3 found"); 
        
        // display the height
        System.out.println("The height is " + rbt.height());   
        
    }
    
    RBT in order
    [data = 1:Color = Black:Parent = 2: LC = -1: RC = -1]
    [data = 2:Color = Black:Parent = -1: LC = 1: RC = 4]
    [data = 3:Color = Red:Parent = 4: LC = -1: RC = -1]
    [data = 4:Color = Black:Parent = 2: LC = 3: RC = 5]
    [data = 5:Color = Red:Parent = 4: LC = -1: RC = -1]
    RBT level order
    [data = 2:Color = Black:Parent = -1: LC = 1: RC = 4]
    [data = 1:Color = Black:Parent = 2: LC = -1: RC = -1]
    [data = 4:Color = Black:Parent = 2: LC = 3: RC = 5]
    [data = 3:Color = Red:Parent = 4: LC = -1: RC = -1]
    [data = 5:Color = Red:Parent = 4: LC = -1: RC = -1]
    Found 3
    The height is 2

Parameters:

args - no command line arguments