redblacktreeproject
Class RedBlackTree

java.lang.Object
  redblacktreeproject.RedBlackTree

public class RedBlackTree
extends java.lang.Object

Constructor Summary

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

boolean	contains(int v) The boolean contains() returns true if the integer is in the RedBlackTree and false otherwise.
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(int 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	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.
 

Method Detail

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

insert

public void insert(int 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

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]])
         }
    }
    color[root[T]] = BLACK
  }
  

Parameters:

z - is the new node

contains

public boolean contains(int v)

The boolean contains() returns true if the integer is in the RedBlackTree and false otherwise.

Parameters:

x - the vaue to search for

Returns:

true if v is in the tree, false otherwise;

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.

 To test 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);
      for(int j = 100; j > 90; j--) rbt.insert(j);

      System.out.println("RBT in order");
      rbt.inOrderTraversal();
      System.out.println("RBT level order");
      rbt.levelOrderTraversal();
 }
RBT in order
[data = 1:Color = Black:Parent = 2: LC = -1: RC = -1]
[data = 2:Color = Black:Parent = 4: LC = 1: RC = 3]
[data = 3:Color = Black:Parent = 2: LC = -1: RC = -1]
[data = 4:Color = Black:Parent = -1: LC = 2: RC = 97]
[data = 5:Color = Red:Parent = 91: LC = -1: RC = -1]
[data = 91:Color = Black:Parent = 93: LC = 5: RC = 92]
[data = 92:Color = Red:Parent = 91: LC = -1: RC = -1]
[data = 93:Color = Red:Parent = 95: LC = 91: RC = 94]
[data = 94:Color = Black:Parent = 93: LC = -1: RC = -1]
[data = 95:Color = Black:Parent = 97: LC = 93: RC = 96]
[data = 96:Color = Black:Parent = 95: LC = -1: RC = -1]
[data = 97:Color = Red:Parent = 4: LC = 95: RC = 99]
[data = 98:Color = Black:Parent = 99: LC = -1: RC = -1]
[data = 99:Color = Black:Parent = 97: LC = 98: RC = 100]
[data = 100:Color = Black:Parent = 99: LC = -1: RC = -1]
RBT level order
[data = 4:Color = Black:Parent = -1: LC = 2: RC = 97]
[data = 2:Color = Black:Parent = 4: LC = 1: RC = 3]
[data = 97:Color = Red:Parent = 4: LC = 95: RC = 99]
[data = 1:Color = Black:Parent = 2: LC = -1: RC = -1]
[data = 3:Color = Black:Parent = 2: LC = -1: RC = -1]
[data = 95:Color = Black:Parent = 97: LC = 93: RC = 96]
[data = 99:Color = Black:Parent = 97: LC = 98: RC = 100]
[data = 93:Color = Red:Parent = 95: LC = 91: RC = 94]
[data = 96:Color = Black:Parent = 95: LC = -1: RC = -1]
[data = 98:Color = Black:Parent = 99: LC = -1: RC = -1]
[data = 100:Color = Black:Parent = 99: LC = -1: RC = -1]
[data = 91:Color = Black:Parent = 93: LC = 5: RC = 92]
[data = 94:Color = Black:Parent = 93: LC = -1: RC = -1]
[data = 5:Color = Red:Parent = 91: LC = -1: RC = -1]
[data = 92:Color = Red:Parent = 91: LC = -1: RC = -1]


Parameters:
args - no command line arguments