Binary Search Tree Deletion

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    // 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)


  Created Fri Oct 30 13:52:51 EET 2009 - Powered by SVG-hut