

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object redblacktreeproject.RedBlackTree
public class RedBlackTree
Constructor Summary  

RedBlackTree()
Notes from CLR "Introduction To Algorithms" Reb Black Trees A redblack 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 

public RedBlackTree()
Notes from CLR "Introduction To Algorithms" Reb Black Trees A redblack 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. Redblack 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 

public void inOrderTraversal(RedBlackNode t)
t
 the root of the tree on the first call.public void inOrderTraversal()
public void insert(int value)
Insertions pseudocode for RBInsert(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 RBInsertfixup(T,z)
value
 is an integer to be insertedpublic void leftRotate(RedBlackNode x)
pseudocode for left rotations pre: right[x] != nil[T] pre: root's parent is nill[T] LeftRotate(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
public void rightRotate(RedBlackNode x)
pseudocode for right rotation pre: left[x] != nil[T] pre: root's parent is nill[T] RightRotate(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
public void RBInsertFixup(RedBlackNode z)
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. Tracinglevel Pseudocode for RBInsertfixup When writing code, it's probably better to work from the more lowlevel pseudocode below. RBInsertfixup(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 } Lowlevel Pseudocode for RBInsertfixup RBInsertfixup(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] LEFTRotate(T,z) } color[p[z]] = BLACK color[p[p[z]]] = RED RIGHTRotate(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] RIGHTRotate(T,z) } color[p[z]] = BLACK color[p[p[z]]] = RED LEFTRotate(T,p[p[z]]) } } color[root[T]] = BLACK }
z
 is the new nodepublic boolean contains(int v)
x
 the vaue to search for
public void levelOrderTraversal()
public static void main(java.lang.String[] args)
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]
args
 no command line arguments


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 