使用红黑树的字典——删除错误

Question

我正在尝试使用红黑树实现一个字典。
我已经测试了插入方法，似乎工作得很好，RBtree似乎保持了正确的形状和颜色。执行二叉树节点删除的方法似乎是正确的，但是在删除后调用的deleteFixUp方法上出现了巨大的问题。

您是否愿意帮助我找出我做错了什么？当然，如果您有任何改进代码的建议，将不胜感激。

RBTreeWParentDictionary.java（这里我实现了RedBlackTree）

package dictionary;

import java.util.Comparator;

public class RBTreeWParentDictionary<K, V> implements IDictionary<K, V> {
  /**
   * The root node of the RBTreeWParentDictionary
   */
  public RBTreeWParentNode<K, V> root;

  /**
   * Object used to compare two T objects.
   */
  private Comparator<K>          comparator;

  private int                    length;

  /**
   * Creates the dictionary based on red/black tree with null root
   * 
   * @param comparator
   *          The comparator for keys
   */
  public RBTreeWParentDictionary(Comparator<K> comparator) {
    this.root = null;
    this.comparator = comparator;
    this.length = 0;
  }

  /**
   * Checks if the tree is empty
   * 
   * @return True if the tree is empty
   */
  public boolean isEmpty() {
    return this.root == null;
  }

  /**
   * Returns the number of elements in the tree
   * 
   * @return The number of elements in the tree
   */
  public int length() {
    return this.length;
  }

  /**
   * Performs a left rotation on the tree node
   * 
   * @param node
   *          The node on which rotate
   */
  private void rotateLeft(RBTreeWParentNode<K, V> node) {
    RBTreeWParentNode<K, V> y = node.getRight();
    node.setRight(y.getLeft());
    if (y.hasLeft()) {
      y.getLeft().setParent(node);
    }
    y.setParent(node.getParent());
    if (!node.hasParent()) { // = this.isEmpty()
      this.root = y;
    }
    else {
      if (node.equals(node.getParent().getLeft())) {
        node.getParent().setLeft(y);
      }
      else {
        node.getParent().setRight(y);
      }
    }
    y.setLeft(node);
  }

  /**
   * Performs a right rotation on the tree node
   * 
   * @param node
   *          The node on which rotate
   */
  private void rotateRight(RBTreeWParentNode<K, V> node) {
    RBTreeWParentNode<K, V> y = node.getLeft();
    node.setLeft(y.getRight());
    if (y.hasRight()) {
      y.getRight().setParent(node);
    }
    y.setParent(node.getParent());
    if (!node.hasParent()) {
      this.root = y;
    }
    else {
      if (node.equals(node.getParent().getRight())) {
        node.getParent().setRight(y);
      }
      else {
        node.getParent().setLeft(y);
      }
    }
    y.setRight(node);
  }

  /*
   * Uses for first tests, now removed
   * 
   * public void testRotateLeft() { this.rotateLeft(this.root); }
   * 
   * public void testRotateRight() { this.rotateRight(this.root); }
   */

  /**
   * Performs all the needed work to the tree under the 3 main rules of R/BTree
   * 
   * @param node
   *          The current node that needs to be checked
   */
  private void treeFixUp(RBTreeWParentNode<K, V> node) {
    RBTreeWParentNode<K, V> u;
    if (!node.hasParent()) {
      return;
    }
    while (node.getParent().isRed()) {
      if (node.getParent().equals(node.getParent().getParent().getLeft())) {
        u = node.getParent().getParent().getRight();
        if (u != null && u.isRed()) {
          node.getParent().setBlack();
          u.setBlack();
          node.getParent().getParent().setRed();
          node = node.getParent().getParent();
        }
        else {
          if (node.equals(node.getParent().getRight())) {
            node = node.getParent();
            rotateLeft(node);
          }
          node.getParent().setBlack();
          node.getParent().getParent().setRed();
          rotateRight(node.getParent().getParent());
        }
      }
      else {
        u = node.getParent().getParent().getLeft();
        if (u != null && u.isRed()) {
          node.getParent().setBlack();
          u.setBlack();
          node.getParent().getParent().setRed();
          node = node.getParent().getParent();
        }
        else {
          if (node.equals(node.getParent().getLeft())) {
            node = node.getParent();
            rotateRight(node);
          }
          node.getParent().setBlack();
          node.getParent().getParent().setRed();
          rotateLeft(node.getParent().getParent());
        }
      }
      if (!node.hasParent()) {
        node.setBlack();
        break;
      }
    }
  }

