🎓 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
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment