The creation and use of binary tree and binary tree search tree were introduced before. Next, we will continue to learn more about trees.
The problem with BST is that when we add the number of nodes many times, it may result in a situation where one edge of the tree may be very deep, with many layers, while the other branch has only a few layers. Some performance problems may arise when we need to add, remove, and search a node. In order to solve these problems, we study the self-balancing tree. There are two kinds of self-balancing trees: AVL tree and red-black tree.

Self-balancing tree

Preparing knowledge

Node Height and Balance Factor

Node height: the maximum value from the other side of the node to any sub-node. This is relatively easy to understand. Then the code to get the node height is implemented as follows:

getNodeHeight(node) {
    if (node == null) {
      return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
  }

Equilibrium factor: The difference between the left subtree height and the right subtree height of each node. When the value is 0, -1 and 1, it is normal, indicating that the binary tree has been balanced. If the value is not one of the three values, the tree needs to be balanced. Following the code for calculating the equilibrium factor of a node and returning its value is as follows:

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
getBalanceFactor(node) {
    const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDifference) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
  }

AVL tree

AVL tree is a self-balancing tree. When adding or removing nodes, AVL will try to maintain self-balancing, that is, it may try to convert to a full tree. Next, we introduce the self-balancing operation of the balance tree, AVL rotation.

AVL Rotation

After adding or removing nodes to AVL, we need to calculate the height of the nodes and verify whether the balance is needed. Rotation operation can be divided into single rotation and double rotation.

Left-left LL (single right rotation)

/**
   * Left left case: rotate right
   *
   *       b                           a
   *      / \                         / \
   *     a   e -> rotationLL(b) ->   c   b
   *    / \                             / \
   *   c   d                           d   e
   *
   * @param node Node<T>
   */
rotationLL(node){
    const tmp = node.right;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
}

Right-right RR (single left rotation)

/**
   * Right right case: rotate left
   *
   *     a                              b
   *    / \                            / \
   *   c   b   -> rotationRR(a) ->    a   e
   *      / \                        / \
   *     d   e                      c   d
   *
   * @param node Node<T>
   */
  rotationLL(node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  }

Left-right (LR): Double rotation to the right

/**
   * Left right case: rotate left then right
   * @param node Node<T>
   */
  rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }

Right-left (RL): Double rotation to the left

/**
   * Right left case: rotate right then left
   * @param node Node<T>
   */
  rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationRR(node);
  }

After learning the balancing operation (rotation), let's perfect the operation of adding or removing nodes from AVL tree.

Adding Nodes

insert(key) {
    this.root = this.insertNode(this.root, key);
  }

  insertNode(node, key) {
    if (node == null) {
      return new Node(key);
    } if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, key);
    } else {
      return node; // duplicated key
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
        // Left left case
        node = this.rotationLL(node);
      } else {
        // Left right case
        return this.rotationLR(node);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
        // Right right case
        node = this.rotationRR(node);
      } else {
        // Right left case
        return this.rotationRL(node);
      }
    }
    return node;
  }

Remove Nodes

 removeNode(node, key) {
    node = super.removeNode(node, key); // {1}
    if (node == null) {
      return node;
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // Left left case
      if (
        this.getBalanceFactor(node.left) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
      ) {
        return this.rotationLL(node);
      }
      // Left right case
      if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationLR(node.left);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // Right right case
      if (
        this.getBalanceFactor(node.right) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
      ) {
        return this.rotationRR(node);
      }
      // Right left case
      if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationRL(node.right);
      }
    }
    return node;
  }
}

The above is about the basic knowledge of AVL tree. Next, we introduce another balance tree, red-black tree.
Like AVL tree, red-black tree is a self-balanced binary tree. Mangrove trees are essentially AVL trees, but they can include multiple inserts and deletions. In a red-black tree, each node follows the following rules:

1. As the name implies, each node is either red or black.
2. The root node of the tree is black.
3. All leaf nodes are black.
4. If a node is red, then both of its children are black.
5. There can not be two adjacent red nodes, a red node can not have a red parent or child node;
6. All paths from a given node to its descendant node (NULL leaf node) contain the same number of black nodes.

