Skip to content
Java/Ant issues
<project name="Project 3" default="compile" basedir=".">
<description>
A build file for Project 3
</description>
<!-- global properties for this build file -->
<property name="source.dir" location="src"/>
<property name="build.dir" location="bin"/>
<property name="doc.dir" location="doc"/>
<!-- <property name="main.class" value="Proj1.class"/> -->
<!-- set up some directories used by this project -->
<target name="init" description="setup project directories">
<mkdir dir="${build.dir}"/>
<mkdir dir="${doc.dir}"/>
</target>
<!-- Compile the java code in ${src.dir} into ${build.dir} -->
<target name="compile" depends="init" description="compile java sources">
<javac srcdir="${source.dir}" destdir="${build.dir}"/>
</target>
<!-- execute the program with the fully qualified name in ${build.dir} -->
<target name="run" description="run the project">
<java dir="${build.dir}" classname="BinarySearchTree" fork="yes">
</java>
</target>
<!-- Delete the build & doc directories and Emacs backup (*~) files -->
<target name="clean" description="tidy up the workspace">
<delete dir="${build.dir}"/>
<delete dir="${doc.dir}"/>
<delete>
<fileset defaultexcludes="no" dir="${source.dir}" includes="**/*~"/>
</delete>
</target>
<!-- Generate javadocs for current project into ${doc.dir} -->
<target name="doc" depends="init" description="generate documentation">
<javadoc sourcepath="${source.dir}" destdir="${doc.dir}" sourcefiles="src/BinarySearchTree.java"/>
</target>
</project>
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Random;
import java.util.Scanner;
// 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
// int size( ) --> Return number of elements of the tree
// ******************ERRORS********************************
// Throws UnderflowException as appropriate
/**
* Implements an unbalanced binary search tree. Note that all "matching" is
* based on the compareTo method.
*
* @author Kevin Qualters
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
/**
* 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);
}
/**
* Insert into the tree; duplicates are ignored.
*
* @param x
* the item to insert.
*/
public void randomizeinsert(AnyType x) {
root = randomizedinsert(x, root);
}
/**
* Return the number of levels of the tree.
*
*/
public int height() {
return height(root);
}
private static Random random = new Random(123456789);
/**
* 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);
}
/**
* Print the tree contents in level order.
*/
public void orderPrintTree(int L) {
for (int i = 0; i <= L && i < height(); i++) {
System.out.print("Lavel " + i + ": ");
printElement(root, i, 0);
System.out.print("\n");
}
}
private void printElement(BinaryNode<AnyType> t, int L, int currentLevel) {
if (t != null) {
printElement(t.left, L, currentLevel + 1);
if (currentLevel == L)
System.out.print(t.element + " ");
printElement(t.right, L, currentLevel + 1);
}
}
/**
* 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<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
if (t == null)
return new BinaryNode<AnyType>(x, null, null);
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.left = insert(x, t.left);
t.size++;
} else if (compareResult > 0) {
t.right = insert(x, t.right);
t.size++;
}
else
; // Duplicate; do nothing
return t;
}
private BinaryNode<AnyType> insert(BinaryNode<AnyType> node,
BinaryNode<AnyType> t) {
if (t == null)
return node;
int compareResult = node.element.compareTo(t.element);
if (compareResult < 0) {
t.left = insert(node, t.left);
t.size++;
} else if (compareResult > 0) {
t.right = insert(node, t.right);
t.size++;
}
else
; // Duplicate; do nothing
return t;
}
/**
* 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<AnyType> randomizedinsert(AnyType x,
BinaryNode<AnyType> t) {
if (t == null)
return new BinaryNode<AnyType>(x, null, null);
int r = random.nextInt(t.size + 1);
// System.out.println("Size: " + t.size + ", r: " + r);
if (r == t.size) {
System.out.println("Insert at root " + t.element + " node " + x);
return insertAtRoot(x, t);
} else {
int compareResult = x.compareTo(t.element);
if (compareResult < 0)
t.left = randomizedinsert(x, t.left);
else if (compareResult > 0)
t.right = randomizedinsert(x, t.right);
else
; // Duplicate; do nothing
}
t.size = ((t.left != null) ? t.left.size : 0)
+ ((t.right != null) ? t.right.size : 0) + 1;
return t;
}
private BinaryNode<AnyType> insertAtRoot(AnyType x, BinaryNode<AnyType> t) {
BinaryNode<AnyType> temp = new BinaryNode<AnyType>(x);
insert(temp, t);
rotateElement(temp, t);
return temp;
}
/**
* 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<AnyType> remove(AnyType x, BinaryNode<AnyType> 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<AnyType> findMin(BinaryNode<AnyType> 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<AnyType> findMax(BinaryNode<AnyType> 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<AnyType> 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<AnyType> t) {
if (t != null) {
printTree(t.left);
System.out.println(t.element + " size = " + t.size);
printTree(t.right);
}
}
/**
* Internal method to compute height of a subtree.
*
* @param t
* the node that roots the subtree.
*/
private int height(BinaryNode<AnyType> t) {
if (t == null)
return 0;
else
return 1 + Math.max(height(t.left), height(t.right));
}
private void rotateWithLeft(BinaryNode<AnyType> k2,
BinaryNode<AnyType> parent, String side) {
BinaryNode<AnyType> k1 = k2.left;
k2.left = k1.right;
k2.size = 1 + ((k2.right != null) ? k2.right.size : 0)
+ ((k2.left != null) ? k2.left.size : 0);
k1.right = k2;
k1.size = 1 + ((k1.right != null) ? k1.right.size : 0)
+ ((k1.left != null) ? k1.left.size : 0);
if (side.equals("left"))
parent.left = k1;
else if (side.equals("right"))
parent.right = k1;
else
root = k1;
}
private void rotateWithRight(BinaryNode<AnyType> k2,
BinaryNode<AnyType> parent, String side) {
BinaryNode<AnyType> k1 = k2.right;
k2.right = k1.left;
k2.size = 1 + ((k2.right != null) ? k2.right.size : 0)
+ ((k2.left != null) ? k2.left.size : 0);
k1.left = k2;
k1.size = 1 + ((k1.right != null) ? k1.right.size : 0)
+ ((k1.left != null) ? k1.left.size : 0);
if (side.equals("left"))
parent.left = k1;
else if (side.equals("right"))
parent.right = k1;
else
root = k1;
}
private void rotateElement(BinaryNode<AnyType> x, BinaryNode<AnyType> t) {
int n = height(t) - height(x);
AnyType value = x.element;
for (int i = 0; i < n; i++) {
rotateElementHelper(root, null, value, "root");
}
}
private void rotateElementHelper(BinaryNode<AnyType> t,
BinaryNode<AnyType> parent, AnyType value, String side) {
if (t.left != null)
if (t.left.element == value)
rotateWithLeft(t, parent, side);
else
rotateElementHelper(t.left, t, value, "left");
if (t.right != null)
if (t.right.element == value)
rotateWithRight(t, parent, side);
else
rotateElementHelper(t.right, t, value, "right");
}
// Basic node stored in unbalanced binary search trees
private static class BinaryNode<AnyType> {
// Constructors
BinaryNode(AnyType theElement) {
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode<AnyType> lt,
BinaryNode<AnyType> rt) {
element = theElement;
left = lt;
right = rt;
size = (lt != null ? lt.size : 0) + (rt != null ? rt.size : 0) + 1;
}
AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
int size;// size of the subtree
}
/** The tree root. */
private BinaryNode<AnyType> root;
// Test program
public static void main(String[] args)throws Exception{
try{
BinarySearchTree<Integer> BST = new BinarySearchTree<Integer>();
BinarySearchTree<Integer> RBST = new BinarySearchTree<Integer>();
String arg0=args[0];
System.out.println(arg0);
int L = Integer.parseInt(arg0);
String fileName = args[1];
Scanner file = new Scanner(new File(fileName));
while (file.hasNext()) {
int x = file.nextInt();
BST.insert(x);
RBST.randomizeinsert(x);
}
file.close();
System.out.println("\nHeight of the normal BST: " + (BST.height() - 1));
System.out.println("Height of the randomized BST: "
+ (RBST.height() - 1));
System.out.println("\nLevel order print of the normal BST");
BST.orderPrintTree(L);
System.out.println("\nLevel order print of the randomized BST");
RBST.orderPrintTree(L);
System.out.print("\n");
}
catch(Exception e){
System.out.println("Please enter valid arguments");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.