TypeScript implements AVL and red-black trees

preface

There is a problem with binary search trees: when a large part of the data inserted into the tree is larger or smaller than a certain node, one edge of the tree is very deep. To solve this problem, a self-balancing tree is a solution.

This article explores two types of self-balancing trees: AVL and red-black, implemented in TypeScript. Interested developers are welcome to read this article.

Writing in the front

The two self-balancing trees described in this article are based on binary search trees. For those who are not familiar with binary search trees, check out TypeScript binary search trees

AVL self-balancing tree

AVL tree (Adelson-Velskii-Landi tree) is a self-balanced binary search tree. The height difference between the left and right sub-trees of any node is at most 1. When adding or deleting nodes, AVL tree tries to convert to a complete tree as much as possible.

Implementation approach

AVL tree is a binary search tree, so we can inherit the binary search tree and rewrite some methods of the binary tree.

Terminology for AVL trees

Inserting or removing a node into an AVL tree is exactly the same as a binary search tree. However, AVL trees differ in that we need to check their balance factor to determine whether the tree needs to be adjusted or not.

Node height and balance factor
Balance operation – Rotation of tree

The height of a node is the maximum edge from a node to any child node. The figure below depicts a tree containing node heights.

The height of the left child node of node 35 is 1 and the height of the right child node is 2
The height of the left child node of node 45 is 2, and that of the right child node is 1
For node 45, the height of the edge of the largest child node is 2
The height of node 35 to node 45 is 1 and the height of node 45 is 2, so node 35 is 3

The balance factor of nodes refers to the difference between the height of the right subtree (HR) and the height of the left subtree (HL) that needs to be calculated for each node in AVL tree, and the value (HR-HL) should be 0, 1 or -1. If the result is not one of these three values, the AVL tree needs to be balanced, and the tree below describes the balance factor for each node.

When the current node has only the left child node, the balance factor is -1
The current node has only the right child node. The equilibrium factor is +1
When both the left and right child nodes of the current section are owned, the balance factor is +1

Balancing operation – Rotation of tree After adding or deleting nodes, we need to calculate the height of nodes to obtain the balance factor, and determine whether rotation is needed to balance the tree according to the balance factor. Tree balance has the following scenarios:

Left-left (LL): Single rotation to the right
Right-right (RR): single rotation to the left
Left-right (LR): Double rotation to the right
Right-left (RL): Double rotation to the left

Node height calculation

Declares a method that takes one parameter: the node to get the height of
Recursively retrieves the height of the left and right subtrees of the current node, returning the value of the larger one
Recursive baseline condition: the node is null

Equilibrium factor calculation

Declares a method that takes one parameter: the node to retrieve the balance factor
Calculate the height of the left and right subtrees of the current node, and calculate their difference
Returns different conditions based on the difference

The rotation of the tree

According to the calculated equilibrium factor, we carry out the corresponding rotation as follows

Left-left (LL): Single rotation to the right

When the height of the left child node of the node is greater than that of the right child node, and the left child node is also balanced or heavy, LL operation needs to be performed on the balance tree. The following figure describes this process

There are three nodes associated with balancing tree operations (X, Y, Z)
Set node X to Y
Set the left child of node Y to the right child of node X
Set the right child of X to the node Y
Update the node

Right-right (RR): single rotation to the left

When the height of the child node on the right of the node is greater than that on the left and the child node on the right is also balanced or the child node on the right is heavy, RR operation needs to be performed on the balance tree. The following figure shows the process

There are three nodes associated with balancing tree operations (X, Y, Z)
Place node X to node Y
Replace the right child of node Y with the left child of node X
Set the left child of node X to node Y

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

When the height of the left child node is greater than that of the right child node, and the left child node is heavier on the right, it is necessary to perform left rotation to repair the balance tree, so that left-left situation will be formed, and then perform a right rotation to repair the unbalanced node. The following figure describes the scenario requiring LR

RR rotation
LL rotation

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

