com.mhhe.clrs2e
Class OrderStatisticTree

java.lang.Object
  |
  +--com.mhhe.clrs2e.BinarySearchTree
        |
        +--com.mhhe.clrs2e.RedBlackTree
              |
              +--com.mhhe.clrs2e.OrderStatisticTree

All Implemented Interfaces:

Dictionary

public class OrderStatisticTree

extends RedBlackTree

Implements an order-statistic tree as described in Section 14.1 of Introduction to Algorithms, Second edition.

Nested Class Summary

protected class	OrderStatisticTree.Node Inner class for an order-statistic tree node, extending a red-black tree node with an additional size field.
static class	OrderStatisticTree.SizeException Exception thrown by actualSize() if the size of the subtree does not agree with the size field of the subtree's root node.

Nested classes inherited from class com.mhhe.clrs2e.RedBlackTree

RedBlackTree.BlackHeightException

Nested classes inherited from class com.mhhe.clrs2e.BinarySearchTree

BinarySearchTree.Visitor

Field Summary

Fields inherited from class com.mhhe.clrs2e.RedBlackTree

BLACK, RED

Fields inherited from class com.mhhe.clrs2e.BinarySearchTree

nil, root

Constructor Summary

OrderStatisticTree()
Creates an order-statistic tree with just a nil, which is the root.

Method Summary

int	actualSize() Returns the actual size of the entire tree.
int	actualSize(java.lang.Object handle) Returns the actual size of the subtree rooted at a node.
void	delete(java.lang.Object handle) Deletes a node from the tree.
java.lang.Object	insert(java.lang.Comparable data) Inserts data into the tree, creating a new node for this data.
protected void	leftRotate(RedBlackTree.Node x) Calls RedBlackTree's RedBlackTree.leftRotate(com.mhhe.clrs2e.RedBlackTree.Node) and then fixes the size fields.
int	rank(java.lang.Object handle) Determines, for a given node, in which ordinal position the node would appear in an inorder walk of the tree.
protected void	rightRotate(RedBlackTree.Node x) Calls RedBlackTree's RedBlackTree.rightRotate(com.mhhe.clrs2e.RedBlackTree.Node) and then fixes the size fields.
protected java.lang.Object	select(BinarySearchTree.Node x, int i) Finds the node in a subtree that is at a given ordinal position in an inorder walk of the subtree.
java.lang.Object	select(int i) Finds the node in the tree that is at a given ordinal position in an inorder walk of the tree.
protected void	setNil(OrderStatisticTree.Node node) Set the sentinel nil to a given node.
protected void	treeInsert(OrderStatisticTree.Node z) Inserts a node, updating the size fields of its ancestors before the superclass's insertNode is called.

Methods inherited from class com.mhhe.clrs2e.RedBlackTree

blackHeight, blackHeight, deleteFixup, insertFixup, setNil, treeInsert

Methods inherited from class com.mhhe.clrs2e.BinarySearchTree

dereference, inorderWalk, inorderWalk, isNil, iterativeSearch, maximum, minimum, postorderWalk, postorderWalk, predecessor, preorderWalk, preorderWalk, search, search, setNil, successor, toString, treeInsert, treeMaximum, treeMinimum

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

OrderStatisticTree

public OrderStatisticTree()

Creates an order-statistic tree with just a nil, which is the root.

Method Detail

setNil

protected void setNil(OrderStatisticTree.Node node)

Set the sentinel nil to a given node.

Parameters:

node - The node that nil is set to.

select

public java.lang.Object select(int i)

Finds the node in the tree that is at a given ordinal position in an inorder walk of the tree.

Parameters:

i - The ordinal position.

Returns:

An opaque handle to the node that is ith in an inorder walk of the tree.

select

protected java.lang.Object select(BinarySearchTree.Node x,
                                  int i)

Finds the node in a subtree that is at a given ordinal position in an inorder walk of the subtree.

Parameters:

x - Root of the subtree.

i - The ordinal position.

Returns:

An opaque handle to the node that is ith in an inorder walk of the subtree.

rank

public int rank(java.lang.Object handle)

Determines, for a given node, in which ordinal position the node would appear in an inorder walk of the tree.

Parameters:

handle - Handle to the node.

Returns:

The ordinal position of the node in an inorder walk of the tree.

Throws:

java.lang.ClassCastException - if Handle does not reference a Node object.

leftRotate

protected void leftRotate(RedBlackTree.Node x)

Calls RedBlackTree's RedBlackTree.leftRotate(com.mhhe.clrs2e.RedBlackTree.Node) and then fixes the size fields.

Overrides:

leftRotate in class RedBlackTree

Parameters:

x - handle The node being left rotated.

rightRotate

protected void rightRotate(RedBlackTree.Node x)

Calls RedBlackTree's RedBlackTree.rightRotate(com.mhhe.clrs2e.RedBlackTree.Node) and then fixes the size fields.

Overrides:

rightRotate in class RedBlackTree

Parameters:

x - handle The node being right rotated.

insert

public java.lang.Object insert(java.lang.Comparable data)

Inserts data into the tree, creating a new node for this data.

Specified by:

insert in interface Dictionary

Overrides:

insert in class RedBlackTree

Parameters:

data - The data being inserted.

Returns:

A handle to the Node that is created. Node is opaque to methods outside this class.

treeInsert

protected void treeInsert(OrderStatisticTree.Node z)

Inserts a node, updating the size fields of its ancestors before the superclass's insertNode is called.

Parameters:

z - The node to insert.

delete

public void delete(java.lang.Object handle)

Deletes a node from the tree.

Specified by:

delete in interface Dictionary

Overrides:

delete in class RedBlackTree

Parameters:

handle - Handle to the node being deleted.

Throws:

java.lang.ClassCastException - if handle is not a Node object.

actualSize

public int actualSize()
               throws OrderStatisticTree.SizeException

Returns the actual size of the entire tree.

Throws:

OrderStatisticTree.SizeException - if any size instance variable is incorrect.

actualSize

public int actualSize(java.lang.Object handle)
               throws OrderStatisticTree.SizeException

Returns the actual size of the subtree rooted at a node.

Parameters:

handle - Handle to the node that is the root of the subtree.

Throws:

OrderStatisticTree.SizeException - if any size instance variable is incorrect.

java.lang.ClassCastException - if handle is not a Node object.