BinarySearchTree
Keywords: weiss.nonstandard.BinarySearchTree class

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

## weiss.nonstandard
Class BinarySearchTree<AnyType extends java.lang.Comparable<? super AnyType>>

    java.lang.Object
      weiss.nonstandard.BinarySearchTree<AnyType>

Direct Known Subclasses:
  BinarySearchTreeWithRank

    public class BinarySearchTree<AnyType extends java.lang.Comparable<? super AnyType>>

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<AnyType>` | `root` The tree root.

Constructor Summary
`BinarySearchTree()` Construct the tree.

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

  The tree root.

Constructor Detail

### BinarySearchTree

    public BinarySearchTree()

  Construct the tree.

Method Detail

### insert

    public void insert(AnyType x)

  Insert into the tree.

  Parameters:
    `x` - the item to insert.
  Throws:
    `DuplicateItemException` - if x is already present.

### remove

    public void remove(AnyType 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 AnyType findMin()

  Find the smallest item in the tree.

  Returns:
    smallest item or null if empty.

### findMax

    public AnyType findMax()

  Find the largest item in the tree.

  Returns:
    the largest item or null if empty.

### find

    public AnyType find(AnyType 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<AnyType> insert(AnyType x,
                                                           weiss.nonstandard.BinaryNode<AnyType> 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<AnyType> remove(AnyType x,
                                                           weiss.nonstandard.BinaryNode<AnyType> 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<AnyType> removeMin(weiss.nonstandard.BinaryNode<AnyType> 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 t is empty.

### findMin

    protected weiss.nonstandard.BinaryNode<AnyType> findMin(weiss.nonstandard.BinaryNode<AnyType> 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: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD