RedBlackTree

RedBlackTree.js

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

  insert(value) {
    // Define an inner helper function for the recursive insertion
    const insertHelper = (node) => {
      // The current node we're considering
      const currNode = node

      // If the value to insert is less than the value of the current node
      if (value < currNode.value) {
        // If a left child node exists, recursively call 'insertHelper' on it
        if (currNode.left) {
          insertHelper(currNode.left)
        } else {
          // If no left child node exists, create a new node with the value
          // Make the new node a left child of the current node
          // The color of the new node is red by default (from the RBTNode constructor)
          currNode.left = new RBTNode(value)
          // Set the parent of the new node to be the current node
          currNode.left.parent = currNode
          // Call the helper method '_insertFixup' to maintain Red-Black Tree properties after insertion
          this._insertFixup(currNode.left)
        }
      } else if (value > currNode.value) {
        // If the value to insert is greater than the value of the current node
        // If a right child node exists, recursively call 'insertHelper' on it
        if (currNode.right) {
          insertHelper(currNode.right)
        } else {
          // If no right child node exists, create a new node with the value
          // Make the new node a right child of the current node
          // The color of the new node is red by default (from the RBTNode constructor)
          currNode.right = new RBTNode(value)
          // Set the parent of the new node to be the current node
          currNode.right.parent = currNode
          // Call the helper method '_insertFixup' to maintain Red-Black Tree properties after insertion
          this._insertFixup(currNode.right)
        }
      }
      // If the value is equal to the current node's value, we do nothing because
      // duplicates are not typically allowed in binary search trees
    }

    // If the tree is empty (no root node)
    if (!this.root) {
      // Create a new root node with the value
      // The color of the new root node is red by default (from the RBTNode constructor)
      this.root = new RBTNode(value)
      // Call the helper method '_insertFixup' to maintain Red-Black Tree properties after insertion
      // In this case, it will simply recolor the root to black
      this._insertFixup(this.root)
    } else {
      // If the tree is not empty, call the 'insertHelper' function on the root node
      insertHelper(this.root)
    }
  }

  // Helper method to maintain tree balance after an insertion
  _insertFixup(node) {
    // Start with the node that was just inserted
    let currNode = node

    // While the parent of the current node is red and the grandparent exists
    // This loop maintains the property that no two red nodes will be adjacent
    while (this._isRed(currNode.parent) && currNode.parent.parent) {
      // Define some helper variables to make the code more readable
      const { parent } = currNode
      const grandparent = parent.parent

      // If the parent of the current node is a left child
      if (parent === grandparent.left) {
        // If the uncle (the right child of the grandparent) is red
        if (this._isRed(grandparent.right)) {
          // Flip the colors of the parent, grandparent, and uncle
          // This maintains the property that every path from a node to its descendant leaves contains the same number of black nodes
          this._flipColor(grandparent)
        } else {
          // If the uncle is black or null
          // If the current node is a right child, do a left rotation to make it a left child
          // This is done to prevent two red nodes from being adjacent
          if (currNode === parent.right) {
            this._leftRotation(parent)
            // After the rotation, the current node and its parent are swapped
            currNode = parent
          }
          // Perform a right rotation on the grandparent
          // This makes the former parent (a red node) the parent of its former parent (a black node)
          // This maintains the property that every path from a node to its descendant leaves contains the same number of black nodes
          this._rightRotation(grandparent)
        }
      } else {
        // The mirror case when the parent of the current node is a right child
        // The code is the same except that 'left' and 'right' are exchanged
        if (this._isRed(grandparent.left)) {
          this._flipColor(grandparent)
          currNode = grandparent
        } else {
          if (currNode === parent.left) {
            this._rightRotation(parent)
            currNode = parent
          }
          this._leftRotation(grandparent)
        }
      }
      // Move up the tree
      currNode = grandparent
    }
    // Ensure the root is always black to maintain the black-root property
    this.root.color = NodeColor.BLACK
  }

  delete(value, node = this.root) {
    // Search the tree to find the target node
    const targetNode = this.search(value, node)

    // If the target node is not found, return false
    if (!targetNode) {
      return false
    }

    // If the target node has no children (leaf node)
    if (!targetNode.left && !targetNode.right) {
      // If the target node is red, simply remove it by replacing it with null in its parent
      // Red nodes can be removed freely because removing them doesn't affect the black height property
      if (this._isRed(targetNode)) {
        this._replaceParent(targetNode, null)
      } else {
        // If the target node is black, removal would affect black height property
        // Hence, we need to call '_deleteFixup' to fix the potential violations
        this._deleteFixup(targetNode)
        // After that, we can remove the black node
        this._replaceParent(targetNode, null)
      }
    } else if (!targetNode.left || !targetNode.right) {
      // If the target node has only one child (unilateral subtree)
      if (targetNode.left) {
        // If the child is on the left, set the child's color to black
        // The color is set to black to maintain the black height property
        targetNode.left.color = NodeColor.BLACK
        // Update the parent pointer of the child
        targetNode.left.parent = targetNode.parent
        // Replace the target node with its child
        this._replaceParent(targetNode, targetNode.left)
      } else {
        // Similar operations for the right child
        targetNode.right.color = NodeColor.BLACK
        targetNode.right.parent = targetNode.parent
        this._replaceParent(targetNode, targetNode.right)
      }
    } else {
      // If the target node has two children
      // Find the node with the smallest value that is larger than the value of the target node (aux)
      // This node is used to replace the target node
      const aux = this.findMin(targetNode.right)
      // Replace the value of the target node with the value of the aux node
      targetNode.value = aux.value
      // Delete the aux node recursively
      // The aux node will have at most one child, so this deletion is easier
      this.delete(aux.value, targetNode.right)
    }
    // Return the root of the tree after deletion
    return this.root
  }

  // Helper method to maintain tree balance after a deletion
  _deleteFixup(node) {
    // 'currNode' is the node to be fixed
    let currNode = node

    // Loop until 'currNode' is the root or 'currNode' is red
    while (currNode !== this.root && !this._isRed(currNode)) {
      // Get the parent of 'currNode'
      const { parent } = currNode
      // Define 'sibling', which will be the sibling of 'currNode'
      let sibling

      // If 'currNode' is a left child
      if (currNode === parent.left) {
        // 'sibling' is the right child of 'parent'
        sibling = parent.right

        // If the 'sibling' is red
        if (this._isRed(sibling)) {
          // Perform left rotation on 'parent'
          this._leftRotation(parent)
        }
        // If both children of 'sibling' are black
        else if (!this._isRed(sibling.left) && !this._isRed(sibling.right)) {
          // If 'parent' is red
          if (this._isRed(parent)) {
            // Swap colors of 'parent' and 'sibling'
            parent.color = NodeColor.BLACK
            sibling.color = NodeColor.RED
            // Fixup is done because 'currNode' now has an additional black link
            break
          }
          // If 'parent' is black, make 'sibling' red
          sibling.color = NodeColor.RED
          // Move up the tree
          currNode = parent
        }
        // If 'sibling's left child is red and right child is black
        else if (this._isRed(sibling.left) && !this._isRed(sibling.right)) {
          // Perform right rotation on 'sibling'
          this._rightRotation(sibling)
        }
        // If 'sibling's right child is red
        else {
          // Perform left rotation on 'parent'
          this._leftRotation(parent)
          // Change color of 'parent' and 'sibling's right child to black
          parent.color = NodeColor.BLACK
          sibling.right.color = NodeColor.BLACK
          // Fixup is done because 'currNode' now has an additional black link
          break
        }
      }
      // If 'currNode' is a right child, similar operations are performed with 'left' and 'right' interchanged
      else {
        sibling = parent.left
        if (this._isRed(sibling)) {
          this._rightRotation(parent)
        } else if (!this._isRed(sibling.left) && !this._isRed(sibling.right)) {
          if (this._isRed(parent)) {
            parent.color = NodeColor.BLACK
            sibling.color = NodeColor.RED
            break
          }
          sibling.color = NodeColor.RED
          currNode = parent
        } else if (this._isRed(sibling.right) && !this._isRed(sibling.left)) {
          this._leftRotation(sibling)
        } else {
          this._rightRotation(parent)
          parent.color = NodeColor.BLACK
          sibling.left.color = NodeColor.BLACK
          break
        }
      }
    }
  }

  search(value, node = this.root) {
    // Check if the current node is null (reached a leaf node or an empty tree)
    if (!node) {
      // Value not found, return false
      return false
    }
    // Check if the current node's value matches the search value
    if (value === node.value) {
      // Value found, return the node
      return node
    }
    // If the search value is less than the current node's value, go to the left subtree
    if (value < node.value) {
      // Recursively call the search function on the left child node
      return this.search(value, node.left)
    }
    // If the search value is greater than the current node's value, go to the right subtree
    // This assumes the tree follows the convention of left child nodes having lesser values and right child nodes having greater values
    return this.search(value, node.right)
  }

  /*
  This method is used to replace the parent of a given node with a new node. It is primarily used during node deletion and rotation operations. When a node is deleted or when rotations are performed, it may be necessary to update the parent reference of a child node to point to a new node.
  */
  _replaceParent(currNode, newNode) {
    // Get the parent node of the current node
    const { parent } = currNode
    // Check if the current node is the root node (no parent)
    if (!parent) {
      // If so, set the new node as the new root of the tree
      this.root = newNode
    }
    // If the current node is the left child of its parent
    else if (currNode === parent.left) {
      // Set the new node as the left child of the parent
      parent.left = newNode
    }
    // If the current node is the right child of its parent
    else {
      // Set the new node as the right child of the parent
      parent.right = newNode
    }
  }

  /*
  A helper method that performs a left rotation on the tree structure.
  
  Left rotation is an operation that repositions the nodes in the tree 
  to maintain its properties when they have been disturbed, for example, during insertion or deletion. 
  
  It is used when the right child of a node is colored red. The operation involves repositioning 
  the node and its right child, and updating the colors of the nodes accordingly. After a left rotation, the 
  former parent becomes the left child of its former right child. 

  This method should be called when it is safe to do a left rotation, that is, when the right child is not null.
  */
  _leftRotation(node) {
    // 'currNode' is set as the right child of 'node'
    const currNode = node.right

    // The left child of 'currNode' becomes the right child of 'node'
    node.right = currNode.left

    // 'node' becomes the left child of 'currNode'
    currNode.left = node

    // The color of 'currNode' is set as the color of 'node'
    currNode.color = node.color

    // The color of 'node' is set as red
    node.color = NodeColor.RED

    // The parent of 'node' is replaced with 'currNode'
    this._replaceParent(node, currNode)

    // The parent of 'currNode' is set as the parent of 'node'
    currNode.parent = node.parent

    // 'node' becomes the child of 'currNode'
    node.parent = currNode

    // If 'node' has a right child, the parent of the right child is set as 'node'
    if (node.right) {
      node.right.parent = node
    }
  }

  /*
  A helper method that performs a right rotation on the tree structure.

  Right rotation is an operation that repositions the nodes in the tree 
  to maintain its properties when they have been disturbed, for example, during insertion or deletion. 

  It is used when the left child of a node is colored red. The operation involves repositioning 
  the node and its left child, and updating the colors of the nodes accordingly. After a right rotation, the 
  former parent becomes the right child of its former left child.

  This method should be called when it is safe to do a right rotation, that is, when the left child is not null.
  */
  _rightRotation(node) {
    // 'currNode' is set as the left child of 'node'
    const currNode = node.left

    // The right child of 'currNode' becomes the left child of 'node'
    node.left = currNode.right

    // 'node' becomes the right child of 'currNode'
    currNode.right = node

    // Update color: The color of 'currNode' is set as the color of 'node'
    currNode.color = node.color

    // The color of 'node' is set as red
    node.color = NodeColor.RED

    // Update parent node: The parent of 'node' is replaced with 'currNode'
    this._replaceParent(node, currNode)

    // The parent of 'currNode' is set as the parent of 'node'
    currNode.parent = node.parent

    // 'node' becomes the child of 'currNode'
    node.parent = currNode

    // If 'node' has a left child, the parent of the left child is set as 'node'
    if (node.left) {
      node.left.parent = node
    }
  }

  /*
  Helper method that changes the color of a node and its children.
  The concept here is to change the color of the parent node to red, and the color of the two child nodes to black.
  This color flip is part of the process that helps to maintain the properties of a Red-Black Tree, which include keeping the tree balanced and ensuring that no two red nodes are adjacent, among others.
  Please note that before calling this method, you should check that both children of the node are present and their colors are red. This method assumes this condition is met.
  */
  _flipColor(node) {
    // The color of the current node is set to RED
    node.color = NodeColor.RED

    // The color of the left child of the current node is set to BLACK
    node.left.color = NodeColor.BLACK

    // The color of the right child of the current node is set to BLACK
    node.right.color = NodeColor.BLACK
  }

  // Helper method to check the node color
  _isRed(node) {
    return node ? node.color === NodeColor.RED : false
  }

  // Helper method that finds the node with the smallest value in the tree. It's used during the delete operation to find the successor of a node that's being deleted.
  findMin(node = this.root) {
    let currentNode = node
    while (currentNode && currentNode.left) {
      currentNode = currentNode.left
    }
    return currentNode
  }

  // Displays an array that will represent the tree
  // in level-order, with each sub-array representing a level of the tree.
  levelOrderTraversal() {
    // Create an empty array to store the traversed nodes
    const temp = []
    // Create an array to keep track of the current level of nodes
    const queue = []

    // If the tree has a root, add it to the queue
    if (this.root) {
      queue.push(this.root)
    }

    // Keep traversing the tree while there are nodes in the queue
    while (queue.length) {
      // Create an array to store the nodes of the current level
      const subTemp = []
      // Store the number of nodes in the current level
      const len = queue.length

      // Iterate through the current level of nodes
      for (let i = 0; i < len; i += 1) {
        // Dequeue the first node in the queue
        const node = queue.shift()
        // Push the node's value to the subTemp array
        subTemp.push(node.value)
        // If the node has a left child, add it to the queue
        if (node.left) {
          queue.push(node.left)
        }
        // If the node has a right child, add it to the queue
        if (node.right) {
          queue.push(node.right)
        }
      }

      // Push the subTemp array to the temp array
      temp.push(subTemp)
    }
    // Return the final temp array
    return temp
  }
}

export default RedBlackTree