Algorithm: Removing Nodes from OrderedSet<E extends Comparable <E>
Use the following algorithm to remove elements contained in an OrderedSet.
// Remove the node with the given element and return true.
// Return false if the element was not in the BST.
public boolean remove(E element)
Traverse the BST until element is found. Use curr and prev to find the element leaving
prev referring the node you want to remove. It may be the case that curr is null
indicatingthat element was not found. There are four cases to consider:
Case 1 (special case): Not found
Return false
Case 2 (special case): The root is to be removed, and it has no left child.
root = root's right subtreeand return true
Case 3: The node is further down the tree with no left child. Adjust the parent's link
if curr is on the left side of prev,
move parent's left link down to curr's right child
else
curr is on the right side of prev, so move parent's right down to curr's right child
return true
Case 4: curr has a left child.
We can no longer ignore the left subtree. Find the maximum element in the left
subtree and move that element and value to the node referenced by curr. Then
eliminate the node with the maximum element in theleft subtree to avoid duplicates
and return true.
Warmup: Starting with the given elements and structure of the BSTs, draw the elements and structure of each BST after the node has been removed by the given message. Use the algorithm above.
/ \
25 75
\ \
30 80
remove(25) / 10
/ \
5 20
remove(10) / 50
/ \
25 75
\ \
30 90
/ \
80 95
remove(75) / 50
/ \
25 90
/ \
70 99
/ \
60 85
remove(90) / 50
/ \
25 90
/ \
70 99
/ \
60 85
/
80
remove(90) / 50
/ \
25 90
/ \
70 99
/ \
60 85
remove(50)