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: the definition above is not exactly the same as the version in Lewis & Chase. 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, like the one in our textbok, 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
BSTclass. 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
Comparableobjects to a binary search tree. For our purposes, though, we will consider it OK to create a
BSTclass as an extension of the
addmethod in the
BSTclass to add an element to the correct spot in the binary search tree. Remember that the
addmethod takes an
Objectparameter. In order to find the correct spot, you will have to cast the
Objectparameter to a
Comparable. Document the redefined method well, including the precondition that the parameter object must be
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
remove-- Takes a
Comparableas a parameter (or an
Objectwhich 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 non-empty 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?
trueif the object was in the tree (and was removed), or
falseif 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?
equals method must be redefined for the
Identify any other
BinaryTree methods that must be redefined.
equals-- takes an
Objectas a parameter and returns
trueif it is a
BSTand 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
equalsmethod, you should also redefine the
hashCodemethod; in this case, you may redefine it to throw an
BinaryTreemethods in the
BSTclass as necessary.
isBSTmethod in the
BinaryTreeLabclass that takes a binary tree as a parameter and returns
trueif the tree is a binary search tree and
falseif 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
ExtremeValueCalculatorclass from the Binary Tree Lab. The precondition for
isBSTis that all the objects in the binary tree must be
Authors: Autumn C. Spaulding firstname.lastname@example.org
and Alyce Brady email@example.com