Binary Search Tree Array

An Alternative Implementation of the Binary-Search-Tree Data Type

It is intended to contribute to the assessment of the following two learning outcomes:

L2. Design and develop implementations of collection classes, applying the principles of object-oriented programming and conforming to the relevant conventions, standards and accepted best practice in the programming language used.

L3. Identify and implement algorithms, using recursion where appropriate, for a variety of technically demanding tasks including explorations of graphs and search spaces to find and/or arrive at a destination or goal state.

Problem Description

This project illustrates that the binary-search-tree data type has more than one implementation. You can also use the technique described below to save a binary search tree (in fact, any binary tree) to disk so that it can be subsequently retrieved with its original structures.

Develop an array-based implementation of the binary-search-tree data type. Your class, BinarySearchTreeArray<E>, will have the same method specifications as in the BinarySearchTree<E> class but will use indexes to simulate the parent, left and right links. For example, the fields in your embedded Entry<E> class might have:

 

E  element; int  parent,

left,

right;

Similarly, the BinarySearchTreeArray<E> class might have the following three fields

Entry<E>[] tree;

int  root,                size;

The root Entry<E> object is stored in tree[0], and a null reference is indicated by the index, -1.  For example, suppose we create a binary search tree by entering the String objects “dog”, “turtle”, “cat”, “ferret”. The tree would be as follows:

The array representation, with the elements stored in the order in which they are entered, is

dog -1 2 1
turtle 0 3 -1
cat 0 -1 -1
ferret 1 -1 -1

The method definitions are very similar to those in the

BinarySearchTree<E> class, except that an expression such as

root.leftis replaced with tree[root].left

For example, here is a possible definition of the getEntry method

protected Entry<E>getEntry(Object obj) {    int  temp = root,                   comp;

while (temp != -1) {              comp = ((Comparable)obj).compareTo(tree[temp].element);

if (comp == 0)

return tree[temp];

else if (comp < 0)

temp = tree[temp].left;

else

temp = tree[temp].right;

} // while    return null;

}

You will also need to modify the TreeIterator class.

Remember that Entry<E> values are actually references to Entry<E> objects. Some of the time, it will be helpful to replace declarations that in the BinarySearchTree<E> class are Entry<E> variables, with int variables, as is proposed for the root variable for example, because, in the BinarySearchTreeArray<E> class, the “references” to the left and right children and the parent of an Entry will be array indexes. However, there will be places where it will be easier to retain Entry<E> as the type of a variable. For the protected methods such as successor(), getEntry(), deleteEntry() etc. that have Entry<E> parameters or return types you might want to think about which of these should be of type int and which of type Entry<E>.

As           with               BinarySearchTree<E>                you          should           make            your

BinarySearchTreeArray<E> class extendAbstractSet<E>.

The getEntry() method that Collins includes as an example in the project description is intended to be illustrative of one possible implementation – it is not compulsory to use his code for this method if you have a better idea.

You will almost certainly find it easier to write the add() and size() methods first and make sure that these work correctly in your testing before moving on to the others (you will need to include a dummy iterator() method to get the code to compile as this is an abstract method in AbstractSet<E> but it can just throw an UnsupportedOperationException till you get round to writing the TreeIterator class).

The most difficult method to implement is deleteEntry() – when you get round to writing and testing the remove() method that calls it you will find it easier if you test it first with small trees (perhaps start with 3 elements and then move on to 5 elements once it seems to be working with 3) and for debugging purposes you might want to include a method that displays the whole array so that you can see the values of all the fields of each Entry (remember to give the Entry<E> class a toString() method to simplify this), though such a method should not be part of the public interface of the class and you should restrict its visibility.

Removing an element from the binary search tree will create an empty slot in the array where the Entry for that element was located. You will need to give some thought to how to reuse or avoid such slots.

In terms of testing your class, write an application class that creates an instance of the BinarySearchTree class and an instance of your BinarySearchTreeArray class. For each public constructor and method of each class run some test cases, the same for both instances where you can, and output the state of the two trees after each to confirm that they are the same.

