TypeScript data structures and algorithms: red-black trees

The previous article “TypeScript Data Structures and Algorithms: AVL Trees” implemented the data structures and algorithms of self-balancing AVL trees in TypeScript, and this article continues to implement even better red-black trees.

Although AVL tree has achieved the balance of binary search tree, it is complicated and time-consuming because every time a node is added or deleted, the rebalance operation will be involved. So in industrial applications, will use another approximate balanced tree algorithm red black tree to achieve.

This time it was longer because red black trees took me a lot of time to learn and understand. This is the most difficult data structure code I have encountered so far. Although I understand the principle now, I still can’t write it when I write it offline. And there is one big difference between red-black trees and other data structures: ordinary data structures are designed, but red-black trees are mathematical models derived from 2-3 trees.

I’m not going to go over the classic derivation, but if you’re interested, you can read the fourth Edition of Algorithms on pages 269 to 292, which describes in detail how 2-3 trees are self-balanced and how 2-3 trees are mapped to the equivalent left-leaning red-black trees. It’s worth noting that the book’s author, Robert Sedgewick, was the inventor of the red-black tree. After learning, I have several profound experiences:

1. For the 2-3 treeequivalentThe red black tree, due to the 2-3 treeTrigeminal nodeHas been to3 个Binary node treeSo in a red black treeredThe color means that this is in two or three treesTrigeminal node.
2. AVL treeIs close toThe log ₂ N; for2-3 treeSince the node can bebinaryortrigeminalSo the height will not exceed the equilibriumThe log ₂ NIt can’t be lower than thatThe log ₃ N; And for2-3 treeequivalentRed and black treeAs a result ofTrigeminal nodeHas been toLayer 2So the height will not exceed the equilibrium2 the log ₂ N.
3. The key point is, if you see a red black treeRed nodes(link), don’t think of it as a child node, just stretch it out and you’ll understand2-3 treeandLeft-leaning red black tree, as shown in the figure below:

In addition, the left-leaning red-black tree has some other inferred properties:

• redLinks areOn the leftLinks;
• There is noAny nodeIt's connected to two red links at once(That is, the red nodeNot adjacentorIs the sibling node);
• The tree isPerfect black balance, that is, there is the same number of black links on any empty link path to the root node (that is, after the red is smoothed out, the height of each leaf node cannot differ by more than one1).

I will not go into details about the algorithm implementation process of red black trees. According to my understanding, the TypeScript code of the fourth edition of the algorithm is as follows:

Red black tree code

Node class

The Node class RedBlackNode inherits the Node class Node of the binary search tree previously implemented:

import { Node } from "./node";

// Node color enumeration value
export enum Colors {
  RED = 0,
  BLACK = 1
}

// Red-black tree Node, inherited from normal Node
export class RedBlackNode<K> extends Node<K> {
  left: RedBlackNode<K>;
  right: RedBlackNode<K>;
  // Red-black tree nodes have the color special attribute
  color: Colors;

  constructor(public key: K) {
    super(key);
    // The default color of the node is red
    this.color = Colors.RED;
  }

  / * * *@description: Returns whether the node is red */
  isRed(): boolean {
    return this.color === Colors.RED;
  }

  / * * *@description: bit operation reverses the node color */
  flipColor() {
    this.color = 1 ^ this.color; }}Copy the code

Red and black tree class

Similarly, the red-black tree class RedBlackTree is also inherited from the BinarySearchTree class BinarySearchTree. In the implementation of RedBlackTree code, reference algorithm four has been implemented in the RedBlackTree class JAVA code.

import { defaultCompare, ICompareFunction, Compare } from ".. /util";
import BinarySearchTree from "./binary-search-tree";
import { RedBlackNode, Colors } from "./models/red-black-node";

