All Packages Class Hierarchy This Package Previous Next Index
Class DataStructures.BinarySearchTreeWithRank
java.lang.Object

+DataStructures.BinarySearchTree

+DataStructures.BinarySearchTreeWithRank
 public class BinarySearchTreeWithRank
 extends BinarySearchTree
Implements a binary search tree with a findKth method.
Note that all "matching" is based on the compares method.

BinarySearchTreeWithRank()


findKth(int)
 Find the kth smallest item in the tree.

findKth(int, BinaryNode)
 Internal method to find kth smallest item in a subtree.

insert(Comparable, BinaryNode)
 Internal method to insert into a subtree, adjusting
Size fields as appropriate.

main(String[])


remove(Comparable, BinaryNode)
 Internal method to remove from a subtree, adjusting
Size fields as appropriate.

removeMin(BinaryNode)
 Internal method to remove the smallest item from a subtree,
adjusting Size fields as appropriate.
BinarySearchTreeWithRank
public BinarySearchTreeWithRank()
findKth
public Comparable findKth(int k) throws ItemNotFound
 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:
ItemNotFound
 if k is less
than 1 or more than the size of the tree.
insert
protected BinaryNode insert(Comparable x,
BinaryNode t) throws DuplicateItem
 Internal method to insert into a subtree, adjusting
Size fields as appropriate.
 Parameters:
 x  the item to insert.
 t  the node that roots the tree.
 Returns:
 the new root.
 Throws:
DuplicateItem
 if item that
matches x is already in the subtree rooted at t.
 Overrides:
 insert in class BinarySearchTree
remove
protected BinaryNode remove(Comparable x,
BinaryNode t) throws ItemNotFound
 Internal method to remove from a subtree, adjusting
Size fields as appropriate.
 Parameters:
 x  the item to remove.
 t  the node that roots the tree.
 Returns:
 the new root.
 Throws:
ItemNotFound
 no item that
matches x is in the subtree rooted at t.
 Overrides:
 remove in class BinarySearchTree
removeMin
protected BinaryNode removeMin(BinaryNode t) throws ItemNotFound
 Internal method to remove the smallest item from a subtree,
adjusting Size fields as appropriate.
 Parameters:
 t  the node that roots the tree.
 Returns:
 the new root.
 Throws:
ItemNotFound
 the subtree is empty.
 Overrides:
 removeMin in class BinarySearchTree
findKth
protected BinaryNode findKth(int k,
BinaryNode t) throws ItemNotFound
 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:
ItemNotFound
 if k is less
than 1 or more than the size of the subtree.
main
public static void main(String[] args)
All Packages Class Hierarchy This Package Previous Next Index