Package gaiasky.util

Class BinarySearchTree

  • public class BinarySearchTree
extends java.lang.Object
    Implements an unbalanced binary search tree. Note that all "matching" is based on the compareTo method.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected gaiasky.util.BinaryNode root
      The tree root.

    • Constructor Summary

      Constructors 
      Constructor Description
      BinarySearchTree()
      Construct the tree.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.lang.Comparable find​(java.lang.Comparable x)
      Find an item in the tree.
      java.lang.Comparable findIntervalStart​(java.lang.Comparable x)
      Find the start of the interval where x is in.
      java.lang.Comparable findMax()
      Find the largest item in the tree.
      java.lang.Comparable findMin()
      Find the smallest item in the tree.
      protected gaiasky.util.BinaryNode findMin​(gaiasky.util.BinaryNode t)
      Internal method to find the smallest item in a subtree.
      void insert​(java.lang.Comparable x)
      Insert into the tree.
      protected gaiasky.util.BinaryNode insert​(java.lang.Comparable x, gaiasky.util.BinaryNode t)
      Internal method to insert into a subtree.
      boolean isEmpty()
      Test if the tree is logically empty.
      static void main​(java.lang.String[] args)  
      void makeEmpty()
      Make the tree logically empty.
      void remove​(java.lang.Comparable x)
      Remove from the tree..
      protected gaiasky.util.BinaryNode remove​(java.lang.Comparable x, gaiasky.util.BinaryNode t)
      Internal method to remove from a subtree.
      void removeMin()
      Remove minimum item from the tree.
      protected gaiasky.util.BinaryNode removeMin​(gaiasky.util.BinaryNode t)
      Internal method to remove minimum item from a subtree.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • root

        protected gaiasky.util.BinaryNode root
        The tree root.

    • Constructor Detail

      • BinarySearchTree

        public BinarySearchTree()
        Construct the tree.

    • Method Detail

      • insert

        public void insert​(java.lang.Comparable x)
        Insert into the tree.
        Parameters:
        x - the item to insert.
        Throws:
        java.lang.RuntimeException - if x is already present.

      • remove

        public void remove​(java.lang.Comparable x)
        Remove from the tree..
        Parameters:
        x - the item to remove.
        Throws:
        java.lang.RuntimeException - if x is not found.

      • removeMin

        public void removeMin()
        Remove minimum item from the tree.
        Throws:
        java.lang.RuntimeException - if tree is empty.

      • findMin

        public java.lang.Comparable findMin()
        Find the smallest item in the tree.
        Returns:
        smallest item or null if empty.

      • findMax

        public java.lang.Comparable findMax()
        Find the largest item in the tree.
        Returns:
        the largest item or null if empty.

      • find

        public java.lang.Comparable find​(java.lang.Comparable x)
        Find an item in the tree.
        Parameters:
        x - the item to search for.
        Returns:
        the matching item or null if not found.

      • findIntervalStart

        public java.lang.Comparable findIntervalStart​(java.lang.Comparable x)
        Find the start of the interval where x is in.
        Parameters:
        x - is the item to search the start for.
        Returns:
        node containing the start of the interval where x is in, or null if x is not contained in any interval.

      • makeEmpty

        public void makeEmpty()
        Make the tree logically empty.

      • isEmpty

        public boolean isEmpty()
        Test if the tree is logically empty.
        Returns:
        true if empty, false otherwise.

      • insert

        protected gaiasky.util.BinaryNode insert​(java.lang.Comparable x,
                                         gaiasky.util.BinaryNode t)
        Internal method to insert into a subtree.
        Parameters:
        x - the item to insert.
        t - the node that roots the tree.
        Returns:
        the new root.
        Throws:
        java.lang.RuntimeException - if x is already present.

      • remove

        protected gaiasky.util.BinaryNode remove​(java.lang.Comparable x,
                                         gaiasky.util.BinaryNode t)
        Internal method to remove from a subtree.
        Parameters:
        x - the item to remove.
        t - the node that roots the tree.
        Returns:
        the new root.
        Throws:
        java.lang.RuntimeException - if x is not found.

      • removeMin

        protected gaiasky.util.BinaryNode removeMin​(gaiasky.util.BinaryNode t)
        Internal method to remove minimum item from a subtree.
        Parameters:
        t - the node that roots the tree.
        Returns:
        the new root.
        Throws:
        java.lang.RuntimeException - if x is not found.

      • findMin

        protected gaiasky.util.BinaryNode findMin​(gaiasky.util.BinaryNode t)
        Internal method to find the smallest item in a subtree.
        Parameters:
        t - the node that roots the tree.
        Returns:
        node containing the smallest item.

      • main

        public static void main​(java.lang.String[] args)