2

我正在尝试遵循Granville Barnett 的“数据结构和算法”中的 BST 算法，但我不理解它在下面描述的节点删除算法。

第 3.3 节（第 22 页）

从 BST 中删除节点相当简单，需要考虑四种情况：

  1. 要删除的值是叶节点；或者
  2. 要删除的值有一个右子树，但没有左子树；或者
  3. 要删除的值有一个左子树，但没有右子树；或者
  4. 要删除的值同时具有左子树和右子树，在这种情况下，我们提升左子树中的最大值。

图 3.2（第 22 页）

    23
   /  \
  14   31
 /
7
 \
  9
  • 案例 #1 指向节点 9。
  • 案例 #2 指向节点 7。
  • 案例 #3 指向节点 14。
  • 案例 #4 指向节点 23。

我将上面 #4 的文本解释为，当我们删除 23 时，我们将 14 提升为 root 并使 31 成为其右孩子：

  14
 /  \
7   31
 \
  9

...但是案例＃4的书中算法（从第23页开始）让我感到困惑（我在这里用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's parent
12  findParent(largestValueNode.value).right = null;
13  nodeToRemove.value = largestValueNode.value;
14  
15  count--;
16  return true; // successful
17}

如果我按照算法，largestValueNode是节点 14，所以它的父节点是节点 23。为什么该算法会使父节点的右孩子无效？

为什么第 13 行将largestValueNode' 值复制到要删除的节点中？

我预计第 11-13 行是：

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

编辑：

这本书的算法确实有一个错误。修复如下：

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}
4

4 回答 4

3

如果你这样做

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

你没有考虑14可能有一个正确的孩子的情况。例如：

     23
    / \
   14  31
  / \
 7   15
  \
   9

删除时您的解决方案23应该是

     15
    / \
   14  31
  / 
 7  
  \
   9

因此，您将15' 的原始父级的右子级设置14为空。这就是第一个代码正在做的事情。

编辑：解决您的评论

使用您的解决方案，您将获得

     23
    / 
   14  
  / \
 7   15
  \   \
   9   31

另外，原代码也是错误的；尝试这样的事情：

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

还要回答“为什么第 13 行将最大值节点的值复制到要删除的节点中？”

我们正在删除largestValueNode，在此之前我们将它的值存储在nodeToRemove

于 2012-07-08T00:01:58.440 回答
1

对于这个特定的例子，这本书的算法似乎是错误的（假设你已经完美地翻译成 Java :)）。它正在做你提到的事情，但它适合这种情况：

其中 nodeToRemove = 23 并且在您的 BST 14 中有一个右孩子 15。本书的算法将在这里用 15 替换 23 并将 14 的右孩子设置为空。在这种情况下，您的算法将失败。

于 2012-07-08T00:10:09.053 回答
0

很高兴知道原始代码是错误的——我只花了几个小时在上面，一直在想我错过了什么。如果通过了根元素，则存在 NPE 问题，并且无论如何都不会考虑根元素的删除。

这是我的 Java 实现，可能会使用一些优化 - 欢迎提出建议。O (n log n)最坏的情况下。下面进行测试。

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;
}

单元测试（显然都通过了）：

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();
} */
}
于 2014-02-15T21:58:13.677 回答
0

仔细看一下这条线：

largestValueNode.right = nodeToRemove.right;

请注意这条线如何导致14看起来像这样（忽略孙子）：

  14
 /  \
7   31

但这正是我们想要的！由于14now has作为其右孩子，因此成为 的右31孩子不再正确，因此为了清理，将 的右孩子设置为 NULL。311515

于 2012-07-08T00:17:34.720 回答