com.mhhe.clrs2e
Class IntervalTree

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

All Implemented Interfaces:

Dictionary

public class IntervalTree

extends RedBlackTree

Implements an interval tree as described in Section 14.3 of Introduction to Algorithms, Second edition.

Nested Class Summary

protected class

IntervalTree.Node Inner class for an interval tree node, extending a red-black tree node with an additional max field.

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

IntervalTree()
Creates an empty interval tree with just a nil, which is the root.

Method Summary

void	delete(java.lang.Object handle) Deletes a node from the tree.
java.lang.Object	insert(java.lang.Comparable data) Inserts an interval into the tree, creating a new node for this interval.
protected void	leftRotate(RedBlackTree.Node handle) Calls RedBlackTree's RedBlackTree.leftRotate(com.mhhe.clrs2e.RedBlackTree.Node) and then fixes the max fields.
protected void	rightRotate(RedBlackTree.Node handle) Calls RedBlackTree's RedBlackTree.rightRotate(com.mhhe.clrs2e.RedBlackTree.Node) and then fixes the max fields.
java.lang.Object	search(java.lang.Comparable k) Finds an interval that overlaps with a given interval.
protected void	treeInsert(IntervalTree.Node x) Inserts a node, updating the max 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, 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

IntervalTree

public IntervalTree()

Creates an empty interval tree with just a nil, which is the root.

Method Detail

leftRotate

protected void leftRotate(RedBlackTree.Node handle)

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

Overrides:

leftRotate in class RedBlackTree

Parameters:

handle - Handle to the node being left rotated.

rightRotate

protected void rightRotate(RedBlackTree.Node handle)

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

Overrides:

rightRotate in class RedBlackTree

Parameters:

handle - Handle to the node being right rotated.

insert

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

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

Specified by:

insert in interface Dictionary

Overrides:

insert in class RedBlackTree

Parameters:

data - The interval being inserted.

Returns:

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

Throws:

java.lang.ClassCastException - if data is not an Interval object.

treeInsert

protected void treeInsert(IntervalTree.Node x)

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

Parameters:

x - 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.

search

public java.lang.Object search(java.lang.Comparable k)

Finds an interval that overlaps with a given interval.

Specified by:

search in interface Dictionary

Overrides:

search in class BinarySearchTree

Parameters:

k - The interval to overlap with.

Returns:

A handle to a node that overlaps with k, or the sentinel nil if no interval in the tree overlaps with k.

Throws:

java.lang.ClassCastException - if k is not an Interval object.