When the height of the right child node is greater than that of the left child node, and the left side of the right child node is heavy, right rotation of the balance tree is needed to repair it, which will form a right-right situation, and then a left rotation of the unbalanced node is needed to repair it. The following figure describes the scenario requiring RL

LL rotation
RR rotation

Insert and remove nodes

The logic of inserting or removing nodes into an AVL tree is the same as that of a binary search tree, except that the insertion requires verification of whether the tree is balanced or not, and the corresponding rotation operation is required if the tree is not balanced.

Gets the balance factor of the node currently inserted into the tree
If the tree is unbalanced after inserting nodes into the left subtree, we need to compare whether the inserted key is smaller than the key of the left subtree. If so, LL rotation is performed, otherwise LR rotation is performed
If the tree is unbalanced after inserting nodes into the right subtree, we need to compare whether the inserted key is smaller than the key of the right subtree. If so, RR rotation is performed, otherwise RL rotation is performed

The implementation code

Create a new avltree.ts file
Declare AVLTree class, inheriting BinarySearchTree class

export default class AVLTree<T> extends BinarySearchTree<T>{
    constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
        super(compareFn); }}Copy the code

Declare balance factor enumeration

enum BalanceFactor {
    UNBALANCED_RIGHT = 1,
    SLIGHTLY_UNBALANCED_RIGHT = 2,
    BALANCED = 3,
    SLIGHTLY_UNBALANCED_LEFT = 4,
    UNBALANCED_LEFT = 5
}
Copy the code

Realize compute node height function

private getNodeHeight(node: Node<T>): number{
    if (node == null) {
        return - 1;
    }
    return Math.max(this.getNodeHeight(<Node<T>>node.left), this.getNodeHeight(<Node<T>>node.right)) + 1;
}
Copy the code

Realize the balance factor calculation function

private getBalanceFactor(node: Node<T>) {
    // Calculate the difference
    const heightDifference = this.getNodeHeight(<Node<T>>node.left) - this.getNodeHeight(<Node<T>>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:
            returnBalanceFactor.BALANCED; }}Copy the code

Achieve four rotations of the tree

/** ** a e -> rotationLL(b) -> c b */ \ /** c d de ** @param node */
private rotationLL(node: Node<T>) {
    // Create the TMP variable to store the left child node of the node
    const tmp = <Node<T>>node.left;
    // Change the left child of node to the right child of TMP
    node.left = tmp.right;
    // Change the right child node of TMP to node
    tmp.right = node;
    // Update the node
    return tmp;
}

/** * c b -> rotationRR(a) -> a e */ \ / \ * de c d * @param node */
private rotationRR(node: Node<T>) {
    // Place node X on node Y
    const tmp = <Node<T>>node.right;
    // Set the right child of Y to the left child of X
    node.right = tmp.left;
    // Set the left child of X to Y
    tmp.left = node;
    // Update the node
    return tmp;
}

/** * double rotation to the right, first to the right and then to the left * @param node */
private rotationLR(node: Node<T>) {
    node.left = this.rotationRR(<Node<T>>node.left);
    return this.rotationLL(node);
}

/** * right left: double rotation to the left, first left and then right * @param node */
private rotationRL(node: Node<T>) {
    node.right = this.rotationLL(<Node<T>>node.right);
    return this.rotationRR(node);
}
Copy the code

Overrides the insert and remove node functions

// Insert a node into the AVL tree
insert(key: T) {
    this.root = this.insertNode(<Node<T>>this.root, key)
}