Solution

BinarySearchTree.java

importjava.util.*;

public class BinarySearchTree<E> extends AbstractSet<E>

{

protected Entry<E> root;

protectedint size;

/**

*  Initializes this BinarySearchTree object to be empty, to contain only elements

*  of type E, to be ordered by the Comparable interface, and to contain no

*  duplicate elements.

*

*/

publicBinarySearchTree()

{

root = null;

size = 0;

} // default constructor

/**

* Initializes this BinarySearchTree object to contain a shallow copy of

* a specified BinarySearchTree object.

* The worstTime(n) is O(n), where n is the number of elements in the

* specifiedBinarySearchTree object.

*

* @paramotherTree – the specified BinarySearchTree object that this

*                BinarySearchTree object will be assigned a shallow copy of.

*

*/

publicBinarySearchTree (BinarySearchTree<? extends E>otherTree)

{

root = copy (otherTree.root, null);

size = otherTree.size;

} // copy constructor

protected Entry<E> copy (Entry<? extends E> p, Entry<E> parent)

{

if (p != null)

{

Entry<E> q = new Entry<E> (p.element, parent);

q.left = copy (p.left, q);

q.right = copy (p.right, q);

return q;

} // if

return null;

} // method copy

publicboolean equals (Object obj)

{

if (!(objinstanceofBinarySearchTree))

return false;

return equals (root, ((BinarySearchTree<? extends E>)obj).root);

} // method 1-parameter equals

publicboolean equals (Entry<E> p, Entry<? extends E> q)

{

if (p == null || q == null)

return p == q;

if (!p.element.equals (q.element))

return false;

if (equals (p.left, q.left) && equals (p.right, q.right) )

return true;

return false;

} // method 2-parameter equals

/**

*  Returns the size of this BinarySearchTree object.

*

* @return the size of this BinarySearchTree object.

*

*/

publicint size( )

{

return size;

} // method size()

/**

*  Returns an iterator positioned at the smallest element in this

*  BinarySearchTree object.

*

*  @return an iterator positioned at the smallest element in this

*                BinarySearchTreeobject.

*

*/

public Iterator<E> iterator()

{

return new TreeIterator();

} // method iterator

/**

*  Determines if there is at least one element in this BinarySearchTree object that

*  equals a specified element.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*  @paramobj – the element sought in this BinarySearchTree object.

*

*  @return true – if there is an element in this BinarySearchTree object that

*                equals obj; otherwise, return false.

*

*  @throwsClassCastException – if obj cannot be compared to the

*           elements in this BinarySearchTree object.

*  @throwsNullPointerException – if obj is null.

*

*/

publicboolean contains (Object obj)

{

returngetEntry (obj) != null;

} // method contains

/**

*  Ensures that this BinarySearchTree object contains a specified element.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*  @param element – the element whose presence is ensured in this

*                 BinarySearchTreeobject.

*

*  @return true – if this BinarySearchTree object changed as a result of this

*                method call (that is, if element was actually inserted); otherwise,

*                return false.

*

*  @throwsClassCastException – if element cannot be compared to the

*                  elements already in this BinarySearchTree object.

*  @throwsNullPointerException – if element is null.

*

*/

publicboolean add (E element)

{

if (root == null)

{

if (element == null)

throw new NullPointerException();

root = new Entry<E> (element, null);

size++;

return true;

} // empty tree

else

{

Entry<E> temp = root;

int comp;

while (true)

{

comp =  ((Comparable)element).compareTo (temp.element);

if (comp == 0)

return false;

if (comp < 0)

if (temp.left != null)

temp = temp.left;

else

{

temp.left = new Entry<E> (element, temp);

size++;

return true;

} // temp.left == null

else if (temp.right != null)

temp = temp.right;

else

{

temp.right = new Entry<E> (element, temp);

size++;

return true;

} // temp.right == null

} // while

} // root not null

} // method add

/**

*  Ensures that this BinarySearchTree object does not contain a specified

*  element.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*  @paramobj – the object whose absence is ensured in this

*                 BinarySearchTreeobject.

*

*  @return true – if this BinarySearchTree object changed as a result of this

*                method call (that is, if obj was actually removed); otherwise,

*                return false.

*

*  @throwsClassCastException – if obj cannot be compared to the

*                  elements already in this BinarySearchTree object.

*  @throwsNullPointerException – if obj is null.

*

*/

publicboolean remove (Object obj)

{

Entry<E> e = getEntry (obj);

if (e == null)

return false;

deleteEntry (e);

return true;

} // method remove

/**

*  Finds the Entry object that houses a specified element, if there is such an Entry.

*  TheworstTime(n) is O(n), and averageTime(n) is O(log n).

*

*  @paramobj – the element whose Entry is sought.

*

*  @return the Entry object that houses obj – if there is such an Entry;

*                otherwise, return null.

*

*  @throwsClassCastException – if obj is not comparable to the elements

*                  already in this BinarySearchTree object.

*  @throwsNullPointerException – if obj is null.

*

*/

protected Entry<E>getEntry (Object obj)

{

int comp;

if (obj == null)

throw new NullPointerException();

Entry<E> e = root;

while (e != null)

{

comp = ((Comparable)obj).compareTo (e.element);

if (comp == 0)

return e;

else if (comp < 0)

e = e.left;

else

e = e.right;

} // while

return null;

} // method getEntry

/**

*  Deletes the element in a specified Entry object from this BinarySearchTree.

*

*  @param p the Entry object whose element is to be deleted from this

*                 BinarySearchTreeobject.

*

*  @return the Entry object that was actually deleted from this BinarySearchTree

*                object.

*

*/

protected Entry<E>deleteEntry (Entry<E> p)

{

size–;

// If p has two children, replace p’s element with p’s successor’s

// element, then make p reference that successor.

if (p.left != null &&p.right != null)

{

Entry<E> s = successor (p);

p.element = s.element;

p = s;

} // p had two children

// At this point, p has either no children or one child.

Entry<E> replacement;

if (p.left != null)

replacement = p.left;

else

replacement = p.right;

// If p has at least one child, link replacement to p.parent.

if (replacement != null)

{

replacement.parent = p.parent;

if (p.parent == null)

root = replacement;

else if (p == p.parent.left)

p.parent.left  = replacement;

else

p.parent.right = replacement;

} // p has at least one child

else if (p.parent == null)

root = null;

else

{

if (p == p.parent.left)

p.parent.left = null;

else

p.parent.right = null;

} // p has a parent but no children

return p;

} // method deleteEntry

/**

*  Finds the successor of a specified Entry object in this BinarySearchTree.

*  TheworstTime(n) is O(n) and averageTime(n) is constant.

*

*  @param e – the Entry object whose successor is to be found.

*

*  @return the successor of e, if e has a successor; otherwise, return null.

*

*/

protected Entry<E> successor (Entry<E> e)

{

if (e == null)

return null;

else if (e.right != null)

{

// successor is leftmost Entry in right subtree of e

Entry<E> p = e.right;

while (p.left != null)

p = p.left;

return p;

} // e has a right child

else

{

// go up the tree to the left as far as possible, then go up

// to the right.

Entry<E> p = e.parent;

Entry<E>ch = e;

while (p != null &&ch == p.right)

{

ch = p;

p = p.parent;

} // while

return p;

} // e has no right child

} // method successor

protected class TreeIterator implements Iterator<E>

{

protected Entry<E>lastReturned = null,

next;

/**

*  Positions this TreeIterator to the smallest element, according to the Comparable

*  interface, in the BinarySearchTree object.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*/

protectedTreeIterator()

{

next = root;

if (next != null)

while (next.left != null)

next = next.left;

} // default constructor

/**

*  Determines if there are still some elements, in the BinarySearchTree object this

*  TreeIterator object is iterating over, that have not been accessed by this

*  TreeIterator object.

*

*  @return true – if there are still some elements that have not been accessed by

*                thisTreeIterator object; otherwise, return false.

*

*/

publicbooleanhasNext()

{

return next != null;

} // method hasNext

/**

*  Returns the element in the Entry this TreeIterator object was positioned at

*  before this call, and advances this TreeIterator object.

*  TheworstTime(n) is O(n) and averageTime(n) is constant.

*

*  @return the element this TreeIterator object was positioned at before this call.

*

*  @throwsNoSuchElementException – if this TreeIterator object was not

*                 positioned at an Entry before this call.

*

*/

public E next()

{

if (next == null)

throw new NoSuchElementException();

lastReturned = next;

next = successor (next);

returnlastReturned.element;

} // method next

/**

*  Removes the element returned by the most recent call to this TreeIterator

*  object’s next() method.

*  TheworstTime(n) is O(n) and averageTime(n) is constant.

*

*  @throwsIllegalStateException – if this TreeIterator’s next() method was not

*                called before this call, or if this TreeIterator’sremove() method was

*                called between the call to the next() method and this call.

*

*/

public void remove()

{

if (lastReturned == null)

throw new IllegalStateException();

if (lastReturned.left != null &&lastReturned.right != null)

next = lastReturned;

deleteEntry(lastReturned);

lastReturned = null;

} // method remove

} // class TreeIterator

protected static class Entry<E>

{

protected E element;

protected Entry<E> left = null,

right = null,

parent;

/**

*  Initializes this Entry object.

*

*  This default constructor is defined for the sake of subclasses of

*  theBinarySearchTree class.

*/

public Entry() { }

/**

*  Initializes this Entry object from element and parent.

*

*/

public Entry (E element, Entry<E> parent)

{

this.element = element;

this.parent = parent;

} // constructor

} // class Entry

} // class BinarySearchTree 

