Question: Description: Develop a Binary Search Tree data structure in a class named BinarySearchTree that extends the AbstractBinarySearchTree class. Objective(s): Demonstrate basic knowledge of programming using
Description:
Develop a Binary Search Tree data structure in a class named BinarySearchTree that extends the AbstractBinarySearchTree class.
Objective(s):
Demonstrate basic knowledge of programming using Java Generics.
Demonstrate their ability to extend existing data structures for use in new ones.
Use Test-Driven Development.
Requirements:
Your class must be named BinarySearchTree. You can download a skeleton class here: BinarySearchTree.java
.
Your class must extend the abstract class: AbstractBinarySearchTree. You can download the source file here: AbstractBinarySearchTree.java
. Read this class carefully. It contains inner classes and helper methods that will prove useful in developing your tree. NOTE: Do not modify the abstract class.
Your class must be generic and its method signatures must match those specified in the abstract class.
Your Binary Search Tree must have a no-args constructor. This is what we will use for testing.
Develop tests for your Binary Search Tree. Save your tests in BinarySearchTreeTest.java and submit with your code.
Methods:
You must implement the following methods from the abstract class:
contains: Takes a target element as its argument and returns true if the element is in the tree.
/** * Returns true if the binary tree contains an element that matches * the specified element and false otherwise. * Should run in O( log n ) time. * @param targetElement the element being sought in the tree * @return true if the tree contains the target element */ public abstract boolean contains( T targetElement );
find: Takes as arguments a Node n and a target element. Efficiently searches the subtree rooted at node n. Returns the node that contains the target element. If no such node is found, returns null.
/** * Efficiently searches the subtree rooted at n. * Should run in O( log n ) time. * @param n - root of a subtree * @param target - the element sought * @return returns the node in the subtree rooted at n that contains the target element */ public abstract Node find( Node n, T target );
getMaxNode: Takes as its argument a Node. Searches the subtree rooted at its argument. Returns the node containing the maximum element.
/** * Returns the node with the largest element in the subtree rooted at * the given node. * Should run in O( log n ) time * @return the node with the largest element in the subtree */ public abstract Node getMaxNode( Node node );
getNextLarger: Takes as an argument a node. Returns the node containing the next larger element from the argument node.
/** * Returns the node with the biggest element in the subtree rooted at * the given node. * Should run in O( log n ) time * @return the next biggest Node in the subtree rooted at node */ public abstract Node getNextLarger( Node node );
height: Returns the height of the given node.
/** * @param node * @return 1 + the maximum height of a child of node, where a leaf has height 0. * @throws IllegalArgumentException if node is null */ public abstract int height( Node node );
removeElement: Removes the node containing the given element from the tree.
/** * Removes and returns the specified element from this tree. * * @param targetElement the element to be removed from the tree * @return the element to be removed from the tree * @throws IllegalArgumentException if targetElement is null */ public abstract T removeElement( T targetElement );
inorderIterator: Returns an iterator that steps through the elements in the tree as if by inorder traversal.
/** * Returns an iterator that represents an inorder traversal on this binary tree. * * @return an iterator over the elements of this binary tree */ public abstract Iterator inorderIterator( );
Testing:
You must develop your tests for methods specified in the abstract class. Then develop your Binary Search Tree to meet the tests. See Test-Driven Development. As an example of some tests, you can see InstructorBinarySearchTreeTest.java
BinarySearchTree.java
import java.util.ArrayList;
import java.util.Iterator;
/**
* A Binary Search Tree is a binary tree that has the property that for
any
* given node A in the tree, the value of the nodes in the left subtree
are
* less than the value of node A and the value of the nodes in the right
subtree
* are greater than the value of node A.
*
* @param
*/
public class BinarySearchTree >
extends AbstractBinarySearchTree {
/**
* Returns true if the binary tree contains an element that matches
* the specified element and false otherwise.
*
* @param targetElement the element being sought in the tree
* @return true if the tree contains the target element
*/
@Override
public boolean contains( T targetElement ) {
// YOUR CODE HERE
}
/**
* Efficiently searches the subtree rooted at n.
* Should run in O( log n ) time.
* @param n - root of a subtree
* @param target - the element sought
* @return returns the node in the subtree rooted at n that contains
the target element
*/
@Override
public Node find( Node node, T target ) {
// YOUR CODE HERE
}
/**
* Returns the node with the largest element in the subtree rooted at
* the given node.
*
* @return the node with the largest element in the subtree
*/
@Override
public Node getMaxNode( Node node ) {
// YOUR CODE HERE
}
/**
* Returns the node with the biggest element in the subtree rooted at
* the given node.
* Should run in O( log n ) time
* @return the next biggest Node in the subtree rooted at node
*/
@Override
public Node getNextLarger( Node node ) {
// YOUR CODE HERE
}
/**
* @param node
* @return 1 + the maximum height of a child of node, where a leaf has
height 0.
* @throws IllegalArgumentException if node is null
*/
public int height( Node node ) {
// YOUR CODE HERE
}
/**
* Removes and returns the specified element from this tree.
*
* @param targetElement the element to be removed from the tree
* @return the element to be removed from the tree
* @throws IllegalArgumentException if targetElement is null
*/
@Override
public T removeElement( T targetElement ) {
// YOUR CODE HERE
}
/**
* Returns an iterator that represents an inorder traversal on this
binary tree.
*
* @return an iterator over the elements of this binary tree
*/
@Override
public Iterator inorderIterator( ) {
// YOUR CODE HERE
}
} // End of BinarySearchTree
AbstractBinarySearchTree.java
import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* AbstractBinarySearchTree defines the methods required in a binary
search tree.
*/
public abstract class AbstractBinarySearchTree
T > >
implements Iterable {
// =================================================================
// Abstract Methods : These are the methods you need to define.
/**
* Returns true if the binary tree contains an element that matches
* the specified element and false otherwise.
* Should run in O( log n ) time.
* @param targetElement the element being sought in the tree
* @return true if the tree contains the target element
*/
public abstract boolean contains( T targetElement );
/**
* Efficiently searches the subtree rooted at n.
* Should run in O( log n ) time.
* @param n - root of a subtree
* @param target - the element sought
* @return returns the node in the subtree rooted at n that contains
the target element
*/
public abstract Node find( Node n, T target );
/**
* Returns the node with the largest element in the subtree rooted at
* the given node.
* Should run in O( log n ) time
* @return the node with the largest element in the subtree
*/
public abstract Node getMaxNode( Node node );
/**
* Returns the node with the biggest element in the subtree rooted at
* the given node.
* Should run in O( log n ) time
* @return the next biggest Node in the subtree rooted at node
*/
public abstract Node getNextLarger( Node node );
/**
* @param node
* @return 1 + the maximum height of a child of node, where a leaf has
height 0.
* @throws IllegalArgumentException if node is null
*/
public abstract int height( Node node );
/**
* Removes and returns the specified element from this tree.
*
* @param targetElement the element to be removed from the tree
* @return the element to be removed from the tree
* @throws IllegalArgumentException if targetElement is null
*/
public abstract T removeElement( T targetElement );
/**
* Returns an iterator that represents an inorder traversal on this
binary tree.
*
* @return an iterator over the elements of this binary tree
*/
public abstract Iterator inorderIterator( );
// END OF ABSTRACT METHODS - You must implement the above methods
// =================================================================
// =================================================================
// Instance Variables, Accessors, and Mutators
private Node root; // Root of the Binary Search Tree
private int size = 0; // Number of elements in the Binary
// Search Tree
private long modificationCount = 0; // Increments every time a change
is made
// to the tree
/**
* @return the root of the binary tree
*/
public Node getRoot( ) {
return root;
}
/**
* Sets the root of the binary tree.
* @param n - a Node
*/
public void setRoot( Node node ) {
root = node;
if ( node != null ) {
node.setParent( null );
}
}
/**
* Returns a reference to the root element
*
* @return a reference to the root
*/
public T getRootElement( ) {
T result = null;
if ( root != null ) {
result = root.getElement( );
}
return result;
}
/**
* Returns the number of elements in this binary tree.
*
* @return the number of elements in the tree
*/
public int size( ) {
return size;
}
/**
* Modify the size of the Binary Search Tree
* @param newSize
*/
protected void setSize( int newSize ) {
size = newSize;
}
protected long getModificationCount( ) {
return modificationCount;
}
protected void incrementModificationCount( ) {
modificationCount++;
}
// END OF VARIABLES, ACCESSORS, MUTATORS
// =================================================================
// =================================================================
// Methods
/**
* Returns true if this binary tree is empty and false otherwise.
*
* @return true if this binary tree is empty, false otherwise
*/
public boolean isEmpty( ) {
return size == 0 || root == null;
}
/**
* Returns a reference to the specified element if it is found in
* this binary tree. Throws an exception if the specified element
* is not found.
*
* @param targetElement the element being sought in the tree
* @return a reference to the specified element
*/
protected Node find( T targetElement ) {
return find( root, targetElement );
}
/**
* @param node
* @return the number of ancestors of node, excluding itself.
*/
public int depth( Node node ) {
if ( node == null ) {
throw new IllegalArgumentException( );
}
if ( node == getRoot( ) ) {
return 0;
}
return 1 + depth( node.getParent( ) );
}
/**
* Returns the node with the smallest element in the subtree rooted at
* the given node.
*
* @return the node with the smallest element in the subtree
*/
protected Node getMinNode( Node node ) {
if ( node == null ) {
return null;
}
if ( node.getLeftChild( ) == null ) {
return node;
}
return getMinNode( node.getLeftChild( ) );
}
public Node getNextSmallest( Node node ) {
if ( node.hasLeftChild( ) ) {
return getMaxNode( node.getLeftChild( ) );
}
return null;
}
/**
* Adds the specified element to the proper location in this tree.
*
* @param element the element to be added to this tree
*/
public void addElement( T element ) {
if ( element == null ) {
throw new IllegalArgumentException( );
}
if ( root == null ) { // adding first element in tree
root = new Node( element );
size++;
modificationCount++;
} else {
addElement( root, element );
}
}
private void addElement( Node node, T element ) {
if ( node == null || element == null ) {
throw new IllegalArgumentException( ); // Should never happen
}
int compare = element.compareTo( node.getElement( ) );
if ( compare == 0 ) { // element goes in current node
node.setElement( element );
modificationCount++;
} else if ( compare
if ( node.getLeftChild( ) != null ) {
addElement( node.getLeftChild( ), element );
} else {
node.setLeftChild( new Node( element, node ) );
size++;
modificationCount++;
}
} else if ( compare > 0 ) { // element belongs in the right subtree
if ( node.getRightChild( ) != null ) {
addElement( node.getRightChild( ), element );
} else {
node.setRightChild( new Node( element, node ) );
size++;
modificationCount++;
}
}
return;
}
/**
* Returns an iterator over the elements of this tree.
*
* @return an iterator over the elements of this binary tree
*/
public Iterator iterator( ) {
ArrayList list = new ArrayList( );
breadthfirstTraversal( getRoot( ), new Visitor( ) {
public void visit( AbstractBinarySearchTree.Node n ) {
list.add( n.getElement( ) );
}
} );
return new BstIterator( list );
}
/**
* Performs a breadth-first traversal over the nodes in the subtree
rooted at node.
* @param node - root of subtree being traversed
* @param v - defines the action to be performed on each node visited
during the traversal
*/
public void breadthfirstTraversal( Node node, Visitor v ) {
ArrayList q = new ArrayList( );
if ( !isEmpty( ) ) {
q.add( node );
while ( !q.isEmpty( ) ) {
Node n = q.remove( 0 );
v.visit( n );
if ( n.hasLeftChild( ) ) {
q.add( n.getLeftChild( ) );
}
if ( n.hasRightChild( ) ) {
q.add( n.getRightChild( ) );
}
}
}
}
/**
* Returns the string representation of this binary tree.
*
* @return a string representation of the binary tree
*/
public String toString( ) {
String result = "[ ";
for ( T element : this ) {
result += element + " ";
}
return result + "]";
}
// END OF METHODS
// =================================================================
// =================================================================
// Constructors
/**
* No-Args Constructor: For creating empty trees.
*/
public AbstractBinarySearchTree( ) {
}
// END OF CONSTRUCTORS
// =================================================================
// =================================================================
// INNER CLASSES - Use these to implement your tree
/**
* Tree node containing an element, a parent, left child, right child.
*/
protected class Node {
private T element;
private Node parent, leftChild, rightChild;
/**
* Creates a new tree node with the specified data.
* @param obj the element that will become a part of the new tree
node
*/
public Node( T obj ) {
element = obj;
parent = null;
leftChild = null;
rightChild = null;
}
/**
* Creates a new tree node with the specified data.
* @param obj the element that will become a part of the new tree
node
* @param parent the parent of the new tree node
*/
public Node( T obj, Node parent ) {
this( obj );
this.parent = parent;
leftChild = null;
rightChild = null;
}
/**
* Creates a new tree node with the specified data.
* @param obj the element that will become a part of the new tree
node
* @param leftChild the left child of the new tree node
* @param rightChild the right child of the new tree node
*/
public Node( T obj, Node leftChild, Node rightChild ) {
this( obj, null );
this.leftChild = leftChild;
this.rightChild = rightChild;
}
/**
* Creates a new tree node with the specified data.
* @param obj the element that will become a part of the new tree
node
* @param leftChild the left child of the new tree node
* @param rightChild the right child of the new tree node
* @param parent the parent of the new tree node
*/
public Node( T obj, Node leftChild, Node rightChild, Node parent ) {
this( obj, leftChild, rightChild );
this.parent = parent;
}
/**
* @return the element stored at this node
*/
public T getElement( ) {
return element;
}
/**
* Set the element of the node
* @param element
*/
public void setElement( T element ) {
this.element = element;
}
/**
* @return the right child of this node
*/
public Node getRightChild( ) {
return rightChild;
}
/**
* Sets the right child of this node.
*
* @param node the right child of this node
*/
public void setRightChild( Node node ) {
rightChild = node;
if ( node != null ) {
node.parent = this;
}
}
/**
* @return true if node has right child
*/
public boolean hasRightChild( ) {
return rightChild != null;
}
/**
* @return the left child of the node
*/
public Node getLeftChild( ) {
return leftChild;
}
/**
* Sets the left child of this node.
*
* @param node the left child of this node
*/
public void setLeftChild( Node node ) {
leftChild = node;
if ( node != null ) {
node.parent = this;
}
}
/**
* @return true if node has left child
*/
public boolean hasLeftChild( ) {
return leftChild != null;
}
/**
* @return true if node is a leaf
*/
public boolean isExternal( ) {
return ( !hasLeftChild( ) && !hasRightChild( ) );
}
/**
* @return true if node has any children
*/
public boolean isInternal( ) {
return hasLeftChild( ) || hasRightChild( );
}
/**
* @return true if node is the root of the tree
*/
public boolean isRoot( ) {
return this == root;
}
/**
* @return true if node has only one child
*/
public boolean hasOneChild( ) {
return ( hasLeftChild( ) && !hasRightChild( ) ) ||
( !hasLeftChild( ) && hasRightChild( ) );
}
/**
* @return true if node has both left and right children
*/
public boolean hasBothChildren( ) {
return hasLeftChild( ) && hasRightChild( );
}
/**
* @return the parent of the node
*/
public Node getParent( ) {
return parent;
}
/**
* Sets the left child of this node.
*
* @param node the left child of this node
*/
public void setParent( Node node ) {
parent = node;
}
/**
* @return true if node has a parent
*/
public boolean hasParent( ) {
return parent != null;
}
/**
* Stringify the node for debugging
*/
public String toString( ) {
return String.format( "
element,
leftChild == null ? null : leftChild.getElement( ),
rightChild == null ? null : rightChild.getElement( ) );
}
} // End of Inner Class Node
/**
* An iterator class that can be used to implement an iterator for the
* nodes in the Binary Search Tree.
*/
public class BstIterator implements Iterator {
// Modifications Count of BST when iterator was created.
long changes = 0;
// Elements from tree to be served up by iterator
ArrayList list = new ArrayList( );
/**
* @return true if there are more elements remaining
*/
@Override
public boolean hasNext( ) {
return !list.isEmpty( );
}
/*
* @return the next available element in the iterator
*
* @throws ConcurrentModificationException - if the tree has been
updated
* since creating the iterator.
*
* @throws NoSuchElementException - if there are no more elements
* available
*/
@Override
public T next( ) {
if ( changes != getModificationCount( ) ) {
throw new ConcurrentModificationException( );
}
if ( list.isEmpty( ) ) {
throw new NoSuchElementException( );
}
return list.remove( 0 );
}
/**
* Constructor
* @param list of elements to iterate over.
*/
public BstIterator( ArrayList list ) {
this.list = list;
changes = getModificationCount( );
}
} // End of Inner Class MyIterator
/**
* Vistor used by lambda expressions to perform an action on each node
in a traversal.
* @param
*/
public interface Visitor > {
public void visit( AbstractBinarySearchTree.Node n );
} // END OF Visitor
// END OF INNER CLASSES
// =================================================================
} // END OF AbstractBinarySearchTree
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help