HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML
 

"Pointer Free Data Structures"
Vol. 1, Issue 3, P.40

	

Listing 1: The node class

//RBNode is a node of our tree. This class will 
//never be manipulated directly as the user will 
//deal with RBTree which in turn manipulates many 
//instances of RBNode.
class RBNode {
	
private int key;
private byte color;

private RBNode left;
private RBNode right;
public RBNode parent;
	
//constructors: 
	
//used when we are creating "dummy" nodes
public RBNode() {
	this.left = null;
	this.right = null;
	this.parent = null;
}
	
//creates a new node in the tree with the values passed in.
public RBNode( int theKey, String theColor, RBNode p ) {
	this.setKey( theKey );
	this.setColor( theColor );
	this.left = null;
	this.right = null;
	this.parent = p;
}
	
//accepts an int and places it in the key variable. 
//I chose not to do any error
//checking here, but this was done mainly for brevity.
public void setKey( int k ) { 
	this.key = k; 
}
		
//return the current key
public int getKey() { 
	return this.key; 
}
		
//accepts either "red" or "black" as Strings and 
//sets the color bit accordingly
public void setColor( String c ) {
	if ( "red".equals( c )) 
		this.color = 1; 
	else if ( "black".equals( c )) 
		this.color = 0; 
}
		
//return the color as a string
public String getColor() {
	if ( this.color == 1 ) { return "red"; }
	return "black";
}
	
//returns the right node
public RBNode getRight() throws NoSuchNodeException {
	//if there is no right node, we throw an exception
	if ( this.right == null ) 
	throw new NoSuchNodeException( "right", this );
		
	//otherwise we return the right node
	return this.right;
}
	
//returns the left node
public RBNode getLeft() throws NoSuchNodeException{
	//if there is no left node, we throw an exception
	if ( this.left == null ) 
	throw new NoSuchNodeException( "left", this );
		
	//otherwise we return the left node
	return this.left;
}
	
//return the parent node
public RBNode getParent() throws NoSuchNodeException {
	//test for a null parent; for example the root of the tree
	if ( this.parent == null ) 
	throw new NoSuchNodeException( "parent", this );
		
	//return the parent if no exception is thrown
	return this.parent;
}
	
//sets the left node to newNode
public void setLeft( RBNode newNode ) {
	this.left = newNode;
}
	
//sets the right node to newNode
public void setRight( RBNode newNode ) {
	this.right = newNode;
}
	
	//sets the parent node to newNode
	public void setParent( RBNode newNode ) {
		this.parent = newNode;
	}
}

Listing 2: Defining the Exception

public class NoSuchNodeException extends Exception {
public String attrName;
public Object newValue;
	
NoSuchNodeException( String name, Object value ) {
	super( "The node named \"" + name + "\" DNE" );
	attrName = name;
	newValue = value;
}
}


Listing 3: An RBTree

