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 tree`equivalent`The red black tree, due to the 2-3 tree`Trigeminal node`Has been to`3``Binary node tree`So in a red black tree`red`The color means that this is in two or three trees`Trigeminal node`.
2. `AVL tree`Is close to`The log ₂ N`; for`2-3 tree`Since the node can be`binary`or`trigeminal`So the height will not exceed the equilibrium`The log ₂ N`It can’t be lower than that`The log ₃ N`; And for`2-3 tree`equivalent`Red and black tree`As a result of`Trigeminal node`Has been to`Layer 2`So the height will not exceed the equilibrium`2 the log ₂ N`.
3. The key point is, if you see a red black tree`Red nodes`(link), don’t think of it as a child node, just stretch it out and you’ll understand`2-3 tree`and`Left-leaning red black tree`, as shown in the figure below:

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

• `red`Links are`On the left`Links;
• `There is no`Any node`It's connected to two red links at once`(That is, the red node`Not adjacent`or`Is the sibling node`);
• The tree is`Perfect 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 one`1`).

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);
} 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