protected insertNode(node: Node<T>, key:T) {
    if (node == null) {
        return new Node(key);
    }else if(this.compareFn(key, node.key) === Compare.LESS_THAN) {
        node.left = this.insertNode(<Node<T>>node.left, key);
    }else if(this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
        node.right = this.insertNode(<Node<T>>node.right, key);
    }else {
        return node; // Duplicate keys
    }

    // Calculate the balance factor to determine whether the tree needs a balance operation
    const balanceState = this.getBalanceFactor(node);

    // The tree is out of balance after inserting nodes into the left subtree
    if (balanceState === BalanceFactor.UNBALANCED_LEFT) {
        // Determine whether the inserted key is smaller than the key of the left child node
        if (this.compareFn(key, <T>node.left?.key) === Compare.LESS_THAN) {
            // If the value is smaller than that, rotate LL
            node = this.rotationLL(node);
        } else {
            // Otherwise perform LR rotation
            return this.rotationLR(node); }}// The tree is out of balance after a node is inserted into the right subtree
    if (balanceState === BalanceFactor.UNBALANCED_RIGHT) {
        // Determine whether the inserted key is smaller than the key of the right child node
        if (this.compareFn(key, <T>node.right?.key) === Compare.BIGGER_THAN) {
            // If the value is smaller than that, RR rotation is performed
            node = this.rotationRR(node);
        } else {
            // Otherwise do RL rotation
            return this.rotationRL(node); }}// Update the node
    return node;
}

// Remove the node
protected removeNode(node: Node<T>, key: T) {
    node = <Node<T>>super.removeNode(node, key);
    if (node == null) {
        return node;
    }

    // Get the tree balance factor
    const balanceState = this.getBalanceFactor(node);
    // The left tree is unbalanced
    if (balanceState === BalanceFactor.UNBALANCED_LEFT) {
        // Calculate the balance factor of the left tree
        const balanceFactorLeft = this.getBalanceFactor(<Node<T>>node.left);
        // The left subtree is unbalanced to the left
        if (balanceFactorLeft === BalanceFactor.BALANCED || balanceFactorLeft === BalanceFactor.UNBALANCED_LEFT) {
            // Do the LL rotation
            return this.rotationLL(node);
        }
        // The right subtree is unbalanced to the right
        if (balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
            // Perform LR rotation
            return this.rotationLR(<Node<T>>node.left); }}// Right tree is out of balance
    if (balanceState === BalanceFactor.UNBALANCED_RIGHT) {
        // Calculate the right subtree balance factor
        const balanceFactorRight = this.getBalanceFactor(<Node<T>>node.right);
        // The right subtree is unbalanced to the right
        if (balanceFactorRight === BalanceFactor.BALANCED || balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
            // Perform RR rotation
            return this.rotationRR(node);
        }
        // The right subtree is unbalanced to the left
        if (balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
            // Do the RL rotation
            return this.rotationRL(<Node<T>>node.right); }}return node;
}
Copy the code

For full code, please go to: avltree.ts

Write test code

We implemented the AVL tree above, so let’s use an example to test if the above code executes correctly

const avlTree = new AVLTree();
const printNode = value= >{
    console.log(value);
}
/** * test tree unbalance * 30 30 30 */ \ / \ /* 27 60 -> 12 60 -> remove(10) 12 60 */ / \ * 12 10 27 27 */ * 10 */
avlTree.insert(30);
avlTree.insert(27);
avlTree.insert(60);
avlTree.insert(12);
avlTree.insert(10);
avlTree.remove(10);
// after the sequence traversal
avlTree.preOrderTraverse(printNode);
Copy the code

The result is as follows:

Red and black tree

Red-black tree: The name implies that the nodes in the tree are either red or black. It is also a self-balanced binary tree. Above we implement AVL tree, we insert or remove nodes into AVL tree may cause rotation, so we need a self-balancing tree with multiple inserts and deletions, red black tree is better. With low insertion or deletion frequency, AVL trees are better than red-black trees.

Implementation approach

Each node of a red-black tree should follow the following principles:

Nodes are either red or black
The root of the tree is black
All the leaves are black
If a node is red, both of its children are black
There cannot be two adjacent red nodes, and a red node cannot have a red parent or child
All paths from a given node to its descendants (NULL leaf nodes) contain the same number of black nodes.

Insert the node

The logic of inserting a node into a red-black tree is the same as that of a binary tree. In addition to the logic of inserting a node, we also need to apply a color to the node after insertion and verify that the tree meets the red-black tree conditions and is still self-balanced.

