    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