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)