We need to create a new node class to describe the red-black tree: the color of the node, the reference to the parent node
Rewrite the INSERT method to create a new red-black tree node as the root if the tree is empty, and set the root node’s color to black
If the tree is not empty at the time of insertion, we insert nodes in the correct position like a binary search tree, and after the insertion, we determine whether the rules of the red-black tree are satisfied
Overwrite the insert node function, save the reference of the parent node when insert, return the reference of the node to verify the properties of the inserted tree

Verify red-black tree properties

To verify that a red-black tree is still balanced and meets all its requirements, we need to use two concepts: recolor and rotation.

After inserting a node into the tree, the new node will be red. This does not affect the rule of the number of black nodes (Rule 6), but it does affect rule 5: two descendant red nodes cannot coexist. If the parent of the inserted node is black, there is no problem. However, if the parent of the inserted node is red, then rule 5 is violated. To resolve this conflict, we only need to change the parent, grandfather, and uncle nodes, as depicted in the following figure

Verify red-black tree properties:

Starting with the inserted node, we verify that its parent is red and that the node is not black.
Verify that the parent node is the left or right child of the grandfather node
If the parent node is the child to the left of the grandfather node, there are three scenarios
1. Tertiary nodes are red, and we just need to fill them in again
2. The node is the right child of the parent node, and we need to rotate it left
3. The node is the left child of the parent node, and we need to rotate it right
If the parent node is the child node to the right of the grandfather node, there are also three situations
1. Tertiary nodes are red, so I can just color them in again
2. The node is the left child node, rotated right
3. The node is the right child node, rotated left
Set the color of the root node. Since the root node must be black, the color of the root node may change after we do this, so we need to set it to black

The implementation code

Create a new redBlacktree.ts file
Declare the RedBlackTree class and create a helper RedBlackNode class that inherits the BinarySearchTree class

export class RedBlackNode<K> extends Node<K> {
    public left: RedBlackNode<K> | undefined;
    public right: RedBlackNode<K> | undefined;
    public parent: RedBlackNode<K> | undefined;
    public color: number;
    constructor(public key: K) {
        super(key);
        this.color = Colors.RED;
    }

    isRed() {
        return this.color === Colors.RED; }}Copy the code

export default class RedBlackTree<T> extends BinarySearchTree<T> {
    protected root: RedBlackNode<T> | undefined;
    constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
        super(compareFn); }}Copy the code

Override insert method

insert(key: T) {
    if (this.root == null) {
        // If the tree is empty, create a red-black tree node
        this.root = new RedBlackNode(key);
        // Red black tree characteristic 2: the root node is black
        this.root.color = Colors.BLACK;
    } else {
        // Insert the node in the appropriate place. The insertNode method returns the newly inserted node
        const newNode = this.insertNode(this.root, key);
        // Verify the red-black tree property after the node is inserted
        this.fixTreeProperties(newNode); }}protected insertNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
    // The current inserted key is smaller than the current node key
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
    if (node.left == null) { // The left child of the current node is null
        // Create a red-black tree node on the left child of the current node
        node.left = new RedBlackNode(key);
        // Save a reference to the parent
        node.left.parent = node;
        // Returns a reference to the node
        return node.left;
    } else {
        // The left child of the current node is not null, recursively looking for an appropriate position to insert it
        return this.insertNode(node.left,key); }}else if (node.right == null) { // The right child is null
        // Create a red-black tree node on the right child of the current node
        node.right = new RedBlackNode(key);
        // Save a reference to the parent
        node.right.parent = node;
        // Returns a reference to the node
        return node.right;
    } else {
        // Recursively find the right place to insert it
        return this.insertNode(node.right, key); }}Copy the code

Implement red-black tree attribute verification method

