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