red-black tree

Creating the skeleton of the red-black tree

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
//Define color classes
const Colors = {
  RED:'red',
  BLACK:'black'
};
//Node Types for Creating Red-Black Trees
class RedBlackNode extends Node{
  constructor(key){
    super(key);
    this.key = key;
    this.color = Colors.RED;
    this.parent = null;
  }
  isRed(){
    return this.color === Colors.RED;
  }
};
class RedBlackTree extends BinarySearchTree{
  constructor(compareFn = defaultCompare){
    super(compareFn);
    this.compareFn = compareFn;
    this.root = null;
  };
}

Rotation operation

Right single rotation

 //rotationLL
  static rotationLL(node){
    const tmp = node.left;
    node.left = tmp.right;
    if(tmp.right && tmp.right.key){
      tmp.right.parent = node;
    }
    tmp.right.parent = node.parent;
    if (!node.parent){
      this.root = tmp;
    }else{
      if(node === node.parent.left){
        node.parent.left = tmp;
      }else{
        node.parent.right = tmp;
      }
      tmp.right = node;
      node.parent = tmp;
    }
  };

Left single rotation

//rotationRR
  static rotationRR(node){
    const tmp = node.right;
    node.right = tmp.left;
    if (tmp.left && tmp.left.key){
      tmp.left.parent = node;
    }
    tmp.parent = node.parent;
    if (!node.parent){
      this.root = tmp;
    }else{
      if(node === node.parent.left){
        node.parent.left = tmp;
      }else{
        node.parent.right = tmp;
      }
    }
    tmp.left = node;
    node.parent = tmp;
  }

Verify node color attributes

 //Verify the properties of the red-black tree after inserting nodes
  static fixTreeProperties(node){
    while (node && node.parent && node.parent.color.isRed() && node.color !== Colors.BLACK){
      let parent = node.parent;
      const grandParent = parent.parent;
      //case A: The parent node is the left child node
      if (grandParent && grandParent.left === parent){
        const uncle = grandParent.right;
        //case 1A: Uncle nodes are also red - just need to refill
        if (uncle && uncle.color === Colors.RED){
          grandParent.color = Colors.RED;
          parent.color  = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        }else{
          // case 2A: The node is the right child node - right rotation
          if (node === parent.left){
            RedBlackTree.rotationRR(parent);
            node = parent;
            parent = node.parent;
          }
          //case 3A: The child node is the left child node - left rotation
          else if(node === parent.right){
            RedBlackTree.rotationRR(grandParent);
            parent.color = Colors.BLACK;
            grandParent.color = Colors.RED;
            node = parent;
          }
        }
      }
      //case B: The parent is the right child
      else{
        const uncle = grandParent.left;
        //Case 1B: Uncle node is red -- just need to refill
        if(uncle && uncle.color === Colors.RED){
          grandParent.color = Colors.RED;
          parent.color = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        }
        //Case 2B: The node is the left child node - right rotation
        if (node === parent.left){
          RedBlackTree.rotationLL(parent);
          node = parent;
          parent = node.parent;
        }
        //Case 3B: The node is the right child - left rotation
        else if(node === parent.right){
          RedBlackTree.rotationRR(grandParent);
          parent.color = Colors.BLACK;
          grandParent.color = Colors.RED;
          node = parent;
        }
      }
      this.root.color = Colors.BLACK;
    }
  }

Add new nodes

 //Insert new nodes into the red-black tree
  insertNode(node,key){
    if(this.compareFn(key,node.key) === Compare.LESS_THAN){
      if(node.left === null){
        node.left = new RedBlackNode(key);
        node.left.parent = node;
        return node.left;
      }
      else{
        return this.insertNode(node.left,key);
      }
    }
    else if(node.right === null){
      node.right = new RedBlackNode(key);
      node.right.parent = node;
      return node.right;
    }
  };
  insert(key) {
    if (this.root === null){
      this.root = new RedBlackNode(key);
      this.root.color = Colors.BLACK;
    }else{
      const newNode = this.insertNode(this.root, key);
      RedBlackTree.fixTreeProperties(newNode);
    }
  };