Learning JavaScript Data Structures and Algorithms - Third Edition

Inserting a node in the Red-Black tree

Inserting a node in a Red-Black tree works the same way as in BST. In addition to inserting the code, we will also apply a color to the node and after the insertion, we will verify whether the tree still meets the rules of the Red-Black tree and that it is still balanced.

The following code inserts a new node in a Red-Black tree:

insert(key: T) {
  if (this.root == null) { // {1}
    this.root = new RedBlackNode(key); // {2}
    this.root.color = Colors.BLACK; // {3}
  } else {
    const newNode = this.insertNode(this.root, key); // {4}
    this.fixTreeProperties(newNode); // {5}
  }
}

If the tree is empty ({1}), then we will create a new Red-Black tree node ({2}) and to comply with rule 2, we will set the root color as black ...