红黑树 - JavaScript 中的删除方法

Question

看下面的原始红黑树：

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

我在尝试删除 29 时遇到问题。因为尝试删除此节点会导致双黑（我们称之为 DB）情况，而 DB 的远侄（5R）节点是红色的节点，我们应该能够通过简单地交换父节点 (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, node) 总是 returns root（可能 children 不同）。如果进行旋转，则应该 return 子树的新根。

在您的示例中，它在哪里导致问题？

你用 root.value = 42, root.left.value = 10. 调用 root.left = this.removeBST(root.left, node); 你在左子树中做了你需要做的事情，然后将值 10 的节点分配给左 child共 42.

当 root.value 为 10 且 root.right.value 为 29 时，您也调用 root.right = this.removeBST(root.right, node);。你正确地进行了旋转（如果你在旋转之后查看 this.root，它看起来不错），但是你 return 值为 29 的节点并将其分配给 root.right!

Answer 2

下次试试。 :)

你需要 return removeBST 什么吗？我认为你不需要，因为当你进行旋转和其他智能操作时，你确实修改了相应的节点。

所以不要写root.left = this.removeBST(root.left, node)，只要写this.removeBST(root.left, node)然后对右边的child做同样的事情。此外，只需在 remove 中调用 this.removeBST，但不要重新分配 this.root。它似乎适用于该示例，但我可能会遗漏一些您真正需要它的其他情况。 (code)

红黑树 - JavaScript 中的删除方法

Red-Black Tree - Deletion method in JavaScript

javascript

recursion

red-black-tree

data-structures