cse1030.recursion

Class BinarySearchTree<E extends Comparable<? super E>>

java.lang.Object

cse1030.recursion.BinarySearchTree<E>

Type Parameters:

E - the type of the data stored in the nodes of the binary search tree

public class BinarySearchTree<E extends Comparable<? super E>>
extends Object

A binary search tree class.

A binary search tree is a binary tree where values are stored in the tree according to three rules:

1. values in the left subtree are less than values in the root node
2. values in the right subtree are greater than or equal to values in the root node
3. rules 1 and 2 apply recursively to every subtree

Author:

CSE1030Z

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BinarySearchTree.Node<E> A class that represents nodes in the binary search tree.

Field Summary

Fields

Modifier and Type	Field and Description
private BinarySearchTree.Node<E>	root The root node of the binary search tree.

Constructor Summary

Constructors

Constructor and Description
BinarySearchTree() Create an empty binary search tree.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(E element) Add an element to the tree.
private static <E extends Comparable<? super E>> void	add(E element, BinarySearchTree.Node<E> subtreeRoot) Add an element to the subtree rooted at subtreeRoot.
boolean	contains(E element) Returns true if the tree contains the given element, false otherwise.
private static <E extends Comparable<? super E>> boolean	contains(E element, BinarySearchTree.Node<E> subtreeRoot) Returns true if the subtree rooted at subtreeRoot contains the given element, false otherwise.
BinarySearchTree.Node<E>	getRoot() Get the root node of the tree.
static <E> BinarySearchTree.Node<E>	maximumInSubtree(BinarySearchTree.Node<E> subtreeRoot) Find the node in a subtree that has the largest data element.
static <E> BinarySearchTree.Node<E>	minimumInSubtree(BinarySearchTree.Node<E> subtreeRoot) Find the node in a subtree that has the smallest data element.
static <E> BinarySearchTree.Node<E>	predecessorInSubtree(BinarySearchTree.Node<E> subtreeRoot) Find the node in a subtree that is the predecessor to the root of the subtree.
static <E> BinarySearchTree.Node<E>	successorInSubtree(BinarySearchTree.Node<E> subtreeRoot) Find the node in a subtree that is the successor to the root of the subtree.
String	toString() Return a string representation of the tree.
private static <E> String	toString(BinarySearchTree.Node<E> subtreeRoot) Return a string representation of the subtree rooted at subtreeRoot.

Methods inherited from class java.lang.Object

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

Field Detail

root

private BinarySearchTree.Node<E extends Comparable<? super E>> root

The root node of the binary search tree.

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Create an empty binary search tree.

Method Detail

add

public void add(E element)

Add an element to the tree. The element is inserted into the tree in a position that preserves the definition of a binary search tree.

Parameters:

element - the element to add to the tree

add

private static <E extends Comparable<? super E>> void add(E element,
                                         BinarySearchTree.Node<E> subtreeRoot)

Add an element to the subtree rooted at subtreeRoot. The element is inserted into the tree in a position that preserves the definition of a binary search tree.

Parameters:

element - the element to add to the subtree

subtreeRoot - the root of the subtree

contains

public boolean contains(E element)

Returns true if the tree contains the given element, false otherwise.

Parameters:

element - the element to search for

Returns:

true if the tree contains the given element, false otherwise

contains

private static <E extends Comparable<? super E>> boolean contains(E element,
                                                 BinarySearchTree.Node<E> subtreeRoot)

Returns true if the subtree rooted at subtreeRoot contains the given element, false otherwise.

Parameters:

element - the element to search for

subtreeRoot - the root of the subtree

Returns:

true if the subtree rooted at subtreeRoot contains the given element, false otherwise

toString

public String toString()

Return a string representation of the tree.

The string is made up of the elements stored in the tree separated by commas; the entire list of elements is enclosed in braces. The elements are in ascending sorted order.

Overrides:

toString in class Object

Returns:

a string representation of the tree

See Also:

Object.toString()

toString

private static <E> String toString(BinarySearchTree.Node<E> subtreeRoot)

Return a string representation of the subtree rooted at subtreeRoot.

The string is made up of the elements stored in the tree separated by commas where the elements are in ascending sorted order.

The string is generated using inorder processing of the subtree:

1. the string corresponding to subtreeRoot.left is computed
2. the string corresponding to subtreeRoot.data is computed
3. the string corresponding to subtreeRoot.right is computed

The returned string is the concatenation of the three strings computed by the inorder processing of the subtree.

Parameters:

subtreeRoot - the root of the subtree

Returns:

the string representation of the subtree

getRoot

public BinarySearchTree.Node<E> getRoot()

Get the root node of the tree. For testing purposes only.

Returns:

the root node of the tree.

minimumInSubtree

public static <E> BinarySearchTree.Node<E> minimumInSubtree(BinarySearchTree.Node<E> subtreeRoot)

Find the node in a subtree that has the smallest data element.

Parameters:

subtreeRoot - the root of the subtree

Returns:

the node in the subtree that has the smallest data element.

maximumInSubtree

public static <E> BinarySearchTree.Node<E> maximumInSubtree(BinarySearchTree.Node<E> subtreeRoot)

Find the node in a subtree that has the largest data element.

Parameters:

subtreeRoot - the root of the subtree

Returns:

the node in the subtree that has the largest data element.

predecessorInSubtree

public static <E> BinarySearchTree.Node<E> predecessorInSubtree(BinarySearchTree.Node<E> subtreeRoot)

Find the node in a subtree that is the predecessor to the root of the subtree. If the predecessor node exists, then it is the node that has the largest data element in the left subtree of subtreeRoot.

Parameters:

subtreeRoot - the root of the subtree

Returns:

the node in a subtree that is the predecessor to the root of the subtree, or null if the root of the subtree has no predecessor

successorInSubtree

public static <E> BinarySearchTree.Node<E> successorInSubtree(BinarySearchTree.Node<E> subtreeRoot)

Find the node in a subtree that is the successor to the root of the subtree. If the successor node exists, then it is the node that has the smallest data element in the right subtree of subtreeRoot.

Parameters:

subtreeRoot - the root of the subtree

Returns:

the node in a subtree that is the successor to the root of the subtree, or null if the root of the subtree has no successor