| Hide text Hide pseudo-code | |
|
Delete the given keys one at a time from the binary search tree. Possible equal keys were inserted into the left branch of the existing node. Please note that the insertion strategy also affects how the deletion is performed. Some additional problems. | Node Delete(Node root, Key k) 1 if (root == null) // failed search 2 return null; 3 if (k == root.key) // successful search 4 return DeleteThis(root); 5 if (k < root.key) // k in the left branch 6 root.left = Delete(root.left, k); 7 else // k > root.key, i.e., k in the right branch 8 root.right = Delete(root.right, k); 9 return root; Node DeleteThis(Node root) 1 if root has two children 2 p = Largest(root.left); // replace root with its immediate predecessor p 3 root.key = p.key; 4 root.left = Delete(root.left, p) 5 return root; 6 if root has only left child 7 return root.left 8 if root has only right child 9 return root.right 10 else root has no children 11 return null Node Largest(Node root) 1 if root has no right child 2 return root 3 return Largest(root.right) |