# 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
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();