How does this BST node-deletion algorithm work?

Question

I try to follow the BST algorithm in Granville Barnett's “Data Structures and Algorithms,” but I don’t understand what node-dletion is described below.

Section 3.3 (p. 22)

Removing a node from a BST is quite simple, with four cases considered:

• the value to delete is the leaf node; or
• the value for deletion has the correct subtree, but does not have a left subtree; or
• the left subtree has the value for deletion, but does not have the subtree right; or
• both left and right subtrees are important for deletion, in this case we advance the greatest value in the left subtree.

Figure 3.2 (page 22)

23 / \ 14 31 / 7 \ 9 

• Case # 1 points to node 9.
• Case # 2 points to node 7.
• Case # 3 points to node 14.
• Case # 4 points to node 23.

I interpret the text above for # 4, to mean that when we remove 23, we push 14 to the root and make it the right child:

  14 / \ 7 31 \ 9 

... but the algorithm of the book (from page 23) for case No. 4 of bamboo me (I rewrote it here in Java):

 1 boolean remove(T value) { 2 // ... 3 4 // case #4 5 Node largestValueNode = nodeToRemove.left; 6 while (largestValueNode.right != null) { 7 // find the largest value in the left subtree of nodeToRemove 8 largestValueNode = largestValueNode.right; 9 } 10 11 // delete the right child of largestValueNode parent 12 findParent(largestValueNode.value).right = null; 13 nodeToRemove.value = largestValueNode.value; 14 15 count--; 16 return true; // successful 17} 

If I follow the algorithm, the largestValueNode is node 14, so its parent is node 23. Why does the algorithm negate the right child of the parent?

Why largestValueNode line 13 copy the largestValueNode value to node for deletion?

I expected lines 11-13 to be like this:

 11 if (largestValueNode != null) 12 largestValueNode.right = nodeToRemove.right; 13 nodeToRemove.right = null; 

EDIT:

The book algorithm does have an error. Correction:

 1 boolean remove(T value) { 2 // ... 3 4 // case #4 5 Node largestValueNode = nodeToRemove.left; 6 while (largestValueNode.right != null) { 7 // find the largest value in the left subtree of nodeToRemove 8 largestValueNode = largestValueNode.right; 9 } 10 11 Node p = findParent(largestValueNode.value); 12 if (p != null) { 13 if (nodeToRemove == p) 14 nodeToRemove.left = largestValueNode.left; 15 else 16 p.right = largestValueNode.left; 17 } 18 nodeToRemove.value = largestValueNode.value; 19 20 count--; 21 return true; // successful 22} 

Answer 1

if you do that

 11 if (largestValueNode != null) 12 largestValueNode.right = nodeToRemove.right; 13 nodeToRemove.right = null; 

you are not considering the case where 14 may have a valid child. For example:

  23 / \ 14 31 / \ 7 15 \ 9 

This is the solution when removal 23 should be

  15 / \ 14 31 / 7 \ 9 

So you set the correct child of 15 original parent, 14 to null. This is what the first code does.

Edit: addressing your comment

With your decision you will receive

  23 / 14 / \ 7 15 \ \ 9 31 

In addition, the source code is also incorrect; try something like this:

 if(nodeToRemove == findParent(largestValueNode.value)) nodeToRemove.left = largestValueNode.left else findParent(largestValueNode.value).right = largestValueNode.left nodeToRemove.value = largestValueNode.value 

Also, to answer: "Why does line 13 copy the value of the highest ValueNode in the node to be deleted?"

We remove the largestValueNode before which we store this value in nodeToRemove

Answer 2

The book's algorithm seems to be incorrect for this particular example (assuming you translated perfectly into Java :)). It does what you mentioned, but this is correct for the case:

where nodeToRemove = 23 and your BST 14 had the correct child 15. The book algorithm would replace 23 with 15 here and set the 14 right child elements to null. In this case, your algorithm will fail.

Answer 3

Take a close look at the line:

 largestValueNode.right = nodeToRemove.right; 

Notice how this line calls 14 to look like this (ignoring grandchildren):

  14 / \ 7 31 

But this is exactly what you need! Since 14 now has 31 as its right child, it is no longer valid for 31 as the right child of 15 , so for clearing, the correct child of 15 is NULL.

Answer 4

It’s good to know that the source code is wrong - I just spent a few hours on it and always thought that something was missing. There is an NPE problem if the root element is passed, and in any case, the removal of the root element is not taken into account.

Here's my Java implementation, which can probably use some optimization, suggestions are welcome. O (n log n) worst case. Tests below.

 public boolean remove(final T value0) { BinarySearchTreeNode<T> target = findNode(value0); // Node DNE if (target == null) { return false; } // Both children populated, no need for parent if (target.right != null && target.left != null) { BinarySearchTreeNode<T> max = maxChild(target.left); findParent(max.value).right = null; target.value = max.value; } // Root element targeted, parent DNE else if (target == root) { if (target.right == null && target.left == null) { root = null; } else if (target.right == null) { root = target.left; } else { root = target.right; } } // Non-root, single-child node - find if L or R child, update parent reference. else { BinarySearchTreeNode<T> parent = findParent(value0); if (target.right == null && target.left != null) { if (target.value.compareTo(parent.value) < 0) { parent.left = target.left; } else { parent.right = target.left; } } else if (target.right != null && target.left == null) { if (target.value.compareTo(parent.value) < 0) { parent.left = target.right; } else { parent.right = target.right; } } } return true; } 

---

Unit tests (all pass, obviously):

 package BinarySearchTreeTests; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertNull; import static org.junit.Assert.assertTrue; import org.junit.Before; import org.junit.Test; public class Remove { BinarySearchTree<Integer> tree; @Before public void setUp() { tree = new BinarySearchTree<Integer>(); } @Test public void fromEmptyTree() { assertFalse(tree.remove(8)); } @Test public void fromTreeWithOnlyRootNode() { tree.add(10); assertTrue(tree.remove(10)); assertNull(tree.root); } @Test public void nonexistentElement() { tree.add(10); assertFalse(tree.remove(8)); } /** * N * 10--| * | 6 * 5--| * 3 */ @Test public void nodeWithNoRightChildren() { tree.add(10); tree.add(5); tree.add(6); tree.add(3); tree.remove(10); assertEquals(tree.root.value, Integer.valueOf(5)); assertEquals(tree.root.left.value, Integer.valueOf(3)); assertEquals(tree.root.right.value, Integer.valueOf(6)); } /** * 17 * 15--| * | 13 * 10--| * N */ @Test public void nodeWithNoLeftChildren() { tree.add(10); tree.add(15); tree.add(17); tree.add(13); tree.remove(10); assertEquals(tree.root.value, Integer.valueOf(15)); assertEquals(tree.root.left.value, Integer.valueOf(13)); assertEquals(tree.root.right.value, Integer.valueOf(17)); } /** * 19 * 17-| * | 16 * 15-| * | | 14 * | 13-| * | 12 * 10--| * N */ @Test public void nodeWithLeftAndRightChildren() { tree.add(10); tree.add(15); tree.add(17); tree.add(13); tree.add(19); tree.add(16); tree.add(14); tree.add(12); tree.remove(15); assertEquals(tree.root.right.value, Integer.valueOf(14)); assertNull(tree.root.right.left.right); } /** * 18 * 15-| * | [ALWAYS EMPTY] * 15-| * | | 13 * | 12-| * | 11 * 10--| * N * @Test public void removeDuplicate() { Above diagram shows duplicate cases are already tested implicitly. fail(); } */ }