CP164 Final: Recursive Removal
Recursive Removal
The search portion of node deletion is very similar to the search portion of node insertion.
There are two base cases: when the key is found in the tree, or when the search reaches the
bottom of the tree and no match is found. There are two general cases when the value is
less than or greater than the value in the node being searched. If a node is found and
deleted, all of the nodes above the deleted node must have their heights updated.
The _delete_node method performs the actual node deletion according to the cases
discussed above.
(Note that in code presented in this course all changes are performed on the nodes, rather
than on the values in the nodes. A alternate approach would be to move values between
nodes in order to preserve the BST structure. We will not be using this approach in this
course.)
class BST:
def remove(self, key):
"""
-------------------------------------------------------
Removes a node with a value matching key from the bst.
Returns the value matched.
Use: value = bst.remove(key)
-------------------------------------------------------
Preconditions:
key - data to search for (?)
Postconditions:
returns
value - value matching key if found, otherwise returns
None. Update structure of bst as required.
-------------------------------------------------------
"""
assert self._root is not None, "Cannot remove from an empty BST"
self._root, value = self._remove_aux(self._root, key)
return value
def _remove_aux(self, node, key):
"""
-------------------------------------------------------
Attempts to find a value matching key in a BST node. Deletes
the node if found and returns the sub-tree root.
Private recursive operation called only by remove.
Use: node, value = self._remove_aux(node, key)
-------------------------------------------------------
Preconditions:
node - a bst node to search for key (_BSTNode)
key - data to search for (?)
Postconditions:
returns
node - the current node or its replacement (_BSTNode)
value - value in node containing key, None otherwise.
-------------------------------------------------------
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
The search portion of node deletion is very similar to the search portion of node insertion. There are two base cases: when the key is found in the tree, or when the search reaches the bottom of the tree and no match is found. There are two general cases when the value is less than or greater than the value in the node being searched. If a node is found and deleted, all of the nodes above the deleted node must have their heights updated. The _delete_node method performs the actual node deletion according to the cases discussed above. (note that in code presented in this course all changes are performed on the nodes, rather than on the values in the nodes. A alternate approach would be to move values between nodes in order to preserve the bst structure. We will not be using this approach in this course. ) class bst: def remove(self, key):
