javalinked-listbinary-search-tree
constructing a binary search tree in java
I'm trying to construct this binary search tree in Java:
Here's my linked binary search tree implementation class:
/**
* LinkedBinarySearchTree implements the BinarySearchTreeADT interface
* with links.
*
* @author Java Foundations
* @version 4.0
*/
public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T>
implements BinarySearchTreeADT<T>
{
/**
* Creates an empty binary search tree.
*/
public LinkedBinarySearchTree()
{
super();
}
/**
* Creates a binary search with the specified element as its root.
*
* @param element the element that will be the root of the new binary
* search tree
*/
public LinkedBinarySearchTree(T element)
{
super(element);
if (!(element instanceof Comparable))
throw new NonComparableElementException("LinkedBinarySearchTree");
}
/**
* Adds the specified object to the binary search tree in the
* appropriate position according to its natural order. Note that
* equal elements are added to the right.
*
* @param element the element to be added to the binary search tree
*/
public void addElement(T element)
{
if (!(element instanceof Comparable))
throw new NonComparableElementException("LinkedBinarySearchTree");
Comparable<T> comparableElement = (Comparable<T>)element;
if (isEmpty())
root = new BinaryTreeNode<T>(element);
else
{
if (comparableElement.compareTo(root.getElement()) < 0)
{
if (root.getLeft() == null)
this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
else
addElement(element, root.getLeft());
}
else
{
if (root.getRight() == null)
this.getRootNode().setRight(new BinaryTreeNode<T>(element));
else
addElement(element, root.getRight());
}
}
modCount++;
}
/**
* Adds the specified object to the binary search tree in the
* appropriate position according to its natural order. Note that
* equal elements are added to the right.
*
* @param element the element to be added to the binary search tree
*/
private void addElement(T element, BinaryTreeNode<T> node)
{
Comparable<T> comparableElement = (Comparable<T>)element;
if (comparableElement.compareTo(node.getElement()) < 0)
{
if (node.getLeft() == null)
node.setLeft(new BinaryTreeNode<T>(element));
else
addElement(element, node.getLeft());
}
else
{
if (node.getRight() == null)
node.setRight(new BinaryTreeNode<T>(element));
else
addElement(element, node.getRight());
}
}
/**
* Removes the first element that matches the specified target
* element from the binary search tree and returns a reference to
* it. Throws a ElementNotFoundException if the specified target
* element is not found in the binary search tree.
*
* @param targetElement the element being sought in the binary search tree
* @throws ElementNotFoundException if the target element is not found
*/
public T removeElement(T targetElement)
throws ElementNotFoundException
{
T result = null;
if (isEmpty())
throw new ElementNotFoundException("LinkedBinarySearchTree");
else
{
BinaryTreeNode<T> parent = null;
if (((Comparable<T>)targetElement).equals(root.element))
{
result = root.element;
BinaryTreeNode<T> temp = replacement(root);
if (temp == null)
root = null;
else
{
root.element = temp.element;
root.setRight(temp.right);
root.setLeft(temp.left);
}
modCount--;
}
else
{
parent = root;
if (((Comparable)targetElement).compareTo(root.element) < 0)
result = removeElement(targetElement, root.getLeft(), parent);
else
result = removeElement(targetElement, root.getRight(), parent);
}
}
return result;
}
/**
* Removes the first element that matches the specified target
* element from the binary search tree and returns a reference to
* it. Throws a ElementNotFoundException if the specified target
* element is not found in the binary search tree.
*
* @param targetElement the element being sought in the binary search tree
* @param node the node from which to search
* @param parent the parent of the node from which to search
* @throws ElementNotFoundException if the target element is not found
*/
private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent)
throws ElementNotFoundException
{
T result = null;
if (node == null)
throw new ElementNotFoundException("LinkedBinarySearchTree");
else
{
if (((Comparable<T>)targetElement).equals(node.element))
{
result = node.element;
BinaryTreeNode<T> temp = replacement(node);
if (parent.right == node)
parent.right = temp;
else
parent.left = temp;
modCount--;
}
else
{
parent = node;
if (((Comparable)targetElement).compareTo(node.element) < 0)
result = removeElement(targetElement, node.getLeft(), parent);
else
result = removeElement(targetElement, node.getRight(), parent);
}
}
return result;
}
/**
* Returns a reference to a node that will replace the one
* specified for removal. In the case where the removed node has
* two children, the inorder successor is used as its replacement.
*
* @param node the node to be removed
* @return a reference to the replacing node
*/
private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node)
{
BinaryTreeNode<T> result = null;
if ((node.left == null) && (node.right == null))
result = null;
else if ((node.left != null) && (node.right == null))
result = node.left;
else if ((node.left == null) && (node.right != null))
result = node.right;
else
{
BinaryTreeNode<T> current = node.right;
BinaryTreeNode<T> parent = node;
while (current.left != null)
{
parent = current;
current = current.left;
}
current.left = node.left;
if (node.right != current)
{
parent.left = current.right;
current.right = node.right;
}
result = current;
}
return result;
}
/**
* Removes elements that match the specified target element from
* the binary search tree. Throws a ElementNotFoundException if
* the specified target element is not found in this tree.
*
* @param targetElement the element being sought in the binary search tree
* @throws ElementNotFoundException if the target element is not found
*/
public void removeAllOccurrences(T targetElement)
throws ElementNotFoundException
{
removeElement(targetElement);
try
{
while (contains((T)targetElement))
removeElement(targetElement);
}
catch (Exception ElementNotFoundException)
{
}
}
/**
* Removes the node with the least value from the binary search
* tree and returns a reference to its element. Throws an
* EmptyCollectionException if this tree is empty.
*
* @return a reference to the node with the least value
* @throws EmptyCollectionException if the tree is empty
*/
public T removeMin() throws EmptyCollectionException
{
T result = null;
if (isEmpty())
throw new EmptyCollectionException("LinkedBinarySearchTree");
else
{
if (root.left == null)
{
result = root.element;
root = root.right;
}
else
{
BinaryTreeNode<T> parent = root;
BinaryTreeNode<T> current = root.left;
while (current.left != null)
{
parent = current;
current = current.left;
}
result = current.element;
parent.left = current.right;
}
modCount--;
}
return result;
}
/**
* Removes the node with the highest value from the binary
* search tree and returns a reference to its element. Throws an
* EmptyCollectionException if this tree is empty.
*
* @return a reference to the node with the highest value
* @throws EmptyCollectionException if the tree is empty
*/
public T removeMax() throws EmptyCollectionException
{
T result = null;
if (isEmpty())
throw new EmptyCollectionException ("binary tree");
else
{
if (root.right == null)
{
result = root.element;
root = root.left;
} //if
else
{
BinaryTreeNode<T> parent = root;
BinaryTreeNode<T> current = root.right;
while (current.right != null)
{
parent = current;
current = current.right;
} //while
result = current.element;
parent.right = current.left;
} //else
modCount--;
} //else
return result;
}
/**
* Returns the element with the least value in the binary search
* tree. It does not remove the node from the binary search tree.
* Throws an EmptyCollectionException if this tree is empty.
*
* @return the element with the least value
* @throws EmptyCollectionException if the tree is empty
*/
public T findMin() throws EmptyCollectionException
{
T result = null;
if (isEmpty())
throw new EmptyCollectionException ("binary tree");
else
{
BinaryTreeNode<T> current = root;
while (current.left != null)
current = current.left;
result = current.element;
} //else
return result;
}
/**
* Returns the element with the highest value in the binary
* search tree. It does not remove the node from the binary
* search tree. Throws an EmptyCollectionException if this
* tree is empty.
*
* @return the element with the highest value
* @throws EmptyCollectionException if the tree is empty
*/
public T findMax() throws EmptyCollectionException
{
T result = null;
if (isEmpty())
throw new EmptyCollectionException ("binary tree");
else
{
BinaryTreeNode<T> current = root;
while (current.right != null)
current = current.right;
result = current.element;
} //else
return result;
}
/**
* Returns a reference to the specified target element if it is
* found in the binary tree. Throws a NoSuchElementException if
* the specified target element is not found in this tree.
*
* @param targetElement the element being sought in the binary tree
* @throws ElementNotFoundException if the target element is not found
*/
public T find(T targetElement) throws ElementNotFoundException
{
BinaryTreeNode<T> current = root;
BinaryTreeNode<T> temp = current;
if (!(current.element.equals(targetElement)) && (current.left !=null)&&(((Comparable)current.element).compareTo(targetElement) > 0))
current = findNode( targetElement, current.left);
else if (!(current.element.equals(targetElement)) && (current.right != null))
current = findNode( targetElement, current.right);
if (!(current.element.equals(targetElement)))
throw new ElementNotFoundException ("binarytree");
return current.element;
}
/**
* Returns the left subtree of the root of this tree.
*
* @return a link to the left subtree of the tree
*/
public LinkedBinarySearchTree<T> getLeft()
{
if (root == null)
throw new EmptyCollectionException("getLeft failed - the tree is empty");
LinkedBinarySearchTree <T> result = new LinkedBinarySearchTree<T> ();
result.root = root.getLeft();
return result;
}
/**
* Returns the right subtree of the root of this tree.
*
* @return a link to the right subtree of the tree
*/
public LinkedBinarySearchTree<T> getRight()
{
if (root == null)
throw new EmptyCollectionException("getLeft failed - the tree is empty");
LinkedBinarySearchTree <T> result = new LinkedBinarySearchTree<T> ();
result.root = root.getRight();
return result;
}
/**
* Returns a reference to the specified target element if it is
* found in this tree.
*
* @param targetElement the element being sought in the tree
* @param next the tree node to begin searching on
*/
private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next)
{
BinaryTreeNode<T> current = next;
if (!(next.element.equals(targetElement)) && (next.left !=null) &&(((Comparable)next.element).compareTo(targetElement) > 0))
next = findNode( targetElement, next.left);
else if (!(next.element.equals(targetElement)) && (next.right != null))
next = findNode( targetElement, next.right);
return next;
}
/*balances the binary search tree so that it maintains
* the maximum difference of the path lengths of the
* left and right children as not more than one*/
public void balance() {
//verify if balance factor of the root of the tree is -2
if(getBalanceFactor(root) == -2) {
//verify if balance factor of left child of tree root is 1
if(getBalanceFactor(root.left) == 1)
root = leftRightRotation(root);
else
root = rightRotation(root);
}
//verify if balance factor of tree root is 2
else if(getBalanceFactor(root) == 2) {
//verify if balance factor of right child of tree root is -1
if(getBalanceFactor(root.right) == -1) {
root = rightLeftRotation(root);
}
else
root = leftRotation(root);
}
}
/*performs right rotation and left rotation, then returns new root*/
private BinaryTreeNode<T> rightLeftRotation(BinaryTreeNode<T> current) {
current.right = rightRotation(current.right);
current = leftRotation(current);
return current;
}
/*performs left rotation then right rotation then returns new root*/
private BinaryTreeNode<T> leftRightRotation(BinaryTreeNode<T> current) {
current.left = leftRotation(current.left);
current = rightRotation(current);
return current;
}
/*returns new root after performing right rotation of specified node*/
private BinaryTreeNode<T> rightRotation(BinaryTreeNode<T> current) {
BinaryTreeNode<T> newRoot = current.left;
BinaryTreeNode<T> temp = newRoot.right;
newRoot.right = current;
current.left = temp;
return newRoot;
}
//returns new root after performing left rotation of specified node
private BinaryTreeNode<T> leftRotation(BinaryTreeNode<T> current) {
BinaryTreeNode<T> newRoot = current.right;
BinaryTreeNode<T> temp = newRoot.left;
newRoot.left = current;
current.right = temp;
return newRoot;
}
//returns difference between path lengths of heights of left and right sides of root
private int getBalanceFactor(BinaryTreeNode<T> current) {
int leftHeight = getHeight(current.left);
int rightHeight = getHeight(current.right);
return(rightHeight - leftHeight);
}
//returns the height of the specified node
private int getHeight(BinaryTreeNode<T> newRoot) {
if(newRoot == null)
return 0;
else
return 1 + Math.max(getHeight(newRoot.left), getHeight(newRoot.right));
}
}
Here's my driver program where my utlimate goal is to create the binary search tree from the image above, balance it, and test if it is balanced:
import java.util.*;
import java.io.*;
public class IsHeightBalanced {
public static void main(String[] args) {
LinkedBinarySearchTree<int> tree = new LinkedBinarySearchTree<int>;
tree.addElement(13);
tree.addElement(7);
tree.addElement(15);
tree.addElement(5);
tree.addElement(10);
tree.addElement(3);
}
}
Right now I'm just trying to construct that binary search tree from the picture here and the line
LinkedBinarySearchTree<int> tree = new LinkedBinarySearchTree<int>();
is giving me errors like "insert dimensions to complete reference type"
Why is this giving such an error? Am I on the right track to creating the binary search tree seen in the picture above? Thanks.
Solution
You Cannot Instantiate Generic Types with Primitive Types. for an example
Consider the following parameterized type:
class Pair<K, V> {
private K key;
private V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
// ...
}
When creating a Pair object, you cannot substitute a primitive type for the type parameter K or V:
Pair<int, char> p = new Pair<>(8, 'a'); // compile-time error
You can substitute only non-primitive types for the type parameters K and V:
Pair<Integer, Character> p = new Pair<>(8, 'a');
Note that the Java compiler autoboxes 8 to Integer.valueOf(8) and 'a' to Character('a'):
Pair<Integer, Character> p = new Pair<>(Integer.valueOf(8), new Character('a'));
- Keep numbers which appear in both columns, in J lang
- Differentiation in J
- How to reshape an array with an arbitrary size in one dimension?
- Why is Insert (fold) right associative
- Write 4 : 'x&{.&.;: y' tacitly
- Alignment issue when printing formatted prime numbers in J language
- How can I define a verb in J that applies a different verb alternately to each atom in a list?
- How to get user input in the J programming language
- How to unbox a list of boxed lists of differing lengths in J?
- How can I fix 'noun result was required' error in J?
- In j, how can I define a verb locally in one scope and pass it to a defined adverb?
- Convert boxed array to normal array?
- Read column of CSV file as array
- Replace atom in array of strings
- What does the dyad `=` do to boxed strings?
- Index of minimum element using J
- How can I take the outer product of string vectors in J?
- Building an array of verbs in J
- Reading in multidigit command line parameter
- Amend with bond to new data shows unexpected behaviour
- How to turn a table or matrix into a (flat) list in J
- How to run dissect in J?
- How to define selection using index function in J
- How to exit the J console?
- Find 4-neighbors using J
- Writing custom verbs in J
- How do I negate a selector in J lang?
- How to use arbitrary selector in interchange in J lang?
- different result once square root is added inside tacit
- Sum of arrays with repeated indices