toys/data-structures/avl-tree/LinkedBinarySearchTree.java

/**
 * LinkedBinarySearchTree implements the BinarySearchTreeADT interface 
 * with links.
 * 
 * Heavilyly modified by me to work with an AVL tree implementation of a dictionary.
 * 
 * @author Dr. Lewis
 * @author Dr. Chase
 * @version 1.0, 8/19/08
 */


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 key/element pair as its root.
    *
    * @param key, element:  the key/element pair that will be the root of the
    *                       new binary search tree
    */
   public LinkedBinarySearchTree (T key, T element) {
      super (key, element);
   }

   /**
    * Adds the specified object to the binary search tree in the
    * appropriate position according to its key value.  Note that
    * equal elements are added to the right.
    *
    * @param key, element:  the key of the element to be added to the binary
    *                       search tree
    */
   public void addElement (Node<T> element) {
      Comparable<T> comparableKey = (Comparable<T>)element.getKey();

      if (isEmpty())
         root = element;
      else {
         Node<T> current = root;
         boolean added = false;

         while (!added) {
            if (comparableKey.compareTo(current.getKey()) < 0) {
               if (current.left == null) {
                  current.setLeft(element);
                  current.getLeft().setParent(current);
                  added = true;
               } else {
                  current = current.left;
               }
            } else {
               if (current.right == null) {
                  current.setRight(element);
                  current.getRight().setParent(current);
                  added = true;
               } else {
                  current = current.right;
               }
            }
         }
      }
      
      count++;
   }
   
   /**
    * 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 an element not found exception occurs
    */
   public T removeElement (T targetElement) throws ElementNotFoundException {
      T result = null;

      if (!isEmpty()) {
         if (((Comparable)targetElement).equals(root.getKey())) {
            result = root.getKey();
            root = replacement(root);
            count--;
         } else {
            Node<T> current, parent = root;
            boolean found = false;

            if (((Comparable)targetElement).compareTo(root.getKey()) < 0)
               current = root.getLeft();
            else
               current = root.getRight();

            while (current != null && !found) {
               if (targetElement.equals(current.getKey())) {
                  found = true;
                  count--;
                  result = current.getKey();
          
                  if (current == parent.getLeft()) {
                     parent.setLeft(replacement(current));
                  } else
                     parent.setRight(replacement(current));
               } else {
                  parent = current;
         
                  if (((Comparable)targetElement).compareTo(current.getKey()) < 0)
                     current = current.getLeft();
                  else
                     current = current.getRight();
               }
            } // End while
            
            if (!found)
               throw new ElementNotFoundException("binary search tree");
         }
      }
      return result;
   }

   /**
    * Removes elements that match the specified target element from 
    * the binary search tree. Throws a ElementNotFoundException if 
    * the sepcified target element is not found in this tree.
    *
    * @param targetElement              the element being sought in the binary \
    *                                   search tree
    * @throws ElementNotFoundException  if an element not found exception occurs
    */
   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
    * EmptyBinarySearchTreeException if this tree is empty. 
    *
    * @return                           a reference to the node with the least 
    *                                   value
    * @throws EmptyCollectionException  if an empty collection exception occurs
    */
   public T removeMin() throws EmptyCollectionException {
      T result = null;

      if (isEmpty())
         throw new EmptyCollectionException ("binary search tree");
      else {
         if (root.left == null) {
            result = root.element;
            root = root.right;
         } else {
            Node<T> parent = root;
            Node<T> current = root.left;
            while (current.left != null) {
               parent = current;
               current = current.left;
            }
            result =  current.element;
            parent.left = current.right;
         }
         count--;
      }
      return result;
   }

   /**
    * Removes the node with the highest value from the binary
    * search tree and returns a reference to its element.  Throws an
    * EmptyBinarySearchTreeException if this tree is empty. 
    *
    * @return  a reference to the node with the highest value
    * @throws EmptyCollectionException  if an empty collection exception occurs
    */
   public T removeMax() throws EmptyCollectionException {
      T result = null;

      if (isEmpty())
         throw new EmptyCollectionException ("binary search tree");
      else {
         if (root.right == null) {
            result = root.element;
            root = root.left;
         } else {
            Node<T> parent = root;
            Node<T> current = root.right;
            while (current.right != null) {
               parent = current;
               current = current.right;
            }
            result =  current.element;
            parent.right = current.left;
         }
         count--;
      }
      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 EmptyBinarySearchTreeException if this tree is empty.
    *
    * @return  the element with the least value
    * @throws EmptyCollectionException  if an empty collection exception occurs
    */
   public T findMin() throws EmptyCollectionException {
      T result = null;

      if (isEmpty())
         throw new EmptyCollectionException ("binary search tree");
      else {
        if (root.left == null)
            result = root.element;
        else {
            Node<T> current = root.left;
            while (current.left != null)
                current = current.left;
            result = current.element;   
        }
      }
      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 EmptyBinarySearchTreeException if this 
    * tree is empty.
    *
    * @return  the element with the highest value
    * @throws EmptyCollectionException  if an empty collection exception occurs
    */
   public T findMax() throws EmptyCollectionException {
      T result = null;

      if (isEmpty())
         throw new EmptyCollectionException ("binary search tree");
      else {
        if (root.right == null)
            result = root.element;
        else {
            Node<T> current = root.right;
            while (current.right != null)
                current = current.right;
            result = current.element;   
        }
      }
      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 sough in the binary tree
    * @throws ElementNotFoundException  if an element not found exception occurs
    */
   public Node<T> find (T targetElement) throws ElementNotFoundException {
      Node<T> current = root;
      
      if (isEmpty()) 
        throw new ElementNotFoundException("binary search tree");
      else {
            boolean found = false;
            while (current != null && !found) {
                if (((Comparable)targetElement).equals(current.getKey()))
                    found = true;
                else if (((Comparable)targetElement).compareTo(current.getKey())<0)
                    current = current.left;
                else
                    current = current.right;
            }
            if (!found) 
                throw new ElementNotFoundException("binary search tree");
      }
      return current;    
   }

   /**
    * 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 being searching on
    */
   private Node<T> findAgain (T targetElement, Node<T> next) {
      Node<T> result = null;
      
      if (isEmpty()) 
        throw new ElementNotFoundException("binary search tree");
      else {
            Node<T> current = next;
            boolean found = false;
            
            while (current != null && !found) {
                if (((Comparable)targetElement).equals(current.element)) {
                    result = current;
                    found = true;
                }
                else if (((Comparable)targetElement).compareTo(current.element)<0)
                    current = current.left;
                else
                    current = current.right;
            }
            if (!found) 
                throw new ElementNotFoundException("binary search tree");
      }
      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 removeed
    * @return      a reference to the replacing node
    */
   protected Node<T> replacement (Node<T> node) {
      Node<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 {
         Node<T> current = node.right;
         Node<T> parent = node;
         
         while (current.left != null) {
            parent = current;
            current = current.left;
         }
         
         if (node.right == current)
            current.left = node.left;
         else {
            parent.left = current.right;
            current.right = node.right;
            current.left = node.left;
         }
         result = current;
      }
      return result;
   }
}