com.mhhe.clrs2e
Class BinarySearchTree

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

All Implemented Interfaces:

Dictionary

Direct Known Subclasses:

RedBlackTree

public class BinarySearchTree

extends java.lang.Object

implements Dictionary

Implements the Dictionary interface as a binary search tree from Chapter 12 of Introduction to Algorithms, Second edition. Objects inserted into a binary search tree must implement the Comparable interface.

When extending this class, you must instantiate a new nil of the proper type and override constructors along with the other methods. See RedBlackTree for an example.

Nested Class Summary

protected class	BinarySearchTree.Node Inner class for a node of a binary search tree.
static interface	BinarySearchTree.Visitor Interface for when we visit a node during a walk.

Field Summary

protected BinarySearchTree.Node	nil Sentinel, replaces NIL in the textbook's code.
protected BinarySearchTree.Node	root Root of the binary search tree.

Constructor Summary

BinarySearchTree()
Creates a binary search tree with just a nil, which is the root.

Method Summary

void	delete(java.lang.Object node) Removes a node from the tree.
static java.lang.Comparable	dereference(java.lang.Object node) Returns the data stored in a node.
protected void	inorderWalk(BinarySearchTree.Node x, BinarySearchTree.Visitor visitor) Performs an inorder walk of the the subtree rooted at a node, applying a Visitor to each node in the subtree.
void	inorderWalk(BinarySearchTree.Visitor visitor) Traverses the tree in inorder applying a Visitor to each node.
java.lang.Object	insert(java.lang.Comparable data) Inserts data into the tree, creating a new node for this data.
boolean	isNil(java.lang.Object node) Returns true if the given node is the sentinel nil, false otherwise.
java.lang.Object	iterativeSearch(java.lang.Comparable k) Searches the tree for a node with a given key.
java.lang.Object	maximum() Returns the node with the maximum key in the tree.
java.lang.Object	minimum() Returns the node with the minimum key in the tree.
protected void	postorderWalk(BinarySearchTree.Node x, BinarySearchTree.Visitor visitor) Performs a postorder walk of the the subtree rooted at a node, applying a Visitor to each node in the subtree.
void	postorderWalk(BinarySearchTree.Visitor visitor) Traverses the tree in postorder applying a Visitor to each node.
java.lang.Object	predecessor(java.lang.Object node) Returns the predecessor of a given node in an inorder walk of the tree.
protected void	preorderWalk(BinarySearchTree.Node x, BinarySearchTree.Visitor visitor) Performs a preorder walk of the the subtree rooted at a node, applying a Visitor to each node in the subtree.
void	preorderWalk(BinarySearchTree.Visitor visitor) Traverses the tree in preorder applying a Visitor to each node.
protected java.lang.Object	search(BinarySearchTree.Node x, java.lang.Comparable k) Searches the subtree rooted at a given node for a node with a given key.
java.lang.Object	search(java.lang.Comparable k) Searches the tree for a node with a given key.
protected void	setNil(BinarySearchTree.Node node) Sets the sentinel nil to a given node.
java.lang.Object	successor(java.lang.Object node) Returns the successor of a given node in an inorder walk of the tree.
java.lang.String	toString() Returns a multiline String representation of the tree, representing the depth of each node by two spaces per depth preceding the String representation of the node.
protected void	treeInsert(BinarySearchTree.Node z) Inserts a node into the tree.
protected java.lang.Object	treeMaximum(BinarySearchTree.Node x) Returns the node with the maximum key in the subtree rooted at a node.
protected java.lang.Object	treeMinimum(BinarySearchTree.Node x) Returns the node with the minimum key in the subtree rooted at a node.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected BinarySearchTree.Node root

Root of the binary search tree.

nil

protected BinarySearchTree.Node nil

Sentinel, replaces NIL in the textbook's code.

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Creates a binary search tree with just a nil, which is the root.

Method Detail

setNil

protected void setNil(BinarySearchTree.Node node)

Sets the sentinel nil to a given node.

Parameters:

node - The node that nil is set to.

isNil

public boolean isNil(java.lang.Object node)

Returns true if the given node is the sentinel nil, false otherwise.

Parameters:

node - The node that is being asked about.

inorderWalk

public void inorderWalk(BinarySearchTree.Visitor visitor)

Traverses the tree in inorder applying a Visitor to each node.

Parameters:

visitor - Object implementing Visitor whose visit method is applied to each node in the tree.

inorderWalk

protected void inorderWalk(BinarySearchTree.Node x,
                           BinarySearchTree.Visitor visitor)

Performs an inorder walk of the the subtree rooted at a node, applying a Visitor to each node in the subtree.

