javascript - 红黑树 - JavaScript 中的删除方法

Question

参见下面的原始红黑树:

         42B
       /    \
     10R     64B
    /  \     /  \
  7B   29B 50R  83R
  /
5R

我在尝试删除 29 时遇到了麻烦。因为尝试删除此节点会导致双黑(我们称之为 DB)情况，而 DB 的远侄子 (5R) 节点是一个RED 节点，我们应该能够通过简单地交换父节点 (10R) 和兄弟节点 (7B) 的颜色、沿 DB 方向旋转 DB 的父节点并为 DB 着色来解决此问题侄子黑色，所以结果是:

         42B
       /    \
     7R     64B
    /  \     /  \
  5B   10B 50R  83R

但我得到的是以下内容:

         42B
       /    \
     10B     64B
    /  \     /  \
  NIL   29B 50R  83R

参见下面的代码，remove(value) 调用 removeBST(root,value)，如果需要，它会调用 fixDoubleBlack()。由于代码很长，我省略了不相关的部分，但我发布了代码 here 。我知道这可能需要一些时间，而且要求很多，所以非常感谢任何愿意看一看的人。在尝试调试这个问题时，我确实老了几岁。

class redBlackTree {
  constructor () {
    this.root = null;
  }
  ... ...
  
  // ------------- RED BLACK: NODE REMOVAL METHODS ------------->>
  remove(value) {
    let node = new Node(value); 

    if (this.root === null) { return; } 
    
    this.root = this.removeBST(this.root, node);
  }

  removeBST (root, node) {//Binary Search Tree (BST) regular remove() method.
    if (root === null || node === null) { return null; } //Tree is either empty or node=null

    if (node.value === root.value) { //value to be removed was found
      if ((root.left === null) && (root.right === null)) { //node is a leaf node.
        if(root === this.root) { return null; } //node is root, just remove it.
        else if (root.color === 'RED') { return null; } //node is a leaf and is RED, just remove it.
        else { 
          //Node being removed (29) is a BLACK node w/ no children, fix double-black.

          this.fixDoubleBlack(root);
          root = null; 

          //calling inOrderTraversal() here shows the correct result.
        }
      } 
  
     }
    ... another cases ...
    else if (node.value < root.value) { root.left = this.removeBST(root.left, node); }
    else if (node.value > root.value) { root.right = this.removeBST(root.right, node); }

    return root; //I believe the problem may be in this return statement !!!
  }

  fixDoubleBlack(node) {
  
    if(node === this.root) { return; } 
    let sibling = this.getSibling(node);
    let parent = node.parent;

    if(!sibling) { this.fixDoubleBlack(parent); }
    else {
      if(sibling.color === 'RED') {... sibling is RED ... }
      else {//As sibling is BLACK, we have three cases that can be applied:
        if(this.anyRedChild(sibling)){//1-: sibling has at least one RED child
          if(this.isLeftChild(sibling)){//sibling is left child
            if(sibling.left && sibling.left.color === 'RED'){
              //DB's far nephew is RED:

              this.colorSwap(parent,sibling); 
              this.colorSwitch(sibling.left); 
              this.rightRotation(parent);

              parent.right = null;

              //calling inOrderTraversal() here shows the correct result.
            }
            else { ... }
          }
          else { ... }
        } 
        else { ... }
      }
    }
  }

  // ---------------------- SUPPORT METHODS -------------------->>
  colorSwitch(node){ ... inverts the color of the node ...}
  colorSwap(node1, node2){ ... swaps the colors of the nodes ...}
  getSibling(node){ ... returns the sibling of the node passed as argument ...}
  isLeftChild(node){... returns a boolean if the node is a left child ... }
  anyRedChild(node){... returns a boolean if the node has a RED child ...}

  // --------------------- ROTATION METHODS -------------------->> 
  rightRotation(node) {//LL condition --> Right Rotation
    let tempNode = node.left;
    node.left = tempNode.right;

    //Update parent reference in case of temp node having a right subtree:
    if(node.left !== null) { node.left.parent = node; }

    //Update temp node parent to be node's parent:
    tempNode.parent = node.parent;

    //Update parent references for rotated node:
    if(node.parent === null) { this.root = tempNode; }
    else if(node === node.parent.left) { node.parent.left = tempNode; }
    else { node.parent.right = tempNode; } 

    tempNode.right = node;
    node.parent = tempNode;
  }
  ...

  // --------------------- TRAVERSAL METHODS ------------------->>
  levelOrderTraversal() {//1st level --> 2nd level --> 3rd level ...
    let queue = [];
    if (this.root !== null) {
      queue.push(this.root);
      while (queue.length > 0) {
        let node = queue.shift();
        console.log(node.value);
        if (node.left !== null) {
          queue.push(node.left);
        }
        if (node.right !== null) {
          queue.push(node.right);
        }
      }
    } else {
      return null;
    }
  }
}
let rbTree = new redBlackTree();

rbTree.insert(42); rbTree.insert(10);  rbTree.insert(64);
rbTree.insert(7);  rbTree.insert(29);  rbTree.insert(50);
rbTree.insert(83); rbTree.insert(5); 

rbTree.remove(29); 

rbTree.levelOrderTraversal();

如上所述，在 fixDoubleBlack() 调用之后调用 levelOrderTraversal() 会显示正确的结果，因此我认为这可能是 removeBST return语句。

Answer 1

下一步试试。 :)

您需要通过 removeBST 返回任何内容吗？我认为您不会，因为当您进行旋转和其他智能操作时，您确实会修改相应的节点。

因此，不要使用 root.left = this.removeBST(root.left, node)，只需编写 this.removeBST(root.left, node) 并执行以下操作与右边的 child 一样。另外，只需在 remove 中调用 this.removeBST，但不要重新分配 this.root。它似乎适用于该示例，但我可能会错过您真正需要它的其他一些情况。 (code)