Delete in Binary Search Trees
(Note: Remember that in a BST, the left child is smaller than the node, and the right child is bigger than the node)
- If the node is not a node, then there is nothing to do
- If data is less than the data in the node, go down the left (which has smaller values)
- If data is more than the data in the node, go down the right (which has bigger values)
- If node has fewer than two children, then return the existing one (which essentially brings down the only child if the deleted node has only got one child)
- Otherwise, if both children exist, replace the data with the data in the largest child in the left subtree and recursively work on the data from the left node, and finally return that node
On this final step, it is important to notice that, when deleting an element from a BST, you need to pull the item from the left child since the right child is always bigger than the node. To make this clear, we could follow this example:
Let's delete the five (5). Then we need to to grab a value to replace the five, and it only makes sense to take the largest child from the left. In this case it would be the four (4). The four is still smaller than the rest of the right children, and bigger than the left children. Then we would get the following:
This code was taken from class, so credit to whoever wrote it! It is shown here to give more context to what was done above.
def delete(node, data): ''' (BTNode, data) -> BTNode Delete, if it exists, node with data and return resulting tree. >>> b = BTNode(8) >>> b = insert(b, 4) >>> b = insert(b, 2) >>> b = insert(b, 6) >>> b = insert(b, 12) >>> b = insert(b, 14) >>> b = insert(b, 10) >>> b = delete(b, 12) >>> print(b) 14 10 8 6 4 2 <BLANKLINE> ''' return_node = node if not node: # Step 1 from the algorithm pass elif data < node.data: # Step 2 from the algorithm node.left = delete(node.left, data) elif data > node.data: # Step 3 from the algorithm node.right = delete(node.right, data) elif not node.left: # Step 4 from the algorithm return_node = node.right elif not node.right: # Step 4, again, from the algorithm return_node = node.left else: # Step 5 from the algorithm node.data = _find_max(node.left).data node.left = delete(node.left, node.data) return return_node
def _find_max(node): ''' (BSTNode) -> BSTNode Return maximal node in the BST rooted at node. Assume node is not None. >>> b = BTNode(8) >>> b = insert(b, 4) >>> b = insert(b, 2) >>> b = insert(b, 6) >>> b = insert(b, 12) >>> b = insert(b, 14) >>> b = insert(b, 10) >>> _find_max(b).data 14 >>> _find_max(b.left).data 6 ''' return _find_max(node.right) if node.right else node
I wish I could say this could is easy to understand. Once you analyze it, it makes sense how it works and what it does. Regardless, there is a difference between knowing what to do and knowing how it needs to be done. The algorithm is not that intuitive, and requires close attention to notice exactly why things happen, and then how.