Package gaiasky.util

Class BinarySearchTree<T extends Comparable<T>>

java.lang.Object
gaiasky.util.BinarySearchTree<T>
public class BinarySearchTree<T extends Comparable<T>> extends Object

  • Field Details

  • Constructor Details

    • BinarySearchTree

      public BinarySearchTree()
      Construct the tree.

  • Method Details

    • main

      public static void main(String[] args)

    • insert

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

    • remove

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

    • findMin

      public Comparable<T> findMin()
      Find the smallest item in the tree.
      Returns:
      smallest item or null if empty.

    • findMax

      public Comparable<T> findMax()
      Find the largest item in the tree.
      Returns:
      the largest item or null if empty.

    • find

      public Comparable<T> find(Comparable<T> 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 Comparable<T> findIntervalStart(Comparable<T> x)
      Find the start of the interval where x is in.
      Parameters:
      x - is the item to search the start for.
      Returns:
      object contained in the start of the interval where x is in, or null if x is not contained in any interval.

    • isEmpty

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

    • insert

      protected BinarySearchTree.BinaryNode<T> insert(T x, BinarySearchTree.BinaryNode<T> 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:
      RuntimeException - if x is already present.

    • remove

      protected BinarySearchTree.BinaryNode<T> remove(Comparable<T> x, BinarySearchTree.BinaryNode<T> 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:
      RuntimeException - if x is not found.

    • removeMin

      protected BinarySearchTree.BinaryNode<T> removeMin(BinarySearchTree.BinaryNode<T> t)
      Internal method to remove minimum item from a subtree.
      Parameters:
      t - the node that roots the tree.
      Returns:
      the new root.
      Throws:
      RuntimeException - if x is not found.

    • findMin

      protected BinarySearchTree.BinaryNode<T> findMin(BinarySearchTree.BinaryNode<T> 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.