JavaScript: Implement an AVL Tree

1. Introduction

An AVL (Adelson-Velsky and Landis) tree is a self-balancing binary search tree, where the difference between heights of left and right subtrees cannot be more than one for all nodes. When the balance factor (difference in heights) is violated, rebalancing is done using rotation operations.

2. Program Overview

We'll implement the AVL tree with basic operations: insertion and in-order traversal for demonstration.

3. Code Program

// Node class to represent nodes
function Node(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.height = 1;  // By default, a new node has height 1
}

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

// Utility function to get the height of the node
function height(node) {
    if (!node) return 0;
    return node.height;
}

// Utility function to get the balance factor
function getBalance(node) {
    if (!node) return 0;
    return height(node.left) - height(node.right);
}

// Right rotate utility function
function rightRotate(y) {
    var x = y.left;
    var T3 = x.right;

    // Rotation
    x.right = y;
    y.left = T3;

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

    // Return the new root
    return x;
}

// Left rotate utility function
function leftRotate(x) {
    var y = x.right;
    var T2 = y.left;

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

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

    // Return the new root
    return y;
}

// Recursive function to insert a node
AVLTree.prototype.insert = function(root, data) {
    // BST insertion
    if (!root) return new Node(data);
    
    if (data < root.data) root.left = this.insert(root.left, data);
    else if (data > root.data) root.right = this.insert(root.right, data);
    else return root; // No duplicates allowed

    // Update the height
    root.height = 1 + Math.max(height(root.left), height(root.right));

    // Get balance to check if it's unbalanced
    var balance = getBalance(root);

    // Rotation cases
    if (balance > 1) {
        if (data < root.left.data) return rightRotate(root);
        else if (data > root.left.data) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }
    }

    if (balance < -1) {
        if (data > root.right.data) return leftRotate(root);
        else if (data < root.right.data) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }
    }

    return root;
}

// Utility function for in-order traversal
AVLTree.prototype.inOrder = function(root) {
    if (!root) return;
    this.inOrder(root.left);
    console.log(root.data);
    this.inOrder(root.right);
}

// Test the AVL Tree
var tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 25);

tree.inOrder(tree.root); // Should print in ascending order: 10, 20, 25, 30

Output:

10
20
25
30

4. Step By Step Explanation

1. Node Class: Represents individual nodes in our AVL tree. Each node has data, left and right pointers, and a height attribute.

2. AVLTree Class: Represents the AVL tree itself. We only keep track of the root node.

3. Height Function: Returns the height of the node. We use it to determine the balance of a node.

4. getBalance Function: Determines if the node is left-heavy, balanced, or right-heavy.

5. rightRotate & leftRotate: Are used to re-balance the tree when the AVL property is violated.

6. Insert Function: This method inserts a new node into the AVL tree and ensures that the AVL property is maintained after the insert.

7. inOrder Function: A simple in-order traversal of the AVL tree.

The test at the end creates an AVL tree and inserts a few nodes. The tree auto-balances itself after every insert, ensuring that the AVL property is always maintained.