TypeScript: Implement an AVL Tree

1. Introduction

AVL Tree (named after its inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree (BST) where the difference between the heights of the left and right subtrees of any node is no more than one. The need for balancing arises to maintain an O(log n) search time, as inserting or deleting elements can lead to a skewed tree, leading to a worst-case time complexity of O(n) for operations.

2. Program Overview

We will implement an AVL Tree with the following functionalities:

- Insertion of nodes.

- In-order traversal for display.

- Balancing the tree after insertions.

3. Code Program

// Node class to represent a node in the AVL Tree
class Node {
    data: number;
    left: Node | null = null;
    right: Node | null = null;
    height: number = 1;

    constructor(data: number) {
        this.data = data;
    }
}

// AVL Tree class
class AVLTree {
    root: Node | null = null;

    // Utility function to get the height of a node
    getHeight(node: Node | null): number {
        if (!node) return 0;
        return node.height;
    }

    // Utility function to get the balance factor of a node
    getBalance(node: Node | null): number {
        if (!node) return 0;
        return this.getHeight(node.left) - this.getHeight(node.right);
    }

    // Right Rotate to balance the AVL Tree
    rightRotate(y: Node): Node {
        let x = y.left!;
        let T3 = x.right;

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

        // Update heights
        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;  // Return new root
    }

    // Left Rotate to balance the AVL Tree
    leftRotate(x: Node): Node {
        let y = x.right!;
        let T2 = y.left;

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

        // Update heights
        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;  // Return new root
    }

    // Insert a node in the AVL Tree and balance the tree
    insert(node: Node | null, data: number): Node {
        // 1. Standard BST Insertion
        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 values are not allowed
        }

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

        // 3. Get the balance factor to check if it's unbalanced
        let balance = this.getBalance(node);

        // 4. Balance the node if it's unbalanced
        // Left Left Case
        if (balance > 1 && data < node.left!.data) {
            return this.rightRotate(node);
        }
        // Right Right Case
        if (balance < -1 && data > node.right!.data) {
            return this.leftRotate(node);
        }
        // Left Right Case
        if (balance > 1 && data > node.left!.data) {
            node.left = this.leftRotate(node.left!);
            return this.rightRotate(node);
        }
        // Right Left Case
        if (balance < -1 && data < node.right!.data) {
            node.right = this.rightRotate(node.right!);
            return this.leftRotate(node);
        }

        return node;
    }

    // Recursive in-order traversal to display the AVL Tree
    inOrder(node: Node | null): void {
        if (node) {
            this.inOrder(node.left);
            console.log(node.data);
            this.inOrder(node.right);
        }
    }

    // Insert data into the AVL Tree
    add(data: number): void {
        this.root = this.insert(this.root, data);
    }

    // Display the AVL Tree
    display(): void {
        this.inOrder(this.root);
    }
}

// Test the AVLTree class
const avl = new AVLTree();
avl.add(10);
avl.add(20);
avl.add(30);
avl.add(25);
avl.display();

The Node class represents a node in the AVL Tree. It contains the data, pointers to left and right children, and a height property to store the height of the node in the tree