TypeScript: Implement an AVL Tree

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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