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>
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 java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
BinarySearchTreeWithRank
public BinarySearchTreeWithRank()
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)