  /**
   * Inserts a node with give key/value
   * 
   * @param key
   *          The key of the node to be inserted
   * @param value
   *          The value of the node to be inserted
   */
  @Override
  public void insert(K key, V value) {
    int res;
    RBTreeWParentNode<K, V> insertedNode = new RBTreeWParentNode<K, V>(key,
        value);
    if (this.isEmpty()) {
      this.root = insertedNode;
      this.root.setBlack();
    }
    else {
      RBTreeWParentNode<K, V> node = this.root;
      while (node != null) {
        res = comparator.compare(key, node.getKey());
        if (res < 0) {
          if (node.hasLeft()) {
            node = node.getLeft();
          }
          else break;
        }
        else if (res > 0) {
          if (node.hasRight()) {
            node = node.getRight();
          }
          else break;
        }
        else { // duplicate key, overwriting
          node.setValue(value);
          return;
        }
      }
      res = comparator.compare(key, node.getKey());
      if (res < 0) {
        node.setLeft(insertedNode);
      }
      else {
        node.setRight(insertedNode);
      }
      treeFixUp(insertedNode);
      this.length++;
    }
  }

  @Override
  public V get(K key) {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public void delete(K key) {
    RBTreeWParentNode<K, V> node = root;
    boolean oldColor;
    int res;

    while (node != null
        && (res = comparator.compare(key, node.getKey())) != 0) {
      if (res < 0) node = node.getLeft();
      else node = node.getRight();
    }    
    if (node == null)
      return;
    oldColor = node.getColor();
    // key found, work with children
    if (!node.hasParent()) {//In root
      root = null;
      return;
    }
    else if(node.hasLeft() && !node.hasRight()) {//left child
      node.getLeft().setParent(node.getParent());
      node.getParent().setLeft(node.getLeft());
    }
    else if (!node.hasLeft() && node.hasRight()) {//right child
      node.getRight().setParent(node.getParent());
      node.getParent().setRight(node.getRight());
    }
    else if (node.hasLeft() && node.hasRight()) {//both children
      RBTreeWParentNode<K, V> tmp = node;
      node = min(tmp.getRight());
      //fix parent node of node
      node.setParent(tmp.getParent());
      if (tmp.getParent().getLeft().equals(tmp)) {
        node.getParent().setLeft(node);
      }
      else node.getParent().setRight(node);

      node.setRight(deleteMin(tmp.getRight()));
      node.setLeft(tmp.getLeft());
      tmp = null;
    }
    else { // is a leaf
      if (node.equals(node.getParent().getLeft()) ) {
        node.getParent().setLeft(null);
      }
      else node.getParent().setRight(null);
    }
    if (oldColor == false) {
      deleteFixUp(node);
    }
  }

  private RBTreeWParentNode<K, V> deleteMin(
      RBTreeWParentNode<K, V> node) {
    if (node.getLeft() == null) {
      return node.getRight();
    }
    node.setLeft(deleteMin(node.getLeft()));
    return node;
  }

  private RBTreeWParentNode<K, V> min(RBTreeWParentNode<K, V> node) {
    if (node.getLeft() == null) {
      return node;
    }
    else return min(node.getLeft());
  }


  private void deleteFixUp(RBTreeWParentNode<K, V> node) {
    while (!node.equals(this.root) && node.isBlack()) {
      if (node.equals(node.getParent().getLeft())) {
        if (node.getParent().hasRight()) {
          RBTreeWParentNode<K, V> w = node.getParent().getRight();
          if (w.isRed()) {
            w.setBlack();
            node.getParent().setRed();
            rotateLeft(node.getParent());
            w=node.getParent().getRight();
          }
          if (w.hasLeft() && w.hasRight() && w.getLeft().isBlack() && w.getRight().isBlack()) {
            w.setRed();
            node = node.getParent();
          }
          else {
            if (w.hasRight() && w.getRight().isBlack()) {
              w.getLeft().setBlack();
              w.setRed();
              rotateRight(w);
              w = node.getParent().getRight();
            }
            w.setColor(node.getParent().getColor());
            node.getParent().setBlack();
            w.getRight().setBlack();
            rotateLeft(node.getParent());
            node = this.root;
          }          
        }
      }
      else {
        //Repeat up changing left with right
        if (node.getParent().hasLeft()) {
          RBTreeWParentNode<K, V> w = node.getParent().getLeft();
          if (w.isRed()) {
            w.setBlack();
            node.getParent().setRed();
            rotateRight(node.getParent());
            w=node.getParent().getLeft();
          }
          if (w.hasLeft() && w.hasRight() && w.getLeft().isBlack() && w.getRight().isBlack()) {
            w.setRed();
            node = node.getParent();
          }
          else {
            if (w.hasLeft() && w.getLeft().isBlack()) {
              w.getRight().setBlack();
              w.setRed();
              rotateLeft(w);
              w = node.getParent().getLeft();
            }
            w.setColor(node.getParent().getColor());
            node.getParent().setBlack();
            w.getLeft().setBlack();
            rotateRight(node.getParent());
            node = this.root;
          }          
        }
      }
    }
    node.setBlack();
  }

  @SuppressWarnings("unused")
  @Override
  public boolean equals(Object other) {
    if (!(other instanceof RBTreeWParentDictionary)) {
      return false;
    }
    if ((this == null && other != null) || (this != null && other == null)) {
      return false;
    }
    if (this == null && other == null) {
      return true;
    }
    else {
      @SuppressWarnings("unchecked")
      RBTreeWParentDictionary<K, V> oth = (RBTreeWParentDictionary<K, V>) other;
      return equalsNodes(this.root, oth.root);
    }
  }

  private boolean equalsNodes(RBTreeWParentNode<K, V> node1,
      RBTreeWParentNode<K, V> node2) {
    if ((node1 == null && node2 != null) || (node1 != null && node2 == null)) {
      return false;
    }
    else if (node1 == null && node2 == null) {
      return true;
    }
    else return node1.equals(node2)
        && equalsNodes(node1.getLeft(), node2.getLeft())
        && equalsNodes(node1.getRight(), node2.getRight());
  }

}

RBTreeWParentNode.java（这是红黑树的节点）

package dictionary;

public class RBTreeWParentNode<K, V> {
  private K                    key;
  private V                    value;
  private boolean              color;
  private RBTreeWParentNode<K, V>  left, right, parent;