//RBTree represents the tree and the methods required to manipulate it. 
class RBTree {
//the root of our tree
public RBNode theRBTree;
	
//used in the rotate and split methods to manage links
//grandchild node
private RBNode grandchild = null;  	
//child node
private RBNode child = null; 		
//current node
private RBNode currNode = null; 	
//parent node
private RBNode parent = null; 		
//grandparent node
private RBNode grand = null; 		
//great-grandparent node
private RBNode great = null; 		
	
//constructor used when the tree is created with an
//initial value
public RBTree ( int firstInt ) { 
	grandchild = null;
	child = null;
	currNode = null; 
	parent = null;
	grand = null;
	great = null; 
	theRBTree = new RBNode( firstInt, "red", null ); 
}
		
//constructor used when the tree is not created with an
//initial value
public RBTree() {
	theRBTree = null;
	grandchild = null;
	child = null;
	currNode = null; 
	parent = null;
	grand = null;
	great = null; 
}	
	
//the insert method which is passed an int
public void insert( int theInt ) { 
this.insert( theInt, theRBTree, theRBTree, theRBTree, theRBTree); 
}
	
//private insert method which recursively 
//calls itself in order to insert the node 
//at the correct spot
private void insert( int theInt, RBNode currNode, 
RBNode parent, RBNode 
	grand, RBNode great ) {
//find and insert the current int into the tree
//is this the first node being inserted
if ( currNode == null ) {
theRBTree = new RBNode( theInt, "red", null); 
   }
else {
//is the current node a "4 node"
try {	
if ( "red".equals( currNode.getLeft().getColor() ) && 
"red".equals( currNode.getRight().getColor() ))
	{ split( theInt, currNode, parent, grand, great ); }																		
	 }
catch ( NoSuchNodeException nsne) { }	   
	
//do we belong to the left of the current node?
if ( theInt < currNode.getKey() ) {
//attempt to call insert with the left node. 
//If the left node is null, and exception
//will be thrown and we will not be able to insert the node.
try { 
this.insert( theInt, currNode.getLeft(), currNode, parent, 
	grand ); }
	catch ( NoSuchNodeException nsne ) {
	//move parent, grand, great "up" one node
	great = grand;
    grand = parent;
	    parent = currNode;	    

currNode.setLeft( new RBNode( theInt, "red", currNode ));
//will never be thrown
try{	currNode = currNode.getLeft(); }
catch( NoSuchNodeException dummy ) { }

split( theInt, currNode, parent, grand, great );
try {	currNode.getRight().setColor( "black" ); }
catch ( NoSuchNodeException nsne2 ) {}		
}
}
		
//do we belong to the right of the current node?
else if ( theInt > currNode.getKey() ) {
try { 
this.insert( theInt, currNode.getRight(), currNode, parent, 			
		grand ); }
catch ( NoSuchNodeException nsne ) {
great = grand;
grand = parent;
parent = currNode;	    
				
currNode.setRight( new RBNode( theInt, "red", parent ));
//will never be thrown
try{	currNode = currNode.getRight(); }
catch( NoSuchNodeException dummy ) { }
				
split( theInt, currNode, parent, grand, great );
try {	currNode.getRight().setColor( "black" ); }
catch ( NoSuchNodeException nsne2 ) {}		
}
}
}
}
		
		
private void split( int theInt, RBNode currNode, 
RBNode parent, RBNode 
	grand, RBNode great ) {
//set new colors ... this defines the node structure
currNode.setColor( "red" );
try { currNode.getLeft().setColor( "black" ); }
catch ( NoSuchNodeException nsne ) {}
try { currNode.getRight().setColor( "black" ); }
catch ( NoSuchNodeException nsne ) {}

if ( "red".equals( parent.getColor() )) {
grand.setColor( "red" );
if ( (theInt < grand.getKey()) != (theInt < parent.getKey()) ) {
	try{	parent = rotate( theInt, grand ); }
	catch( NoSuchNodeException nsne ) { }
}
			
try{	currNode = rotate( theInt, great ); }
catch( NoSuchNodeException nsne ) { }		
	
currNode.setColor( "black" );
}
}
	
private RBNode rotate( int theInt, RBNode theNode ) throws 
NoSuchNodeException {
RBNode grandchild = null;
RBNode child = null;
try { 
child = ( theInt < theNode.getKey() ) ? theNode.getLeft() : 
	theNode.getRight(); 
}
catch ( NoSuchNodeException nsne ) { 
throw new NoSuchNodeException( "child", this); 
}

if( theInt < child.getKey() ) {
try { grandchild = child.getLeft(); }
catch ( NoSuchNodeException nsne ) { 
throw new NoSuchNodeException( "grandchild", this ); 
}
try { child.setLeft( grandchild.getRight() ); }
catch ( NoSuchNodeException nsne ) { 
	child.setLeft( null ); 
}
grandchild.setRight( child );
}
else {
try { grandchild = child.getRight(); }
catch ( NoSuchNodeException nsne ) { 
grandchild = null; 
throw new NoSuchNodeException( "grandchild", this ); 
}
try { child.setRight( grandchild.getLeft() ); }
catch ( NoSuchNodeException nsne ) { 
child.setRight( null ); 
}
grandchild.setLeft( child ); 
}
		
if( theInt < theNode.getKey() ) {
//retain our parent links
grandchild.setParent( theNode );

theNode.setLeft( grandchild );
			
}
else {
grandchild.setParent( theNode );
theNode.setRight( grandchild );
}
return grandchild;
}	
}

 

All Rights Reserved
Copyright ©  2004 SYS-CON Media, Inc.
  E-mail: info@sys-con.com

Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.