: Class BinarySearchTree

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## weiss.nonstandard
Class BinarySearchTree

    java.lang.Object
      |
      +--weiss.nonstandard.BinarySearchTree

Direct Known Subclasses:
  BinarySearchTreeWithRank

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
`protected weiss.nonstandard.BinaryNode` | `root` The tree root.

Constructor Summary
`BinarySearchTree()` Construct the tree.

Method Summary
`java.lang.Comparable` | `find(java.lang.Comparable x)` Find an item in the tree.
`java.lang.Comparable` | `findMax()` Find the largest item in the tree.
`java.lang.Comparable` | `findMin()` Find the smallest item in the tree.
`protected weiss.nonstandard.BinaryNode` | `findMin(weiss.nonstandard.BinaryNode t)` Internal method to find the smallest item in a subtree.
`void` | `insert(java.lang.Comparable x)` Insert into the tree.
`protected weiss.nonstandard.BinaryNode` | `insert(java.lang.Comparable x, weiss.nonstandard.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 weiss.nonstandard.BinaryNode` | `remove(java.lang.Comparable x, weiss.nonstandard.BinaryNode t)` Internal method to remove from a subtree.
`void` | `removeMin()` Remove minimum item from the tree.
`protected weiss.nonstandard.BinaryNode` | `removeMin(weiss.nonstandard.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 weiss.nonstandard.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:
    `DuplicateItemException` - if x is already present.

### remove

    public void remove(java.lang.Comparable x)

  Remove from the tree..
  Parameters:
    `x` - the item to remove.
  Throws:
    `ItemNotFoundException` - if x is not found.

### removeMin

    public void removeMin()

  Remove minimum item from the tree.
  Throws:
    `ItemNotFoundException` - 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.

### 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 weiss.nonstandard.BinaryNode insert(java.lang.Comparable x,
                                                  weiss.nonstandard.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:
    `DuplicateItemException` - if x is already present.

### remove

    protected weiss.nonstandard.BinaryNode remove(java.lang.Comparable x,
                                                  weiss.nonstandard.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:
    `ItemNotFoundException` - if x is not found.

### removeMin

    protected weiss.nonstandard.BinaryNode removeMin(weiss.nonstandard.BinaryNode t)

  Internal method to remove minimum item from a subtree.
  Parameters:
    `t` - the node that roots the tree.
  Returns:
    the new root.
  Throws:
    `ItemNotFoundException` - if x is not found.

### findMin

    protected weiss.nonstandard.BinaryNode findMin(weiss.nonstandard.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)

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD