Binary Search Trees MINI-LAB

By Autumn C. Spaulding with Alyce Brady

Definition of a Binary Search Tree

The recursive 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:

• An empty tree; or
• A node, called a root, containing the data 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. This is known as the Binary Tree Invariant.

An example of a binary search tree appears to the right.

K_BST Class

A binary search tree is a specific type of binary tree; in other words, a binary search tree IS-A binary tree. In this case, the K_BST class is another subclass of the K_RecBinaryTree class. It inherits many binary tree methods, but two methods it must override to achieve and maintain BST behavior are the add and remove methods.

• Download the incomplete K_BST.java and BSTTester.java classes. K_BST.java is a skeleton version of your eventual binary search tree class. BSTTester.java is a test driver similar to BinaryTreeTester.java, but to test binary search trees.
• Read over the class documentation, the class declaration, and the initial comments and constructor in K_BST. Note that the syntax for defining K_BST as a subclass of K_RecBinaryTree includes the restriction that objects in a BST must be of a type T that extends Comparable.

Inserting into a Binary Search Tree

How would you insert an element in a binary search tree? You know that for every tree, the values in the left subtree are less than the value of the root and the values in the right subtree are all greater than or equal to 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. In other words, the type T for the objects in a binary search tree must extend Comparable.

• Redefine the add method in the K_BST class to add an element to the correct spot in the binary search tree.
• Before testing your method, read it over carefully and develop drawings that illustrate the various steps in the algorithm. Recursion can be tricky, but illustrating the process can be useful. Then test the method. You may find the Debug class helpful.

Deleting from a Binary Search Tree

Implement the following methods:

• returnLeftmost -- Private method that returns the data value from 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 returnLeftmost method.
  

• remove -- Takes a value of type T as a parameter and removes it from the BST. First it steps through the tree recursively until it finds the node to remove. Note that, unlike many of the recursive functions in K_RecBinaryTree, you don't have to traverse both the left and right children of any given node to see if the value to remove is there; if it isn't the current node, you will always know whether it would be in the left or right child.

  Once you find the node to remove, you need to determine whether it was a leaf, so you can just remove it (replace its data value and left/right subtrees with null, making it an empty tree), or whether you need to replace it with something else. If there are some values in the right subtree (the node has a non-empty right subtree), then we can replace the value being removed with the smallest value in the right subtree, since that will preserve the BST invariant. This also means deleting the smallest value in the right subtree. If there is nothing in the right subtree (but we already determined this node is not a leaf), then we can just slide the data and links up from the left subtree to the current node. This method returns true if the object was in the tree (and was removed), or false if the object was not in the tree.

Clean and Refactor

Follow this link to clean and refactor your comments and code.

Submission

Submit your completed program through Kit, under Binary Tree.

Have fun! And if you have any questions remember I am available through email, Teams, and my office hours. And don't forget the Collaboration Center, which is a great place to work and ask questions too!