export default class RedBlackTree<T> extends BinarySearchTree<T> {
  protected root: RedBlackNode<T>;

  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
    super(compareFn);
  }

  /** * dextral * / \ / \ * c b -> rotateRight(a) -> d a * / \ / \ * d e e b **@param node Node<T>
   */
  private rotateRight(node: RedBlackNode<T>): RedBlackNode<T> {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    tmp.color = node.color;
    node.color = Colors.RED;
    return tmp;
  }

  / * * * l * * b / \ \ d * * d - > rotateLeft (b) - > b e * / \ \ e a c * * * c@param node Node<T>
   */
  private rotateLeft(node: RedBlackNode<T>): RedBlackNode<T> {
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    tmp.color = node.color;
    node.color = Colors.RED;
    return tmp;
  }

  / * * *@description: Insert key */
  insert(key: T) {
    this.root = this.insertNode(this.root, key);
    this.root.color = Colors.BLACK;
  }

  / * * *@descriptionRecursive method for inserting keys */
  protected insertNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
    // Insert a red node if it is inserted at a blank node
    if (node == null) {
      let node = new RedBlackNode(key);
      node.color = Colors.RED;
      return node;
    }

    / / recursive points
    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 {
      node.key = key;
    }

    return this.balance(node);
  }
  /** * removes the minimum key */
  public deleteMin() {
    if (this.root) return;

    // If the left and right sides of the root node are black, set the root node to red
    if (!this.isRed(this.root.left) && !this.isRed(this.root.right))
      this.root.color = Colors.RED;

    // Call the recursive method that removes the minimum key
    this.root = this.deleteMinNode(this.root);
    // Change the root node color to black
    if (this.root) this.root.color = Colors.BLACK;
  }

  / * * *@description: the recursive method to remove the minimum key */
  private deleteMinNode(node: RedBlackNode<T>): RedBlackNode<T> {
    // Baseline conditions
    if (node.left == null) return null;

    // If the left and right nodes are black, moveRedLeft is called
    if (!this.isRed(node.left) && !this.isRed(node.left.left))
      node = this.moveRedLeft(node);

    // Recursive calls to find the minimum key
    node.left = this.deleteMinNode(node.left);
    // Nodes are balanced after each recursion
    return this.balance(node);
  }

  /** * removes the maximum key */
  public deleteMax() {
    if (!this.root) return;

    // If all the children of the root node are black, set the root node to red
    if (!this.isRed(this.root.left) && !this.isRed(this.root.right))
      this.root.color = Colors.RED;

    // Call the recursive method that removes the largest node
    this.root = this.deleteMaxNode(this.root);
    // Correct the root node color to black
    if (this.root) this.root.color = Colors.BLACK;
  }

  / * * *@description: the recursive method to delete the maximum key node */
  private deleteMaxNode(node: RedBlackNode<T>): RedBlackNode<T> {
    // If the left child node is red, it is right-handed
    if (this.isRed(node.left)) node = this.rotateRight(node);

    // Baseline conditions
    if (node.right == null) return null;

    // If the left and right nodes are black, then moveRedRight is called
    if (!this.isRed(node.right) && !this.isRed(node.right.left))
      node = this.moveRedRight(node);

    // Find the maximum key recursively
    node.right = this.deleteMaxNode(node.right);

    // Nodes are balanced after each recursion
    return this.balance(node);
  }

  / * * *@description: Deletes the specified key */
  public delete(key: T) {
    // Return if there is no node
    if (!this.search(key)) return;

    // If all the children of the root node are black, set the root node to red
    if (!this.isRed(this.root.left) && !this.isRed(this.root.right))
      this.root.color = Colors.RED;

    // Call the recursive method to delete the node
    this.root = this.deleteNode(this.root, key);
    // Correct the root node color to black
    if (this.root) this.root.color = Colors.BLACK;
  }

  / * * *@description: Deletes the recursive method */ of the specified node
  private deleteNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
    // If key is smaller than the current node
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (!this.isRed(node.left) && !this.isRed(node.left? .left)) node =this.moveRedLeft(node);
      // Continue the recursion
      node.left = this.deleteNode(node.left, key);
      // If the key is not less than the current node
    } else {
      if (this.isRed(node.left)) node = this.rotateRight(node);

      // The corresponding node is found and the right child node is empty
      if (
        this.compareFn(key, node.key) === Compare.EQUALS &&
        node.right == null
      )
        return null;

      // If the left and right nodes are black, then moveRedRight is called
      if (!this.isRed(node.right) && !this.isRed(node.right? .left)) node =this.moveRedRight(node);

      // Find the corresponding node, and the right child node is not empty
      if (this.compareFn(key, node.key) === Compare.EQUALS) {
        const x = this.minNode(node.right);
        node.key = x.key;
        node.right = this.deleteMinNode(node.right);
        // Continue recursion is not found
      } else {
        // Do not find the corresponding node, continue recursion
        node.right = this.deleteNode(node.right, key); }}// Nodes are balanced after each recursion
    return this.balance(node);
  }

  / * * *@description: Returns the root node */
  getRoot(): RedBlackNode<T> {
    return this.root;
  }

  / * * *@description: Corrects the node color */
  private flipColors(node: RedBlackNode<T>) {
    node.flipColor();
    node.left.flipColor();
    node.right.flipColor()
  }

  / * * *@description: Balance tree */
  private balance(node: RedBlackNode<T>): RedBlackNode<T> {
    // Core algorithm, through three lines of judgment, to generate a left red black tree
    // Right red left black, left turn the red link to the left
    if (this.isRed(node.right) && !this.isRed(node.left))
      node = this.rotateLeft(node);
    // Left red and left left red, right rotation
    if (this.isRed(node.left) && this.isRed(node.left? .left)) node =this.rotateRight(node);
    // Whenever two reds are brothers, change color and move the red one layer up (equivalent to adding one layer to 23 trees)
    if (this.isRed(node.left) && this.isRed(node.right)) this.flipColors(node);
    return node;
  }

  / * * *@descriptionIf the node is red and left and right are black, make the left or left child node red */
  private moveRedLeft(node: RedBlackNode<T>): RedBlackNode<T> {
    this.flipColors(node);
    if (this.isRed(node.right.left)) {
      node.right = this.rotateRight(node.right);
      node = this.rotateLeft(node);
      this.flipColors(node);
    }
    return node;
  }

  / * * *@description: If the node is red and the right, right and left of the node are black, then the right or right children of the node are red */
  private moveRedRight(node: RedBlackNode<T>): RedBlackNode<T> {
    this.flipColors(node);
    if (this.isRed(node.left.left)) {
      node = this.rotateLeft(node);
      this.flipColors(node);
    }
    return node;
  }

  / * * *@description: Checks whether the node is red */
  private isRed(node: RedBlackNode<T>) {
    // If it is empty, it is also considered black
    // This is important because the bottom of the tree is full of black empty nodes
    if(! node) {return false;
    }
    returnnode.isRed(); }}Copy the code

Finally finish the red-black tree, the next article to analyze binary heap.

---

Front-end notepad, not regularly updated, welcome to pay attention to!

• Wechat official account: Lin Jingyi’s notepad
• Blog: Lin Jingyi’s notebook
• Nuggets column: Lin Jingyi’s notebook
• Zhihu column: Lin Jingyi’s notebook
• Github: MageeLin

---