Java Assignment

Required to augment the author’s Binary Search Tree (BST) code to support these new operations. Method names below are merely suggestions. (The author’s class is attached separately in the file called “authordoc”. I just built a simple test tree in the author’s main method which can be used to test the various operations. )

1. AnyType nthElement(int n) — returns the n-th element (starting from 1) of the in-order traversal of the BST.

2. int rank( AnyType x ) — returns the “rank” of x. The rank of an element is its position (starting with 1) in an in-order traversal.

3. AnyType median( ) — returns the median (middle) element in the BST. If the BST contains an even number of elements, returns the smaller of the two medians.

4. boolean isPerfect( ) — returns true if the BST is a perfect binary tree.

5. boolean isComplete( ) — returns true if the BST is a complete binary tree.

6. String toString( int nrLevels ) — generates the level-order output described in the sample output below.

Most of these operations could easily be implemented by performing an in-order traversal inside the BST and perhaps placing the results in an ArrayList. However, such a method is extremely inefficient. Instead, we are going to achieve faster performance by “augmenting” the BST nodes. You will add a new private integer data member (“tree size”) to the BinaryNode which stores the size of the tree rooted at that node (including the root). You must develop your own algorithms for these operations, but obviously you will use the new tree size data member to guide your search. Think before you code and think recursively!

These items cover those topics not addressed elsewhere in the project description. (R) indicates a requirement, (H) indicates a hint, and (N) indicates a note.

1. (R) Although we are only using the BST for integers, the BST must remain a generic class.

2. (R) Duplicate values are not allowed. Attempts to insert a duplicate value should be ignored.

3. (R) Attempts to remove non-existent values should be ignored.

4. (R) From a coding perspective, the easiest way to avoid duplicate insertions or attempting to remove non-existent elements is to first call find( ). However, this technique is NOT permitted for two reasons.
Calling find( ) before each insert/remove doubles the running time for these operations and is therefore inefficient.
Recusively coding the insert/remove methods to handle these situations is a great learning experience.

5. (R) The level order print (PRINT command) outputs the value of each node, the size of the tree rooted at that node, and the value of the node’s parent in that order, inside parenthesis, separated by commas. (node value, tree size, parent value). Since the root has no parent, print NULL for the root’s parent value. For readability, separate the levels with a blank line and print no more than 6 node/size/parent values per line. If a level requires multiple lines, use consecutive lines (without a blank line between them).

6. (R) Efficieny counts! Use the most efficient algorithm possible In particular, don’t make multiple searches in the tree when one will do. (Yes, we know it doesn’t matter from an asymptotic analysis point of view.)

7. (H) Almost all of these operations should be written recursively, but not necessarily all of them.

8. (N) As is customary, your BST class should not provide any methods for printing. However, the BST can provide a method that formats a string containing information that the user wishes to print. Overloading the toString( ) method is a common technique to achieve this kind of functionality.

Note: The instructor noted that once the tree is built, it will not be changed during testing of the program. (just to simplify the task if that helps)

package Ast.rt;
import java.util.ArrayList;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) –> Insert x
// void remove( x ) –> Remove x
// boolean contains( x ) –> Return true if x is present
// Comparable findMin( ) –> Return smallest item
// Comparable findMax( ) –> Return largest item
// boolean isEmpty( ) –> Return true if empty; else false
// void makeEmpty( ) –> Remove all items
// void printTree( ) –> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate
/**
* Implements an unbalanced binary search tree.
* Note that all “matching” is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class BinarySearchTree>
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
* @throws Exception
*/
public AnyType findMin( ) throws Exception
{

if( isEmpty( ) )
throw new Exception( );
return findMin( root ).element;

}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
* @throws Exception
*/
public AnyType findMax( ) throws Exception
{
if( isEmpty( ) )
throw new Exception( );
return findMax( root ).element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( “Empty tree” );
else
printTree( root );
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode insert( AnyType x, BinaryNode t )
{
if( t == null )
return new BinaryNode( x, null, null);

int compareResult = x.compareTo( t.element );

if( compareResult < 0 ){ t.left = insert( x, t.left ); } else if( compareResult > 0 ){
t.right = insert( x, t.right );
}
else
; // Duplicate; do nothing
return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode remove( AnyType x, BinaryNode t )
{
if( t == null )
return t; // Item not found; do nothing

int compareResult = x.compareTo( t.element );

if( compareResult < 0 ) t.left = remove( x, t.left ); else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode findMin( BinaryNode t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t )
{
if( t != null )
while( t.right != null )
t = t.right;
return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the subtree.
* @return node containing the matched item.
*/
private boolean contains( AnyType x, BinaryNode t )
{
if( t == null )
return false;

int compareResult = x.compareTo( t.element );

if( compareResult < 0 ) return contains( x, t.left ); else if( compareResult > 0 )
return contains( x, t.right );
else
return true; // Match
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the subtree.
*/
private void printTree( BinaryNode t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
/**
* Internal method to compute height of a subtree.
* @param t the node that roots the subtree.
*/
private int height( BinaryNode t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}

// Basic node stored in unbalanced binary search trees
private static class BinaryNode
{

// Constructors
BinaryNode( AnyType theElement )
{
this( theElement, null, null);

}
BinaryNode( AnyType theElement, BinaryNode lt, BinaryNode rt)
{
element = theElement;
left = lt;
right = rt;

}

AnyType element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
int treeSize;

}

/** The tree root. */
private BinaryNode root;

// Test program
public static void main( String [ ] args ) throws Exception
{
BinarySearchTree t = new BinarySearchTree( );

int[] nums = new int[] {55, 40, 60, 30, 45, 70, 20, 35, 44, 47, 66, 80, 3, 36, 37, 43, 48, 65, 67, 77, 90};

for(int i = 0; i < nums.length; i++) t.insert(nums[i]); t.printTree(); System.out.println( "Checking... (no more output means success)" ); } }