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