Hide text Hide pseudo-code | |

Delete the given keys 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 // replace root with its immediate predecessor p 3 p = Largest(root.left); 4 root.key = p.key; 5 root.left = Delete(root.left, p) 6 return root; 7 if root has only left child 8 return root.left 9 if root has only right child 10 return root.right 11 else // root has no children 12 return null Node Largest(Node root) 1 if root has no right child 2 return root 3 return Largest(root.right) |