AVL Trees: Mastering Self-Balancing Binary Search Trees in JavaScript

6.4.2 AVL Trees

AVL Trees are a crucial data structure for anyone looking to master efficient data management and retrieval. As a type of self-balancing binary search tree (BST), AVL trees ensure that the tree remains balanced after every insertion and deletion operation, maintaining an optimal time complexity of O(log n) for these operations. This section will delve into the intricacies of AVL trees, including their definition, the rotations used to maintain balance, and how to implement them in JavaScript.

Understanding AVL Trees

AVL trees are named after their inventors, Adelson-Velsky and Landis, who introduced them in 1962. They are the first dynamically balanced trees, designed to maintain a balanced height to ensure efficient operations. The key feature of an AVL tree is its balance factor, which is stored at each node.

Balance Factor

The balance factor of a node in an AVL tree is defined as the difference in height between its left and right subtrees. For a tree to remain balanced, the balance factor of every node must be -1, 0, or 1. If the balance factor of any node becomes less than -1 or greater than 1, the tree needs rebalancing through rotations.

Rotations in AVL Trees

Rotations are the fundamental operations used to maintain the balance of an AVL tree. There are four types of rotations:

1. Right Rotation (RR)
2. Left Rotation (LL)
3. Left-Right Rotation (LR)
4. Right-Left Rotation (RL)

Right Rotation (RR)

A right rotation is performed when a left-heavy subtree needs balancing. It involves rotating the subtree to the right.

    graph TD;
	    subgraph Right Rotation
	    A[Z]
	    A --> B[Y]
	    B --> C[X]
	    end

In a right rotation, node Y becomes the new root of the subtree, and node Z becomes the right child of Y.

Left Rotation (LL)

A left rotation is used when a right-heavy subtree needs balancing. It involves rotating the subtree to the left.

    graph TD;
	    subgraph Left Rotation
	    A[X]
	    A --> B[Y]
	    B --> C[Z]
	    end

In a left rotation, node Y becomes the new root of the subtree, and node X becomes the left child of Y.

Left-Right Rotation (LR)

An LR rotation is a combination of a left rotation followed by a right rotation. It is used when a left-heavy subtree has a right-heavy child.

    graph TD;
	    subgraph Left-Right Rotation
	    A[Z]
	    A --> B[X]
	    B --> C[Y]
	    end

Right-Left Rotation (RL)

An RL rotation is a combination of a right rotation followed by a left rotation. It is used when a right-heavy subtree has a left-heavy child.

    graph TD;
	    subgraph Right-Left Rotation
	    A[X]
	    A --> B[Z]
	    B --> C[Y]
	    end

Implementing AVL Trees in JavaScript

Implementing an AVL tree involves creating a class for the tree and its nodes, and defining methods for insertion, deletion, and rebalancing.

Node Class

First, let’s define a class for the nodes of the AVL tree.

class AVLNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

AVL Tree Class

Next, we define the AVL tree class with methods for insertion and balancing.

class AVLTree {
    constructor() {
        this.root = null;
    }

    getHeight(node) {
        return node ? node.height : 0;
    }

    getBalanceFactor(node) {
        return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
    }

    rightRotate(y) {
        const x = y.left;
        const T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;
        x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;

        return x;
    }

    leftRotate(x) {
        const y = x.right;
        const T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;
        y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;

        return y;
    }

    insert(node, value) {
        if (!node) {
            return new AVLNode(value);
        }

        if (value < node.value) {
            node.left = this.insert(node.left, value);
        } else if (value > node.value) {
            node.right = this.insert(node.right, value);
        } else {
            return node; // Duplicate values are not allowed
        }

        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

        const balanceFactor = this.getBalanceFactor(node);

        // Left Left Case
        if (balanceFactor > 1 && value < node.left.value) {
            return this.rightRotate(node);
        }

        // Right Right Case
        if (balanceFactor < -1 && value > node.right.value) {
            return this.leftRotate(node);
        }

        // Left Right Case
        if (balanceFactor > 1 && value > node.left.value) {
            node.left = this.leftRotate(node.left);
            return this.rightRotate(node);
        }

        // Right Left Case
        if (balanceFactor < -1 && value < node.right.value) {
            node.right = this.rightRotate(node.right);
            return this.leftRotate(node);
        }

        return node;
    }

    insertValue(value) {
        this.root = this.insert(this.root, value);
    }
}

Complexity Analysis

The AVL tree maintains a balanced height, ensuring that all operations—insertions, deletions, and lookups—are performed in O(log n) time. This efficiency is achieved through the use of rotations that keep the tree balanced after every modification.

Practical Applications

AVL trees are widely used in applications where frequent insertions and deletions are required, and maintaining a balanced tree is crucial for performance. They are ideal for database indexing, memory management, and other systems where data retrieval speed is critical.

Conclusion

Implementing AVL trees in JavaScript provides a solid understanding of self-balancing trees and their importance in maintaining efficient data structures. By mastering AVL trees, you gain insights into the mechanics of balance and the role of rotations in maintaining optimal performance.

Quiz Time!