BinarySearchTreeWithRank
Keywords: weiss.nonstandard.BinarySearchTreeWithRank 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 BinarySearchTreeWithRank<AnyType extends java.lang.Comparable<? super AnyType>>

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

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

extends BinarySearchTree<AnyType>

Field Summary

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

Constructor Summary
`BinarySearchTreeWithRank()`

Method Summary
`AnyType` | `findKth(int k)` Find the kth smallest item in the tree.
`protected weiss.nonstandard.BinaryNode<AnyType>` | `findKth(int k, weiss.nonstandard.BinaryNode<AnyType> t)` Internal method to find kth smallest item in a subtree.
`protected weiss.nonstandard.BinaryNode<AnyType>` | `insert(AnyType x, weiss.nonstandard.BinaryNode<AnyType> tt)` Internal method to insert into a subtree.
`static void` | `main(java.lang.String[] args)`
`protected weiss.nonstandard.BinaryNode<AnyType>` | `remove(AnyType x, weiss.nonstandard.BinaryNode<AnyType> tt)` Internal method to remove from a subtree.
`protected weiss.nonstandard.BinaryNode<AnyType>` | `removeMin(weiss.nonstandard.BinaryNode<AnyType> 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 AnyType 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<AnyType> findKth(int k,
                                                            weiss.nonstandard.BinaryNode<AnyType> 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<AnyType> insert(AnyType x,
                                                           weiss.nonstandard.BinaryNode<AnyType> tt)

  Internal method to insert into a subtree.

  Overrides:
    `insert` in class `BinarySearchTree<AnyType extends java.lang.Comparable<? super AnyType>>`
  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<AnyType> remove(AnyType x,
                                                           weiss.nonstandard.BinaryNode<AnyType> tt)

  Internal method to remove from a subtree.

  Overrides:
    `remove` in class `BinarySearchTree<AnyType extends java.lang.Comparable<? super AnyType>>`
  Parameters:
    `x` - the item to remove.
    `tt` - 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> tt)

  Internal method to remove the smallest item from a subtree, adjusting size fields as appropriate.

  Overrides:
    `removeMin` in class `BinarySearchTree<AnyType extends java.lang.Comparable<? super AnyType>>`
  Parameters:
    `tt` - 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: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD