JavaScript Program to Implement an AVL Tree

Introduction

An AVL Tree is a self-balancing binary search tree (BST) where the difference in heights of the left and right subtrees (called the balance factor) is at most 1 for every node. AVL Trees maintain balance by performing rotations (single or double) when nodes are inserted or deleted, ensuring that the tree remains balanced for efficient search, insertion, and deletion operations.

In an AVL Tree:

• Insertion: When a new node is inserted, the tree may become unbalanced. Rotations are used to restore balance.
• Balance Factor: The balance factor of a node is the height difference between its left and right subtrees. The balance factor can be -1, 0, or 1 for a balanced node.
• Rotations: There are four types of rotations:
  • Left Rotation.
  • Right Rotation.
  • Left-Right Rotation (double rotation).
  • Right-Left Rotation (double rotation).

This guide will walk you through writing a JavaScript program to implement an AVL Tree with basic operations such as insertion and in-order traversal.

Problem Statement

Create a JavaScript program that:

• Implements an AVL Tree with methods for:
  • Insertion: Insert a node into the AVL Tree while maintaining balance.
  • In-order Traversal: Traverse the tree in sorted order.

Example:

• Input: Insert nodes 10, 20, 30, 40, 50, 25
• Output (in-order traversal): 10, 20, 25, 30, 40, 50

Solution Steps

1. Define a Node Class: Create a class to represent each node with a value, height, left child, and right child.
2. Define an AVL Tree Class: Implement methods for:
   • Insert: Insert a node into the tree while maintaining balance using rotations.
   • Rotations: Perform left and right rotations to maintain balance.
   • Height and Balance Factor: Calculate the height and balance factor of each node.
   • In-order Traversal: Traverse the tree in sorted order.

JavaScript Program

Step 1: Define the Node Class

// JavaScript Program to Implement an AVL Tree
// Author: https://www.rameshfadatare.com/

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.height = 1; // Initially, every node's height is 1
    }
}

Step 2: Define the AVL Tree Class

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

    // Get the height of the node
    height(node) {
        if (node === null) {
            return 0;
        }
        return node.height;
    }

    // Calculate the balance factor of a node
    getBalance(node) {
        if (node === null) {
            return 0;
        }
        return this.height(node.left) - this.height(node.right);
    }

    // Right rotate subtree rooted with y
    rightRotate(y) {
        let x = y.left;
        let T2 = x.right;

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

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

        // Return new root
        return x;
    }

    // Left rotate subtree rooted with x
    leftRotate(x) {
        let y = x.right;
        let T2 = y.left;

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

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

        // Return new root
        return y;
    }

    // Insert a node into the AVL Tree
    insert(node, value) {
        // Perform normal BST insertion
        if (node === null) {
            return new Node(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 {
            // Duplicate values are not allowed in AVL Tree
            return node;
        }

        // Update the height of the ancestor node
        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));

        // Get the balance factor of this ancestor node
        let balance = this.getBalance(node);

        // If the node becomes unbalanced, then perform rotations

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

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

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

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

        // Return the (unchanged) node pointer
        return node;
    }

    // In-order traversal of the AVL tree
    inOrder(node) {
        if (node !== null) {
            this.inOrder(node.left);
            console.log(node.value);
            this.inOrder(node.right);
        }
    }

    // Insert a value into the AVL Tree
    insertValue(value) {
        this.root = this.insert(this.root, value);
    }
}

Step 3: Example Usage

// Example usage of the AVL Tree
const avl = new AVLTree();

// Insert values
avl.insertValue(10);
avl.insertValue(20);
avl.insertValue(30);
avl.insertValue(40);
avl.insertValue(50);
avl.insertValue(25);

// In-order traversal of the AVL Tree
console.log("In-order traversal:");
avl.inOrder(avl.root);

Output Example

In-order traversal:
10
20
25
30
40
50

Explanation

Step 1: Define the Node Class

• The Node class represents each node in the AVL Tree. Each node has:
  • value: The value stored in the node.
  • left: A reference to the left child node.
  • right: A reference to the right child node.
  • height: The height of the node, which helps calculate the balance factor.

Step 2: Define the AVL Tree Class

• height(): Returns the height of a node. If the node is null, the height is 0.
• getBalance(): Calculates the balance factor of a node by subtracting the height of the right subtree from the height of the left subtree.
• rightRotate() and leftRotate(): Perform right and left rotations to restore balance when the tree becomes unbalanced.
• insert(): Inserts a new value into the AVL tree. After the insertion, it updates the height and balance factor of the nodes, performing rotations as necessary to maintain balance.
• inOrder(): Performs in-order traversal, printing the values of the nodes in ascending order.

Step 3: Example Usage

• The AVL Tree is created, and values are inserted one by one.
• The in-order traversal prints the values in ascending order.

Time Complexity

• Insertion: O(log n), where n is the number of nodes in the AVL Tree.
  • The tree is balanced, so the height of the tree is log n.
• In-order Traversal: O(n), where n is the number of nodes in the tree.

Conclusion

This JavaScript program implements an AVL Tree, a self-balancing binary search tree that ensures efficient operations even after multiple insertions. The tree uses rotations to maintain balance, providing logarithmic time complexity for insertion, deletion, and search operations.