USING JAVA: You are to create a red-black tree which supports only the operation

Question

USING JAVA:

You are to create a red-black tree which supports only the operations listed below. All operations should have time complexity O(log n) when there are n items in the tree, this is the guarantee that red-black trees give. The class should be derived from the TreeMap class in java.util

The only operations which this class supports are:

public boolean is Empty()

public void makeEmpty()

public void insert(Comparable x) throws DuplicateItem

public void delete(Comparable x) throws ItemNotFound

public void deleteMin() throws ItemNotFound

public void deleteMax() throws ItemNotFound

public Object find(Comparable x) throws ItemNotFound

public Object findMin() throws ItemNotFound

public Object findMax() throws ItemNotFound

Your class should be named RBTree

Notes

In no particular order

TreeMap expects Object and the requirement for RBTree is Comparable

TreeMap doesn’t throw any reasonable checked exceptions. Your RBTree class does.

TreeMap expects to perform a mapping of keys to data. RBTree doesn’t. You may find this to present a problem if you’re not careful in the way you implement some of the methods.

The methods in the above list are the only methods that RBTree supports.

Explanation / Answer

public class RedBlackTree {
/**
* Construct the tree.
*/
public RedBlackTree( ) {
header = new RedBlackNode( null );
header.left = header.right = nullNode;
}

// Compare item and t.element, using compareTo, with
  
private final int compare( Comparable item, RedBlackNode t ) {
if( t == header )
return 1;
else
return item.compareTo( t.element );
}

//Insert into the tree.

public void insert( Comparable item ) throws Exception {
current = parent = grand = header;
nullNode.element = item;

while( compare( item, current ) != 0 ) {
great = grand; grand = parent; parent = current;
current = compare( item, current ) < 0 ?
current.left : current.right;

// Check if two red children; fix if so
if( current.left.color == RED && current.right.color == RED )
{}
}

// Insertion fails if already present
if( current != nullNode )
throw new Exception( );
current = new RedBlackNode( item, nullNode, nullNode );

// Attach to parent
if( compare( item, parent ) < 0 )
parent.left = current;
else
parent.right = current;

}

// Remove from the tree.
  
public void remove( Comparable x ) {
throw new UnsupportedOperationException( );
}

  
// Find the smallest item the tree.

public Comparable findMin( ) {
if( isEmpty( ) )
return null;

RedBlackNode itr = header.right;

while( itr.left != nullNode )
itr = itr.left;

return itr.element;
}

// Find the largest item in the tree.
  
public Comparable findMax( ) {
if( isEmpty( ) )
return null;

RedBlackNode itr = header.right;

while( itr.right != nullNode )
itr = itr.right;

return itr.element;
}
  
public Comparable find( Comparable 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;
}
  
  


private static class RedBlackNode {
// Constructors
RedBlackNode( Comparable theElement ) {
this( theElement, null, null );
}

RedBlackNode( Comparable theElement, RedBlackNode lt, RedBlackNode rt ) {
element = theElement;
left = lt;
right = rt;
color = RedBlackTree.BLACK;
}

Comparable element; // The data in the node
RedBlackNode left; // Left child
RedBlackNode right; // Right child
int color; // Color
}

private RedBlackNode header;
private static RedBlackNode nullNode;
static // Static initializer for nullNode
{
nullNode = new RedBlackNode( null );
nullNode.left = nullNode.right = nullNode;
}

private static final int BLACK = 1; // Black must be 1
private static final int RED = 0;

// Used in insert routine and its helpers
private static RedBlackNode current;
private static RedBlackNode parent;
private static RedBlackNode grand;
private static RedBlackNode great;


public static void main( String [ ] args ) throws Exception {
RedBlackTree t = new RedBlackTree( );
final int NUMS = 400000;
final int GAP = 35461;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );

if( ((Integer)(t.findMin( ))).intValue( ) != 1 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 1 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 1; i < NUMS; i++ )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.