Red-Black Tree - Deletion method in JavaScript

Question

See original Red-Black Tree below:

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

I am having trouble when trying to the delete 29. Since trying to delete this node results in a double-black (let's call it DB) case and DB's far nephew (5R) node is a RED node, we should be able to solve this by simply swapping the colors of parent (10R) and sibling (7B) nodes, rotating DB's parent in DB's direction and coloring DB's nephew BLACK, so the result would be:

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

But instead I'm getting the following:

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

See code below, remove(value) calls removeBST(root,value) that calls fixDoubleBlack() if needed. Since it is a lengthy code, I've omitted the non-related part, but I've posted the code here. I know this may take some time and it is a lot to ask so thanks a lot to anyone who bothers to take a look. I sure got a couple of years older trying to debug this.

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();

As mentioned above, calling levelOrderTraversal() after the fixDoubleBlack() call shows the correct result, so I'm left with the thought that it might be the removeBST return statement.

Hanna G&#225;bor · Accepted Answer

Next try. :)

Do you need to return anything by removeBST? I think you don't, because you do modify the corresponding nodes when you do the rotations and other smart things.

So instead of root.left = this.removeBST(root.left, node), just write this.removeBST(root.left, node) and do the same with the right child. Also, just call this.removeBST in remove, but don't reassign this.root. It seems to work on the example, but I might be missing some other case where you really need it. (code)

Red-Black Tree - Deletion method in JavaScript

Answers (2)

Related Questions