BinarySearchTreeArray.java

importjava.util.*;

public class BinarySearchTreeArray<E> extends AbstractSet<E>

{

public Entry<E>[] tree;

privateint root;

privateint size;

// next available slot in the array to store a new element.

// this is changed when new element is added or removed from the array.

privateint available;

/**

*  Initializes this BinarySearchTreeArray object to be empty, to contain only elements

*  of type E, to be ordered by the Comparable interface, and to contain no

*  duplicate elements.

*

*/

publicBinarySearchTreeArray()

{

tree = (Entry<E>[])new Entry[4];

root = -1;

size = 0;

available = 0;

} // default constructor

/**

* Initializes this BinarySearchTreeArray object to contain a shallow copy of

* a specified BinarySearchTreeArray object.

* The worstTime(n) is O(n), where n is the number of elements in the

* specifiedBinarySearchTreeArray object.

*

* @paramotherTree – the specified BinarySearchTreeArray object that this

*                BinarySearchTreeArray object will be assigned a shallow copy of.

*

*/

publicBinarySearchTreeArray (BinarySearchTreeArray<? extends E>otherTree)

{

this.tree = copy(otherTree.tree, otherTree.tree.length);

this.root = otherTree.root;

this.size = otherTree.size;

this.available = otherTree.available;

} // copy constructor

private Entry<E>[] copy(Entry<? extends E>[] arr, int capacity)

{

// create a new array with the new capacity, and copy the elements into the new array

final Entry<E>[] newarr = (Entry<E> [])new Entry[capacity];

for (int i = 0; i <arr.length; i++)

{

final Entry<? extends E> e = arr[i];

if (e != null)

{

newarr[i] = new Entry<E>(e.element);

newarr[i].parent = e.parent;

newarr[i].left = e.left;

newarr[i].right = e.right;

}

}

returnnewarr;

}

publicboolean equals (Object obj)

{

if (!(objinstanceofBinarySearchTreeArray))

return false;

finalBinarySearchTreeArray<? extends E> other = (BinarySearchTreeArray<? extends E>)obj;

if (this.size != other.size)

return false;

return equals(this.tree, this.root, other.tree, other.root);

} // method 1-parameter equals

privateboolean equals (Entry<E>[] ps, int i, Entry<? extends E>[] qs, int j)

{

if (i == -1 || j == -1)

return i == j;

final Entry<E> p = ps[i];

final Entry<? extends E> q = qs[j];

if (!p.element.equals (q.element))

return false;

if (equals (ps, p.left, qs, q.left) && equals (ps, p.right, qs, q.right) )

return true;

return false;

} // method 2-parameter equals

/**

*  Returns the size of this BinarySearchTree object.

*

* @return the size of this BinarySearchTree object.

*

*/

publicint size( )

{

return size;

} // method size()

/**

*  Returns an iterator positioned at the smallest element in this

*  BinarySearchTreeArray object.

*

*  @return an iterator positioned at the smallest element in this

*                BinarySearchTreeArrayobject.

*

*/

public Iterator<E> iterator()

{

return new TreeIterator();

} // method iterator

/**

*  Determines if there is at least one element in this BinarySearchTreeArray object that

*  equals a specified element.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*  @paramobj – the element sought in this BinarySearchTreeArray object.

*

*  @return true – if there is an element in this BinarySearchTreeArray object that

*                equals obj; otherwise, return false.

*

*  @throwsClassCastException – if obj cannot be compared to the

*           elements in this BinarySearchTreeArray object.

*  @throwsNullPointerException – if obj is null.

*

*/

publicboolean contains (Object obj)

{

returngetEntry (obj) != -1;

} // method contains

/**

*  Ensures that this BinarySearchTreeArray object contains a specified element.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*  @param element – the element whose presence is ensured in this

*                 BinarySearchTreeArrayobject.

*

*  @return true – if this BinarySearchTreeArray object changed as a result of this

*                method call (that is, if element was actually inserted); otherwise,

*                return false.

*

*  @throwsClassCastException – if element cannot be compared to the

*                  elements already in this BinarySearchTreeArray object.

*  @throwsNullPointerException – if element is null.

*

*/

publicboolean add (E element)

{

if (element == null) // do not allow null element

{

throw new NullPointerException();

}

if (root == -1) // add the first element

{

root = alloc(element);

return true;

}

else

{

int parent = root;

while (true)

{

int comp = ((Comparable)element).compareTo (tree[parent].element);

if (comp == 0)

return false;

if (comp < 0)

if (tree[parent].left != -1)

parent = tree[parent].left;

else

{

int v = alloc(element);

tree[parent].left = v;

tree

[v]

.parent = parent;

return true;

} // temp.left == null

else if (tree[parent].right != -1)

parent = tree[parent].right;

else

{

int v = alloc(element);

tree[parent].right = v;

tree

[v]

.parent = parent;

return true;

} // temp.right == null

} // while

} // root not null

} // method add

// a helper function to allocate the new element from the array.

// the available field is used to efficiently find the location to put the element.

privateintalloc(E element)

{

System.out.println(“size=” + size);

if (size == tree.length) // the tree is already full, expand it

{

tree = copy(tree, size * 2);

available = size;

}

while (tree[available] != null) // find next available array slot

{

available = (available + 1) % this.tree.length;

}

tree[available] = new Entry<E>(element);

size ++;

System.out.println(tree.length + ” ” + available);

return available;

}

/**

*  Ensures that this BinarySearchTreeArray object does not contain a specified

*  element.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*  @paramobj – the object whose absence is ensured in this

*                 BinarySearchTreeArrayobject.

*

*  @return true – if this BinarySearchTreeArray object changed as a result of this

*                method call (that is, if obj was actually removed); otherwise,

*                return false.

*

*  @throwsClassCastException – if obj cannot be compared to the

*                  elements already in this BinarySearchTreeArray object.

*  @throwsNullPointerException – if obj is null.

*

*/

publicboolean remove (Object obj)

{

int e = getEntry (obj);

if (e == -1)

return false;

e = deleteEntry (e);

tree[e] = null;

if (e < available)

{

// update the available slot so we can use the array efficiently

available = e;

}

return true;

} // method remove

/**

*  Finds the index of Entry object that houses a specified element, if there is such an Entry.

*  TheworstTime(n) is O(n), and averageTime(n) is O(log n).

*

*  @paramobj – the element whose Entry is sought.

*

*  @return the Entry object that houses obj – if there is such an Entry;

*                otherwise, return null.

*

*  @throwsClassCastException – if obj is not comparable to the elements

*                  already in this BinarySearchTreeArray object.

*  @throwsNullPointerException – if obj is null.

*

*/

privateintgetEntry (Object obj)

{

if (obj == null)

throw new NullPointerException();

int parent = root;

while (parent != -1)

{

int comp = ((Comparable)obj).compareTo (tree[parent].element);

if (comp == 0)

break;

else if (comp < 0)

parent = tree[parent].left;

else

parent = tree[parent].right;

} // while

return parent;

} // method getEntry

/**

*  Deletes the element in a specified Entry object from this BinarySearchTreeArray,

*  given the index of the entry.

*

*  @param p the Entry object whose element is to be deleted from this

*                 BinarySearchTreeArrayobject.

*

*  @return the index of Entry object that was actually deleted from this BinarySearchTreeArray

*                object.

*

*/

privateintdeleteEntry (int p)

{

size–;

Entry<E> e = tree[p];

// If p has two children, replace p’s element with p’s successor’s

// element, then make p reference that successor.

if (e.left != -1 &&e.right != -1)

{

int s = successor (p);

e.element = tree[s].element;

p = s;

e = tree[p];

} // p had two children

// At this point, p has either no children or one child.

int replacement;

if (e.left != -1)

replacement = e.left;

else

replacement = e.right;

// If p has at least one child, link replacement to p.parent.

if (replacement != -1)

{

tree[replacement].parent = e.parent;

if (e.parent == -1)

root = replacement;

else if (p == tree[e.parent].left)

tree[e.parent].left  = replacement;

else

tree[e.parent].right = replacement;

} // p has at least one child

else if (e.parent == -1)

root = -1;

else

{

if (p == tree[e.parent].left)

tree[e.parent].left = -1;

else

tree[e.parent].right = -1;

} // p has a parent but no children

return p;

} // method deleteEntry

/**

*  Finds the successor of a specified Entry object in this BinarySearchTreeArray.

*  TheworstTime(n) is O(n) and averageTime(n) is constant.

*

*  @param e – the index of Entry object whose successor is to be found.

*

*  @return the index of successor of e, if e has a successor; otherwise, return -1.

*

*/

privateint successor (int e)

{

if (e == -1)

return e;

else if (tree[e].right != -1)

{

// successor is leftmost Entry in right subtree of e

e = tree[e].right;

while (tree[e].left != -1)

e = tree[e].left;

return e;

} // e has a right child

else

{

// go up the tree to the left as far as possible, then go up

// to the right.

int p = tree[e].parent;

intch = e;

while (p != -1 &&ch == tree[p].right)

{

ch = p;

p = tree[p].parent;

} // while

return p;

} // e has no right child

} // method successor

protected class TreeIterator implements Iterator<E>

{

protectedintlastReturned = -1,

next;

/**

*  Positions this TreeIterator to the smallest element, according to the Comparable

*  interface, in the BinarySearchTreeArray object.

*  TheworstTime(n) is O(n) and averageTime(n) is O(log n).

*

*/

protectedTreeIterator()

{

next = root;

if (next != -1)

while (tree[next].left != -1)

next = tree[next].left;

} // default constructor

/**

*  Determines if there are still some elements, in the BinarySearchTreeArray object this

*  TreeIterator object is iterating over, that have not been accessed by this

*  TreeIterator object.

*

*  @return true – if there are still some elements that have not been accessed by

*                thisTreeIterator object; otherwise, return false.

*

*/

publicbooleanhasNext()

{

return next != -1;

} // method hasNext

/**

*  Returns the element in the Entry this TreeIterator object was positioned at

*  before this call, and advances this TreeIterator object.

*  TheworstTime(n) is O(n) and averageTime(n) is constant.

*

*  @return the element this TreeIterator object was positioned at before this call.

*

*  @throwsNoSuchElementException – if this TreeIterator object was not

*                 positioned at an Entry before this call.

*

*/

public E next()

{

if (next == -1)

throw new NoSuchElementException();

lastReturned = next;

next = successor (next);

return tree[lastReturned].element;

} // method next

/**

*  Removes the element returned by the most recent call to this TreeIterator

*  object’s next() method.

*  TheworstTime(n) is O(n) and averageTime(n) is constant.

*

*  @throwsIllegalStateException – if this TreeIterator’s next() method was not

*                called before this call, or if this TreeIterator’sremove() method was

*                called between the call to the next() method and this call.

*

*/

public void remove()

{

if (lastReturned == -1)

throw new IllegalStateException();

if (tree[lastReturned].left != -1 && tree[lastReturned].right != -1)

next = lastReturned;

deleteEntry(lastReturned);

lastReturned = -1;

} // method remove

} // class TreeIterator

protected static class Entry<E>

{

protected E element;

protectedint parent;

protectedint left;

protectedint right;

/**

*  Initializes this Entry object.

*

*  This default constructor is defined for the sake of subclasses of

*  theBinarySearchTreeArray class.

*/

public Entry() { }

/**

*  Initializes this Entry object from element and parent.

*

*/

public Entry (E element)

{

this.element = element;

this.parent = -1;

this.left = -1;

this.right = -1;

} // constructor

} // class Entry

} // class BinarySearchTreeArray 

