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.

You don't need a main method as the teach will have his own source code

Explanation / Answer

public class RBTree {

public RBTree() {
header = new RBNode( null );
header.left = header.right = nullNode;
}

private final int compare( Comparable item, RBNode t ) {
if( t == header )
return 1;
else
return item.compareTo( t.element );
}

public boolean isEmpty() {
return header.right == nullNode;
}

public void makeEmpty() {
header.right = nullNode;
}

public RBNode<T> contains(Comparable data) {
RBNode current = header;
while( data.compareTo(current.element != 0 ) {
if( data.compareTo(current.element < 0 ) {
current = current.left;
} else {
current = current.right();
}
if( current == null || current.deleted ) {
return null;
}
}
return current;
}

public void delete() {
deleted = true;
}

public boolean delete( Comparable item ) throws Exception {
RBNode node = contains(item);

if( node != null ) {
node.delete();
return true;
} else {
throw new Exception("Data does not exist: " + data.toString());
}
}

public void insert(Comparable item ) {
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;

if( current.left.color == RED && current.right.color == RED )
handleReorient( item );
}

if( current != nullNode )
throw new DuplicateItemException( item.toString( ) );
current = new RBNode( item, nullNode, nullNode );

if( compare( item, parent ) < 0 )
parent.left = current;
else
parent.right = current;
handleReorient( item );
}

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 Comparable findMin() {
if( isEmpty() )
return null;

RBNode itr = header.right;

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

return itr.element;
}

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

RBNode itr = header.right;

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

return itr.element;
}


private void handleReorient(Comparable item ) {
// Do the color flip
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;

if( parent.color == RED ) // Have to rotate
{
grand.color = RED;
if( ( compare( item, grand ) < 0 ) !=
( compare( item, parent ) < 0 ) )
parent = rotate( item, grand ); // Start dbl rotate
current = rotate( item, great );
current.color = BLACK;
}
header.right.color = BLACK;
}

private RBNode rotate(Comparable item, RBNode parent ) {
if( compare( item, parent ) < 0 )
return parent.left = compare( item, parent.left ) < 0 ?
rotateWithLeftChild( parent.left ) : // LL
rotateWithRightChild( parent.left ) ; // LR
else
return parent.right = compare( item, parent.right ) < 0 ?
rotateWithLeftChild( parent.right ) : // RL
rotateWithRightChild( parent.right ); // RR
}

/**
* Rotate binary tree node with left child.
*/
private static RBNode rotateWithLeftChild( RBNode k2 ) {
RBNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}

/**
* Rotate binary tree node with right child.
*/
private static RBNode rotateWithRightChild( RBNode k1 ) {
RBNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}

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

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

Comparable element; // The data in the node
RBNode left; // Left child
RBNode right; // Right child
int color; // Color
boolean deleted;

}

private RBNode header;
private static RBNode nullNode;
static // Static initializer for nullNode
{
nullNode = new RBNode( 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 RBNode current;
private static RBNode parent;
private static RBNode grand;
private static RBNode great;

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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