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