private fixTreeProperties(node: RedBlackNode<T>) {
    /** * Verify from the inserted node: * 1. The current node exists and the color of the parent node is red * 2. The current node color is not black */
    while(node && node.parent && node.parent.color === Colors.RED && node.color ! == Colors.BLACK) {// Keep the code readable: save the parent and grandfather references of the current node
        let parent = node.parent;
        const grandParent = <RedBlackNode<T>>parent.parent;
        // The parent node is the left child of the grandfather node: case A
        if (grandParent && grandParent.left === parent) {
            // Get the tertiary node
            const uncle =grandParent.left;
            // Case 1A: Tertiary nodes are also red -- just need to be recolor
            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 parent node and the right child node -- rotate left
                if (node === parent.right) {
                    this.rotationRR(parent);
                    node = parent;
                    parent = <RedBlackNode<T>>node.parent;
                }
                // Case 3A: The node is the left child of the parent -- rotate right
                this.rotationLL(grandParent); parent.color = Colors.BLACK; grandParent.color = Colors.RED; node = parent; }}else { // The parent node is the right child node: case B
            // Get the tertiary node
            const uncle = grandParent.left;
            // Case 1B: Tertiary node is red -- just fill in the color
            if (uncle && uncle.color === Colors.RED) {
                grandParent.color = Colors.RED;
                parent.color = Colors.BLACK;
                uncle.color = Colors.BLACK;
                node = grandParent;
            } else {
                // Case 2B: Node is left child node -- right rotation
                if (node === parent.left) {
                    this.rotationLL(parent);
                    node = parent;
                    parent = <RedBlackNode<T>>node.parent;
                }
                // Case 3B: the node is the right child node -- rotated left
                this.rotationRR(grandParent); parent.color = Colors.BLACK; grandParent.color = Colors.RED; node = parent; }}}// Set the root node color
    this.root ! =null? this.root.color = Colors.BLACK : this.root;
}
Copy the code

Implement left rotation and right rotation

// Single rotation to the right
private rotationLL(node: RedBlackNode<T>) {
    const tmp = <RedBlackNode<T>>node.left;
    node.left = tmp.right;
    if (tmp.right && tmp.right.key) {
        tmp.right.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.right = node; node.parent = tmp; }}// Single rotation to the left
private rotationRR(node: RedBlackNode<T>) {
    const tmp = <RedBlackNode<T>>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;
}
Copy the code

For the full code, go to RedBlacktree.ts

Write test code

Now that we’ve implemented a red-black tree, let’s test to see if the methods we’ve implemented all perform correctly

const redBlackTree = new RedBlackTree();
redBlackTree.insert(1);
redBlackTree.insert(2);
redBlackTree.insert(3);
redBlackTree.insert(4);
redBlackTree.insert(5);
redBlackTree.insert(6);
redBlackTree.insert(7);
redBlackTree.insert(8);
redBlackTree.insert(9);
const printNode = value= > console.log(value);
redBlackTree.preOrderTraverse(printNode);
Copy the code

The result is as follows:

At the end of the article eggs

So far, we have studied binary search tree and its two kinds of self-balancing tree implementation.

Next, let’s play a scavenger hunt. The rules of this game are as follows:

The picture above hides the name of the treasure
The file starts with 24E9e
After solving the file name, type the address www.kaisir.cn/uploads/ (use HTTPS for access) and access the treasure in your browser

Note: Finding treasure uses binary search trees, which TypeScript implements

Write in the last

If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
This article was first published in nuggets. Reprint is prohibited without permission 💌

TypeScript implements AVL and red-black trees

preface

Writing in the front

AVL self-balancing tree

Implementation approach

Terminology for AVL trees

Node height calculation

Equilibrium factor calculation

The rotation of the tree

Left-left (LL): Single rotation to the right

Right-right (RR): single rotation to the left

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

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

Insert and remove nodes

The implementation code

Write test code

Red and black tree

Implementation approach

Insert the node

Verify red-black tree properties

The implementation code

Write test code

At the end of the article eggs

Write in the last

Related Posts

Execution Timing of JS Functions

Flying pig marketing domain SSR summary – Double eleven venue to accelerate

Monthly list | Top authors for June 2021 published