Red-Black Tree

Red - Black Tree is another variant of Binary Search Tree in which every node is colored either RED or BLACK. We can define a Red Black Tree as follows...

Red Black Tree is a Binary Search Tree in which every node is colored either RED or BLACK.

In Red Black Tree, the color of a node is decided based on the properties of Red-Black Tree. Every Red Black Tree has the following properties.

Properties of Red Black Tree

• Property #1: Red - Black Tree must be a Binary Search Tree.

• Property #2: The ROOT node must be colored BLACK.

• Property #3: The children of Red colored node must be colored BLACK. (There should not be two consecutive RED nodes).

• Property #4: In all the paths of the tree, there should be same number of BLACK colored nodes.

• Property #5: Every new node must be inserted with RED color.

• Property #6: Every leaf (e.i. NULL node) must be colored BLACK.

Example

Following is a Red-Black Tree which is created by inserting numbers from 1 to 9.

The above tree is a Red-Black tree where every node is satisfying all the properties of Red-Black Tree.

---

Every Red Black Tree is a binary search tree but every Binary Search Tree need not be Red Black tree.

---

Insertion into RED BLACK Tree

In a Red-Black Tree, every new node must be inserted with the color RED. The insertion operation in Red Black Tree is similar to insertion operation in Binary Search Tree. But it is inserted with a color property. After every insertion operation, we need to check all the properties of Red-Black Tree. If all the properties are satisfied then we go to next operation otherwise we perform the following operation to make it Red Black Tree.

• 1. Recolor

• 2. Rotation

• 3. Rotation followed by Recolor

The insertion operation in Red Black tree is performed using the following steps...

• Step 1 - Check whether tree is Empty.

• Step 2 - If tree is Empty then insert the newNode as Root node with color Black and exit from the operation.

• Step 3 - If tree is not Empty then insert the newNode as leaf node with color Red.

• Step 4 - If the parent of newNode is Black then exit from the operation.

• Step 5 - If the parent of newNode is Red then check the color of parentnode's sibling of newNode.

• Step 6 - If it is colored Black or NULL then make suitable Rotation and Recolor it.

• Step 7 - If it is colored Red then perform Recolor. Repeat the same until tree becomes Red Black Tree.

Example

Deletion Operation in Red Black Tree

The deletion operation in Red-Black Tree is similar to deletion operation in BST. But after every deletion operation, we need to check with the Red-Black Tree properties. If any of the properties are violated then make suitable operations like Recolor, Rotation and Rotation followed by Recolor to make it Red-Black Tree.

class Node {
  constructor(value, color) {
    this.value = value;
    this.color = color;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

class RedBlackTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value, "red");
    if (!this.root) {
      this.root = newNode;
    } else {
      this._insertNode(this.root, newNode);
    }
    this._fixInsertViolation(newNode);
  }

  _insertNode(root, newNode) {
    if (newNode.value < root.value) {
      if (root.left === null) {
        root.left = newNode;
        newNode.parent = root;
      } else {
        this._insertNode(root.left, newNode);
      }
    } else {
      if (root.right === null) {
        root.right = newNode;
        newNode.parent = root;
      } else {
        this._insertNode(root.right, newNode);
      }
    }
  }

  _fixInsertViolation(node) {
    while (node !== this.root && node.parent.color === "red") {
      let parent = node.parent;
      let grandParent = parent.parent;
      if (parent === grandParent.left) {
        let uncle = grandParent.right;
        if (uncle && uncle.color === "red") {
          parent.color = "black";
          uncle.color = "black";
          grandParent.color = "red";
          node = grandParent;
        } else {
          if (node === parent.right) {
            this._rotateLeft(parent);
            node = parent;
            parent = node.parent;
          }
          parent.color = "black";
          grandParent.color = "red";
          this._rotateRight(grandParent);
        }
      } else {
        let uncle = grandParent.left;
        if (uncle && uncle.color === "red") {
          parent.color = "black";
          uncle.color = "black";
          grandParent.color = "red";
          node = grandParent;
        } else {
          if (node === parent.left) {
            this._rotateRight(parent);
            node = parent;
            parent = node.parent;
          }
          parent.color = "black";
          grandParent.color = "red";
          this._rotateLeft(grandParent);
        }
      }
    }
    this.root.color = "black";
  }

  _rotateLeft(node) {
    let rightChild = node.right;
    node.right = rightChild.left;
    if (rightChild.left !== null) {
      rightChild.left.parent = node;
    }
    rightChild.parent = node.parent;
    if (node.parent === null) {
      this.root = rightChild;
    } else if (node === node.parent.left) {
      node.parent.left = rightChild;
    } else {
      node.parent.right = rightChild;
    }
    rightChild.left = node;
    node.parent = rightChild;
  }

  _rotateRight(node) {
    let leftChild = node.left;
    node.left = leftChild.right;
    if (leftChild.right !== null) {
      leftChild.right.parent = node;
    }
    leftChild.parent = node.parent;
    if (node.parent === null) {
      this.root = leftChild;
    } else if (node === node.parent.right) {
      node.parent.right = leftChild;
    } else {
      node.parent.left = leftChild;
    }
    leftChild.right = node;
    node.parent = leftChild;
  }

  search(value) {
    return this._searchNode(this.root, value);
  }

  _searchNode(node, value) {
    if (node === null) return false;
    if (node.value === value) return true;
    if (value < node.value) {
      return this._searchNode(node.left, value);
    } else {
      return this._searchNode(node.right, value);
    }
  }
}

// Example usage:
const rbTree = new RedBlackTree();
rbTree.insert(10);
rbTree.insert(5);
rbTree.insert(15);
console.log(rbTree.search(5)); // Output: true
console.log(rbTree.search(20)); // Output: false