Parameters:

x - Root of the subtree.

visitor - Object implementing Visitor whose visit method is applied to each node in the subtree.

preorderWalk

public void preorderWalk(BinarySearchTree.Visitor visitor)

Traverses the tree in preorder applying a Visitor to each node.

Parameters:

visitor - Object implementing Visitor whose visit method is applied to each node in the tree.

preorderWalk

protected void preorderWalk(BinarySearchTree.Node x,
                            BinarySearchTree.Visitor visitor)

Performs a preorder walk of the the subtree rooted at a node, applying a Visitor to each node in the subtree.

Parameters:

x - Root of the subtree.

visitor - Object implementing Visitor whose visit method is applied to each node in the subtree.

postorderWalk

public void postorderWalk(BinarySearchTree.Visitor visitor)

Traverses the tree in postorder applying a Visitor to each node.

Parameters:

visitor - Object implementing Visitor whose visit method is applied to each node in the tree.

postorderWalk

protected void postorderWalk(BinarySearchTree.Node x,
                             BinarySearchTree.Visitor visitor)

Performs a postorder walk of the the subtree rooted at a node, applying a Visitor to each node in the subtree.

Parameters:

x - Root of the subtree.

visitor - Object implementing Visitor whose visit method is applied to each node in the subtree.

toString

public java.lang.String toString()

Returns a multiline String representation of the tree, representing the depth of each node by two spaces per depth preceding the String representation of the node.

Overrides:

toString in class java.lang.Object

search

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

Searches the tree for a node with a given key. Works recursively.

Specified by:

search in interface Dictionary

Parameters:

k - The key being searched for.

Returns:

A reference to a Node object with key k if such a node exists, or a reference to the sentinel nil if no node has key k. The Node class is opaque to methods outside this class.

search

protected java.lang.Object search(BinarySearchTree.Node x,
                                  java.lang.Comparable k)

Searches the subtree rooted at a given node for a node with a given key. Works recursively.

Parameters:

x - Root of the subtree.

k - The key being searched for.

Returns:

A reference to a Node object with key k if such a node exists, or a reference to the sentinel nil if no node has key k. The Node class is opaque to methods outside this class.

iterativeSearch

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

Searches the tree for a node with a given key. Works iteratively.

Parameters:

k - The key being searched for.

Returns:

A reference to a Node object with key k if such a node exists, or a reference to the sentinel nil if no node has key k. The Node class is opaque to methods outside this class.

minimum

public java.lang.Object minimum()

Returns the node with the minimum key in the tree.

Returns:

A Node object with the minimum key in the tree, or the sentinel nil if the tree is empty.

treeMinimum

protected java.lang.Object treeMinimum(BinarySearchTree.Node x)

Returns the node with the minimum key in the subtree rooted at a node.

Parameters:

x - Root of the subtree.

Returns:

A Node object with the minimum key in the tree, or the sentinel nil if the tree is empty.

maximum

public java.lang.Object maximum()

Returns the node with the maximum key in the tree.

Returns:

A Node object with the maximum key in the tree, or the sentinel nil if the tree is empty.

treeMaximum

protected java.lang.Object treeMaximum(BinarySearchTree.Node x)

Returns the node with the maximum key in the subtree rooted at a node.

Parameters:

x - Root of the subtree.

Returns:

A Node object with the maximum key in the tree, or the sentinel nil if the tree is empty.

successor

public java.lang.Object successor(java.lang.Object node)

Returns the successor of a given node in an inorder walk of the tree.

Parameters:

node - The node whose successor is returned.

Returns:

If node has a successor, it is returned. Otherwise, return the sentinel nil.

predecessor

public java.lang.Object predecessor(java.lang.Object node)

Returns the predecessor of a given node in an inorder walk of the tree.

Parameters:

node - The node whose predecessor is returned.

Returns:

If node has a predecessor, it is returned. Otherwise, return the sentinel nil.

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

Parameters:

data - Data to be inserted into the tree.

Returns:

A reference to the Node object created. The Node class is opaque to methods outside this class.

treeInsert

protected void treeInsert(BinarySearchTree.Node z)

Inserts a node into the tree.

Parameters:

z - The node to insert.

delete

public void delete(java.lang.Object node)

Removes a node from the tree.

Specified by:

delete in interface Dictionary

Parameters:

node - The node to be removed.

Throws:

DeleteSentinelException - if there is an attempt to delete the sentinel nil.

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

dereference

public static java.lang.Comparable dereference(java.lang.Object node)

Returns the data stored in a node.

Parameters:

node - The node whose data is returned.

Throws:

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