The definition of a binary search tree (BST) is similar to that of a binary tree,
with one important difference:
A binary search tree is either:
1. an empty tree; or
2. a node, called a root, and two children, left and
right, each of which is itself a binary search tree. Each node contains
a value such that the value at the root is greater than the value in any of
the nodes in the left subtree, and less than or equal to the value of any nodes
in the right subtree. (Berman, "Data Structures via C++:Objects by Evolution",
1997.)
An example of a binary search tree appears below.
Note: Alternative definitions for binary search trees handle duplicates in various ways. The definition above specifies that any duplicates must appear in the right subtree. Some definitions specify that any duplicates must appear in the left subtree (all nodes in the left subtree are less than or equal to the root and all nodes in the right subtree are greater than the root). Still others do not allow duplicates at all, specifying that all nodes in the left subtree are less than the root and all nodes in the right subtree are greater than the root. Thus, any BST implementation must specify how (and whether) it handles duplicates.
How would you insert an element in a binary search tree? You know that
for every tree, the values in the right subtree are all greater than or equal
to the value of the root and the values in the left subtree are less than the
value of the root. Thus, if the value to be inserted is less than the
value in the root node, the new value belongs in the left subtree. If
the value to be inserted is greater than or equal to the value in the root node,
the new value belongs in the right subtree. This leads to a nice recursive
method for inserting an element in a binary search tree. If the tree is
empty, insert the value there. Otherwise, if the value is less than the
current node, insert the value in the left subtree. Otherwise, insert
the value in the right subtree. Since we need to compare values in a binary
search tree, all objects inserted in a binary search tree should be Comparable
.
BST
class. A binary search tree is a specialized
binary tree. Technically it is not a subtype of a binary tree, because
one can add any type of object to a binary tree, whereas one should only add
Comparable
objects to a binary search tree. For our purposes,
though, we will consider it OK to create a BST
class as an extension
of the BinaryTree
class. add
method in the BST
class to add
an element to the correct spot in the binary search tree. Remember that
the add
method takes an Object
parameter.
In order to find the correct spot, you will have to cast the Object
parameter to a Comparable
. Document the redefined method
well, including the precondition that the parameter object must be Comparable
.
You will also need to cast the left and right subtrees to BST
in order to get the right add
method in the recursive calls.Debug
class helpful.Implement the following methods:
leftmost
-- Private method that returns the value of the left-most
node in a tree. (Which extreme value in the tree does this method return?)removeLeftmost
-- Private method that removes the left-most
node in a tree and returns the value that was in that node; returns null if
the tree is empty. If the left-most node has a right child, this method
"removes" the left-most node by replacing its data value and left
and right subtree references with those from the root of the right child.
(It must first save a copy of the original data value, though, so that
it can return it.) At some point the root of what used to be the right subtree
will be garbage-collected, since there is no longer a reference to it from
the left-most node. Once you have this method working you can remove
the leftmost
method.remove
-- Takes a Comparable
as a parameter (or
an Object
which you would then cast to Comparable
)
and removes it from the BST. If the node was a leaf, it becomes an empty
tree by setting its data value and left and right subtree references all to
null. If the node has a right subtree, its value should be replaced
with the smallest value in the right subtree (which should be removed from
the subtree). What should the method do if the node whose value is being removed
is not a leaf but has an empty right subtree? This method returns true
if the object was in the tree (and was removed), or false
if
the object was not in the tree.
Is this an appropriate way to delete from a binary search tree? Does it preserve the BST properties of the tree? How does it preserve them, or how are they violated?
The equals
method must be redefined for the BST
class.
Identify any other BinaryTree
methods that must be redefined.
equals
-- takes an Object
as a parameter and
returns true
if it is a BST
and is equal to this
binary search tree; two binary search trees are equal if they contain the
same nodes (and the same number of each node) (NOTE: whenever you redefine
the equals
method, you should also redefine the hashCode
method; in this case, you may redefine it to throw an UnsupportedMethodException
.)BinaryTree
methods in the BST
class
as necessary. isBST
method in the BinaryTreeLab
class that takes a binary tree as a parameter and returns true
if the tree is a binary search tree and false
if it is not a
binary search tree. Remember that an empty binary tree is a valid binary
search tree. You may find it useful to use the ExtremeValueCalculator
class from the Binary Tree Lab. The precondition
for isBST
is that all the objects in the binary tree must be
Comparable
.
Authors: Autumn C. Spaulding autumn@max.c.skzoo.edu
and Alyce Brady abrady@kzoo.edu