AVL Trees Explained In Javascript: Mastering JavaScript

AVL Trees: Keeping Balance in Binary Search

In the realm of computer science, particularly in data structures, trees play a pivotal role. Among trees, the Binary Search Tree (BST) is a popular choice for its simplicity and ease of understanding. But BSTs have a downside; in the worst-case scenario, they can get skewed, which means operations like searching can take linear time. Enter AVL trees, a self-balancing variant of BSTs.

What is an AVL Tree?

Named after its inventors, Adelson-Velsky and Landis, an AVL tree is a binary search tree with an added feature — it automatically ensures that it remains balanced during insertions and deletions. But what does “balanced” mean in this context? In an AVL tree, for any given node, the heights of its two child subtrees can differ by at most one. This property ensures that the tree remains approximately balanced, which in turn guarantees logarithmic upper bounds for standard operations like insertion, deletion, and lookup.

Why is Balance Important?

Imagine you’re looking up a book in a perfectly organized library where books are sorted alphabetically. If the racks are of uniform height, you’d easily and swiftly find your book. But, if one rack is significantly taller than the others, you might spend an inordinate amount of time sifting through it. Similarly, an unbalanced tree can lead to inefficiencies. AVL trees address this problem by self-adjusting and maintaining balance, ensuring optimal performance for operations.

Visualizing an AVL Tree

Visualizing an AVL tree in plaintext can be done using simple indentation and tree symbols. Let’s take an example:

Consider the AVL tree after inserting the numbers: 30, 20, 40, 10, and 5.

The resulting tree is:

    20
   /  \
  10   30
 /      \
5        40

Here’s how the tree would look after these insertions:

Insert 30:

30

Insert 20:

  30
 /
20

Insert 40:

  30
 /  \
20   40

Insert 10:

  30
 /  \
20   40
 /
10

Insert 5 (this will trigger a rotation to balance the tree):

    20
   /  \
  10   30
 /      \
5        40

The indentation indicates the depth of the node in the tree, and the slashes (/ and \) represent left and right children, respectively. This representation gives a visual sense of the structure of the AVL tree in a plain-text format.

AVL Tree in Modern JavaScript

Let’s dive deep into the structure with a modern JavaScript example:

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.height = 1; // New nodes always start with a height of 1.
    }
}

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

    // Utility function to get the height of a node.
    getHeight(node) {
        return node ? node.height : 0;
    }

    // Utility function to get balance factor of a node.
    getBalanceFactor(node) {
        return this.getHeight(node.left) - this.getHeight(node.right);
    }

    // Rotate node to the right.
    rightRotate(y) {
        const x = y.left;
        const T3 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T3;

        // Update heights post rotation
        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; // New root
    }

    // Rotate node to the left.
    leftRotate(x) {
        const y = x.right;
        const T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights post rotation
        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; // New root
    }

    // Recursively inserts a node and performs rotations if necessary.
    insert(node, data) {
        if (!node) return new Node(data);

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

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

        // Get the balance to check if it became unbalanced.
        const balance = this.getBalanceFactor(node);

        // Left heavy scenario
        if (balance > 1) {
            if (data < node.left.data) {
                return this.rightRotate(node);
            } else {
                node.left = this.leftRotate(node.left);
                return this.rightRotate(node);
            }
        }

        // Right heavy scenario
        if (balance < -1) {
            if (data > node.right.data) {
                return this.leftRotate(node);
            } else {
                node.right = this.rightRotate(node.right);
                return this.leftRotate(node);
            }
        }

        return node;
    }

    add(data) {
        this.root = this.insert(this.root, data);
    }
}

With this JavaScript example, you can create an AVL tree and add nodes. The add function takes care of both inserting and balancing the tree.

Wrapping up

AVL trees are a beautiful combination of algorithmic intelligence and structural precision. They tackle one of the primary weaknesses of the binary search tree — the possibility of becoming skewed. By ensuring balance at every insertion or deletion, AVL trees provide consistent performance, making them