: Class BinarySearchTreeWithRank

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 BinarySearchTreeWithRank

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

public class BinarySearchTreeWithRank
extends BinarySearchTree

Implements an unbalanced binary search tree. Note that all "matching" is based on the compareTo method.

Fields inherited from class weiss.nonstandard.BinarySearchTree
`root`

Constructor Summary
`BinarySearchTreeWithRank()`

Method Summary
`java.lang.Comparable` | `findKth(int k)` Find the kth smallest item in the tree.
`protected weiss.nonstandard.BinaryNode` | `findKth(int k, weiss.nonstandard.BinaryNode t)` Internal method to find kth smallest item in a subtree.
`protected weiss.nonstandard.BinaryNode` | `insert(java.lang.Comparable x, weiss.nonstandard.BinaryNode tt)` Internal method to insert into a subtree.
`static void` | `main(java.lang.String[] args)`
`protected weiss.nonstandard.BinaryNode` | `remove(java.lang.Comparable x, weiss.nonstandard.BinaryNode tt)` Internal method to remove from a subtree.
`protected weiss.nonstandard.BinaryNode` | `removeMin(weiss.nonstandard.BinaryNode tt)` Internal method to remove the smallest item from a subtree, adjusting size fields as appropriate.

Methods inherited from class weiss.nonstandard.BinarySearchTree
`find, findMax, findMin, findMin, insert, isEmpty, makeEmpty, remove, removeMin`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### BinarySearchTreeWithRank

    public BinarySearchTreeWithRank()

Method Detail

### findKth

    public java.lang.Comparable findKth(int k)

  Find the kth smallest item in the tree.
  Parameters:
    `k` - the desired rank (1 is the smallest item).
  Returns:
    the kth smallest item in the tree.
  Throws:
    `java.lang.IllegalArgumentException` - if k is less than 1 or more than the size of the subtree.

### findKth

    protected weiss.nonstandard.BinaryNode findKth(int k,
                                                   weiss.nonstandard.BinaryNode t)

  Internal method to find kth smallest item in a subtree.
  Parameters:
    `k` - the desired rank (1 is the smallest item).
  Returns:
    the node containing the kth smallest item in the subtree.
  Throws:
    `java.lang.IllegalArgumentException` - if k is less than 1 or more than the size of the subtree.

### insert

    protected weiss.nonstandard.BinaryNode insert(java.lang.Comparable x,
                                                  weiss.nonstandard.BinaryNode tt)

  Internal method to insert into a subtree.
  Overrides:
    `insert` in class `BinarySearchTree`
  Parameters:
    `x` - the item to insert.
    `tt` - 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 tt)

  Internal method to remove from a subtree.
  Overrides:
    `remove` in class `BinarySearchTree`
  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 tt)

  Internal method to remove the smallest item from a subtree, adjusting size fields as appropriate.
  Overrides:
    `removeMin` in class `BinarySearchTree`
  Parameters:
    `t` - the node that roots the tree.
  Returns:
    the new root.
  Throws:
    `ItemNotFoundExcetion` - if the subtree is empty.

### 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