这个BST节点删除算法如何工作？

4 回答

• 1

  如果你这样做

  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 的正确子级设置为null . 这是第一个代码正在做的事情 .

  编辑：处理您的评论

  有了你的解决方案，你就会得到

  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行将maximumValueNode的值复制到要删除的节点中？”

  我们正在删除 largestValueNode ，之前我们're storing it'的值在 nodeToRemove 中

  回复于 2024-04-29T12:58:53+08:00
• 3

  看起来这本书的算法对于这个特定的例子是错误的（假设你完全翻译成了Java :)） . 它正在做你提到的，但它适用于这种情况：

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

  回复于 2024-04-29T12:58:53+08:00
• 0

  仔细看看这条线：

  largestValueNode.right = nodeToRemove.right;
  

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

  14
   /  \
  7   31
  

  但这正是所期望的！由于 14 现在将 31 作为其右子，因此 31 不再是 15 的正确子项，所以为了清理起见， 15 的右子项设置为NULL .

  回复于 2024-04-29T12:58:53+08:00
• 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();
  } */
  }
  

  回复于 2024-04-29T12:58:53+08:00