Package gaiasky.util

Class BinarySearchTree

java.lang.Object
gaiasky.util.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

    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 Details

    • root

      protected gaiasky.util.BinaryNode root
      The tree root.

  • Constructor Details

    • BinarySearchTree

      public BinarySearchTree()
      Construct the tree.

  • Method Details

    • 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)