  private static final boolean RED   = true;
  private static final boolean BLACK = false;

  public RBTreeWParentNode(K key, V value, RBTreeWParentNode<K, V> left,
      RBTreeWParentNode<K, V> right, RBTreeWParentNode<K, V> parent) {
    this.key = key;
    this.value = value;
    this.color = RED;
    this.left = left;
    if (this.hasLeft())
      this.getLeft().setParent(this);
    this.right = right;
    if (this.hasRight())
      this.getRight().setParent(this);
    this.parent = parent;
  }

  public RBTreeWParentNode(K key, V value) {
    this.key = key;
    this.value = value;
    this.color = RED;
  }

  public RBTreeWParentNode() {
  }

  public K getKey() {
    return key;
  }

  public V getValue() {
    return value;
  }

  public boolean getColor() {
    return color;
  }

  public RBTreeWParentNode<K, V> getLeft() {
    return left;
  }

  public RBTreeWParentNode<K, V> getRight() {
    return right;
  }

  public RBTreeWParentNode<K, V> getParent() {
    return parent;
  }

  public RBTreeWParentNode<K, V> getBrother() {
    if (this.hasParent()) {
      if (this.getParent().getLeft().equals(this)) {
        return this.getParent().getRight();
      }
      else return this.getParent().getLeft();
    }
    else return null;
  }

  public boolean isRed() {
    return this.color == RED;
  }

  public boolean isBlack() {
    return this.color == BLACK;
  }

  public boolean hasLeft() {
    return this.getLeft() != null;
  }

  public boolean hasRight() {
    return this.getRight() != null;
  }

  public boolean hasParent() {
    return this.getParent() != null;
  }

  public boolean hasBrother() {
    if (this.hasParent()) {
      if (this.getParent().getLeft().equals(this)) {
        return this.getParent().getRight() != null;
      }
      else return this.getParent().getLeft() != null;
    }
    else return false;
  }

  public void setKey(K key) {
    this.key = key;
  }

  public void setValue(V value) {
    this.value = value;
  }

  public void setRed() {
    this.color = RED;
  }

  public void setBlack() {
    this.color = BLACK;
  }

  public void setParent(RBTreeWParentNode<K, V> node) {
    this.parent = node;
  }

  public void setLeft(RBTreeWParentNode<K, V> node) {
    this.left = node;
    if (this.hasLeft())
      this.left.setParent(this);
  }