Test.java

importjava.util.*;

public class Test

{

static Random r = new Random();

public static void main(String[] args)

{

AbstractSet<Integer> s1 = new BinarySearchTree<>();

BinarySearchTreeArray<Integer> s2 = new BinarySearchTreeArray<>();

// iterator is tested in the add& remove functions.

testAdd(s1, s2);

testRemove(s1, s2);

// copy constructor and compare

System.out.println(“Copying BinarySearchTreeArray(s2) into BinarySearchTreeArray(s3)…”);

BinarySearchTreeArray<Integer> s3 = new BinarySearchTreeArray<>(s2);

System.out.println(“s2 == s3? ” + s2.equals(s3) + “\n”);

}

public static void testAdd(AbstractSet<Integer> s1, AbstractSet<Integer> s2)

{

// test add function

// add random numbers into s1 and s2.

// s2 should contains the same number of s1.

finalint n = 20;

System.out.printf(“Adding %d random numbers into BinarySearchTree(s1) and BinarySearchTreeArray(s2).\n”, n);

while (s1.size() < n)

{

int v = r.nextInt(100);

s1.add(v);

s2.add(v);

}

System.out.println(“s1.size=” + s1.size() + ” s2.size=” + s2.size());

System.out.println(“Both Trees should have the same numbers (using iterators).”);

System.out.printf(” id Tree1 Tree2\n”);

final Iterator<Integer> i1 = s1.iterator();

final Iterator<Integer> i2 = s2.iterator();

for (int i = 0; i < n; i++)

{

System.out.printf(“%3d %5d %5d\n”, i, i1.next(), i2.next());

}

System.out.println();

}

public static void testRemove(AbstractSet<Integer> s1, BinarySearchTreeArray<Integer> s2)

{

// test remove function

finalint n = 100;

System.out.printf(“Removing %d random numbers from BinarySearchTree(s1) and BinarySearchTreeArray(s2).\n”, n);

for (int i = 0; i < n; i++)

{

int v = r.nextInt(100);

s1.remove(v);

s2.remove(v);

}

System.out.println(“s1.size=” + s1.size() + ” s2.size=” + s2.size());

System.out.println(“Both Trees should have the same numbers (using iterators).”);

System.out.printf(” id Tree1 Tree2\n”);

final Iterator<Integer> i1 = s1.iterator();

final Iterator<Integer> i2 = s2.iterator();

for (int i = 0; i < s1.size() || i < s2.size(); i++)

{

System.out.printf(“%3d %5d %5d\n”, i, i1.next(), i2.next());

}

System.out.println();

}

}