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.

Constructor Index

o BinarySearchTreeWithRank()

Method Index

o findKth(int)
Find the kth smallest item in the tree.
o findKth(int, BinaryNode)
Internal method to find kth smallest item in a subtree.
o insert(Comparable, BinaryNode)
Internal method to insert into a subtree, adjusting Size fields as appropriate.
o main(String[])
o remove(Comparable, BinaryNode)
Internal method to remove from a subtree, adjusting Size fields as appropriate.
o removeMin(BinaryNode)
Internal method to remove the smallest item from a subtree, adjusting Size fields as appropriate.

Constructors

o BinarySearchTreeWithRank 
  public BinarySearchTreeWithRank()

Methods

o 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.
o 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
o 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
o 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
o 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.
o main 
  public static void main(String args[])

All Packages  Class Hierarchy  This Package  Previous  Next  Index