Welcome to Lesson 12!Learning ObjectivesBy the end of this class, you should know...- How do you implement the recursive BST operations
- search
- minimum
- remove
1. Searching a BST- Searching a BST is an almost identical process to inserting a new node to the tree.
- Let's review BST insert using an example, and then compare it to BST search:
- We can thus adapt the insert pseudocode for search.
- However, search returns a boolean to indicate whether the value was found, whereas insert is a void method.
1. Base Case: the value is equal to the node's data 1a. return true 2. Check if the value is smaller than the node's data. 2a. If this is true 2aa. If node's leftchild is null 2aaa. return false. The value was not found 2b. If the node's leftchild is not null 2bb. recursively call the search helper method passing it node's leftchild and value 3. Otherwise 3a. Check if the node's rightchild is null 3aa. If this is true, return false. The value was not found. 3b. If the node's rightchild is not null 3bb. recursively call the search helper method passing it node's rightchild and value 1.1. Writing the BST Search Method- Below is the code for the public search wrapper method
if(root == null) { return false; } else { return search(data, root); } } - It is your job to write the helper method for search in your upcoming Lab.
2. Finding the Minimum Value in a BST- The purpose of the minimum method is to find the minimum value in the tree.
- Where is the minimum value always located in a Binary Search Tree?
- If you are uncertain, look at an example of BST to see where the minimum is located.
- To find the minimum, all we need to do is to scroll through the nodes in the tree to the proper location.
Pseudocode for private minimum helper (Node node)- If the node's leftchild is not null
- return recursive call to minimum, passing it node's leftchild
- Otherwise
- Return the node's data
3. Removing a Value from a BST- Remove is perhaps the most challenging BST algorithm to implement.
- Like search, insert, and the tree traversals it is also recursive.
- Remove works by first searching for a particular value in a BST.
- Once the node has been located, it can then be removed.
- However, complication comes from the fact that we could encounter several different cases:
**Case 1:**The node we wish to remove if a leaf node**<-- easy case****Case 2:**The node we wish to remove has only one child**<-- medium case****Case 3:**The node we wish to remove has two children**<-- hard case**- When deleting nodes in each of these cases, you must be mindful to preserve the BST property.
- Let's look at each of these possibilities in the diagram below:
- Therefore, when writing remove, we need to handle all three cases.
Pseudocode for remove helper(node, value)1. If node is null 1. return node 2. Otherwise, if value < the node's data 1.set node's leftchild equal to the recursive call of remove helper on node's leftchild 3. Otherwise, if value > the node's data 1. set node's rightchild equal to the recursive call of remove helper on node's rightchild 4. Otherwise, 1. If node is a leaf node 1. Set node to null 2. Otherwise if node has a leftchild but no rightchild 1. set the leftchild to be the node 3. Otherwise if node has a rightchild but no leftchild 1. set the rightchild to be the node 4. Otherwise 1. Search for the minimum value in the right subtree of the node 2. Set the node's data to be the minimum value in the node's right subtree 3. Set node's rightchild equal to the recursive call of remove helper, passing it node's rightchild
and the minimum data of node's right subtree (i.e. delete the duplicate value in
the right subtree) 5. return the node 3.1 Writing BST Remove- Below is the signature for the public remove method (wrapper).
- Note that the private minimum method can be used as a helper inside of the private remove method.
/** * Removes a value from the BST* @param data the value to remove * @precondition !isEmpty() * @precondition the data is located in the tree * @throws NoSuchElementException when the * precondition is violated */ public void remove(T data) throws NoSuchElementException{}
- Redraw the below BSTs after the indicated value has been removed.
- Make sure to draw any intermediary steps.
BST 1: Remove 18BST 2: RemoveBST 3: Remove 15- How to trace the removal processing using the given remove pseudocode:
- The first 3 steps in the pseudocode locate the value to remove inside the tree, and reset connections:
1. If node is null //you have gone past the leaf, therefore value not in tree1. return node //or return null2. Otherwise, if value < the node's data //search to the left1.set node's leftchild equal to the recursive call of remove helper on node's leftchild //reset left connection3. Otherwise, if value > the node's data //search to the right1. set node's rightchild equal to the recursive call of remove helper on node's rightchild //reset right connection4. Otherwise, //you found it! Now time to remove!- Step 4 handles removal according to the three cases (easy, medium and hard).
1. If node is a leaf node //easy1. Set node to null 2. Otherwise if node has a leftchild but no rightchild //medium 11. set the leftchild to be the node 3. Otherwise if node has a rightchild but no leftchild //medium 21. set the rightchild to be the node 4. Otherwise //hard1. Search for the minimum value in the right subtree of the node 2. Set the node's data to be the minimum value in the node's right subtree 3. Set node's rightchild equal to the recursive call of remove helper, passing it node's rightchild
and the minimum data of node's right subtree (i.e. delete the duplicate value in
the right subtree)- Note that this method returns a node - Why?
- The method recursively re-sets connections within the tree
- Unlike search or insert - where we are at the level of the parent looking down to a child - when removing, we are at the level of the child node.
- With no pointers from child back to parent, we must use recursion to help rebuild the tree after removing an element.
- The connections get re-built from the node that was removed all the way back up to the root node.
Wrap Up- Answer the practice exam questions on Canvas for today's lesson
~Have a Great Weekend!~ |