[ad_1]

I am reading the book Algorithms by Sedgewick and Wayne of Princeton, and it presents a BST deletion method for BSTMaps.

```
public void deleteMin()
{
root = deleteMin(root);
}
private Node deleteMin(Node x)
{
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(Key key)
{ root = delete(root, key); }
private Node delete(Node x, Key key)
{
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
else if (cmp > 0) x.right = delete(x.right, key);
else
{
if (x.right == null) return x.left;
if (x.left == null) return x.right;
Node t = x;
x = min(t.right); // <----This would cause infinite loop
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}
```

It turns out to be a famous algorithm called eager Hibbard deletion, which is also presented in this link: http://math.oxford.emory.edu/site/cs171/hibbardDeletion/

As the code is in Java, I tried to implement it myself. But it causes infinite loop because of a reference problem. If x is pointed to the successor, and x.left is updated, then the deleteMin method will not only delete the original node, but go through the new left branch to delete the min of the other half of the tree.

This can be bypassed by copying the values and keys of min(t.right) instead of just use ‘=’, and the t node would be unnecessary.

But my question is: **is the code in the book (and the webpage) just blatantly wrong?** It is hard to conceive since this is a well-received book at its 4th edition.

[ad_2]