  public void setRight(RBTreeWParentNode<K, V> node) {
    this.right = node;
    if (this.hasRight())
      this.right.setParent(this);
  }

  public void setColor(boolean color) {
    this.color = color;
  }

  @Override
  public boolean equals(Object other) {
    if (!(other instanceof RBTreeWParentNode)) {
      return false;
    }
    if ((this == null && other != null) || (this != null && other == null)) {
      return false;
    }
    @SuppressWarnings("unchecked")
    RBTreeWParentNode<K, V> oth = (RBTreeWParentNode<K, V>) other;
    return checkFieldsEquals(oth);
  }

  private boolean checkFieldsEquals(RBTreeWParentNode<K, V> oth) {
    //Check keys
    if ((this.getKey() == null && oth.getKey() != null)
        || (this.getKey() != null && oth.getKey() == null)) {
      return false;
    }
    else {
      if ((this.getKey() == null && oth.getKey() == null)
          || this.getKey().equals(oth.getKey())) {
        if ((this.getValue() == null && oth.getValue() != null)
            || (this.getValue() != null && oth.getValue() == null)) {
          return false;
        }
        else {
          if ((this.getValue() == null && oth.getValue() == null)
              || (this.getValue().equals(oth.getValue()))) {
            if (this.getColor() != oth.getColor()) {
              return false;
            }
            else {
              return (this.getKey() == null && oth.getKey() == null)
                  || this.getKey().equals(oth.getKey());
            }
          }
          else return false;
        }
      }
      else {
        return false;
      }
    }
  }

}

RBTreeWParentDictionaryTest.java -> 我的测试类

更新于 09/07/2016 我已经更新了我的代码，因为我发现在修复后没有将节点游标更新为根节点，并且只有当删除的节点为黑色时才调用修复函数。
考虑到我的测试用例 testDeleteDoubles，我发现当它有兄弟时选择了错误的候选项来与要删除的项交换。
在这个模拟器上看到，候选者应该是被删除项左侧分支上的最大节点，但它不应该是继承者，所以右侧分支上的最小项是吗？

- tommaso capelli

---

我仔细地阅读了FixDelete的代码，它似乎做了我所期望的一切。我建议您将其设置为受保护的，并编写一些测试，以查明出现错误的原因。 - sprinter

你好 @sprinter，我更新了我的代码，因为我发现了一些问题，但是我仍然无法解决它。我猜测在删除具有两个子节点的节点时，我选择了错误的后继节点。你对此有什么看法？ - tommaso capelli

我认为这个问题没有一种快速解决方案。delete 方法似乎包含了很多 bug。例如，在“两个子节点都存在”的情况下，应该更新 oldColor，而且 deleteFixUp 应该使用一个子节点，而不是节点自身。 - dejvuth

谢谢@dejvuth的评论。您能具体说明一下吗？当我删除一个有两个子节点的节点时，oldColor应该采取哪个值？在哪个子节点上应该调用deleteFixUp？ - tommaso capelli

Answer 1

在delete()中，需要记住被删除节点的子节点，因为删除后可能会违反红黑树的性质。假设我们声明了RBTreeWParentNode<K, V> childOfDeletedNode;

然后，在左子节点的情况下，您需要更新childOfDeletedNode = node.getLeft();

对于右子节点的情况，您需要更新childOfDeletedNode = node.getRight();

对于两个子节点，您需要在调用min()之后添加以下内容：

oldColor = node.getColor();
childOfDeletedNode = node.getLeft();
node.setColor(tmp.getColor());

对于节点的删除，可以选择任意一个子节点 childOfDeletedNode = node.getRight();

接着，使用 deleteFixUp(childOfDeletedNode); 来修复该子节点的颜色。

现在由于childOfDeletedNode可能为 null，因此需要在循环条件中添加对 node != null 的检查，并在最后一行设置颜色为黑色之前添加 if 语句来处理该情况。

无论如何，您所参考的模拟器会找到左子树的最大节点。您的解决方案找到右子树的最小节点。两种方法都是正确的，但结果不同。您需要修正测试用例。

举例说明，在删除之前：

      10(B)
     /    \
    8(R)  100(B)
   /   \
  5(B) 9(B)
 /   \
2(R) 6(R)

在删除 8 后，您可以用右子树的最小节点 9 进行替换。该节点的颜色将改为红色。

      10(B)
     /    \
    9(R)  100(B)
   /
  5(B)
 /   \
2(R) 6(R)

- dejvuth