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)