🎓 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
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if they differ by more than one at any time, rebalancing is done to restore this property. AVL trees are named after their inventors, Adelson-Velsky and Landis. Due to their balancing property, they guarantee O(log n) time complexity for insert, delete, and search operations.
2. Implementation Steps
1. Define a Node class to represent individual nodes in the AVL tree, containing information about data, height, and left/right children.
2. Create an AVLTree class that will provide methods for common operations.
3. Implement rotation methods (leftRotate, rightRotate, leftRightRotate, rightLeftRotate) to maintain the AVL tree balance.
4. Implement methods such as insert, delete, search, findMin, findMax, and tree traversal methods.
3. Implementation in Kotlin Programming
class Node(var key: Int) {
var height: Int = 1
var left: Node? = null
var right: Node? = null
}
class AVLTree {
private fun height(node: Node?): Int {
return node?.height ?: 0
}
private fun updateHeight(node: Node) {
node.height = 1 + maxOf(height(node.left), height(node.right))
}
private fun balanceFactor(node: Node?): Int {
return height(node?.left) - height(node?.right)
}
private fun leftRotate(x: Node): Node {
val y = x.right!!
val T2 = y.left
y.left = x
x.right = T2
updateHeight(x)
updateHeight(y)
return y
}
private fun rightRotate(y: Node): Node {
val x = y.left!!
val T2 = x.right
x.right = y
y.left = T2
updateHeight(y)
updateHeight(x)
return x
}
fun insert(root: Node?, key: Int): Node {
if (root == null) return Node(key)
if (key < root.key) root.left = insert(root.left, key)
else if (key > root.key) root.right = insert(root.right, key)
else return root
updateHeight(root)
val balance = balanceFactor(root)
if (balance > 1) {
if (key < root.left!!.key) {
return rightRotate(root)
} else {
root.left = leftRotate(root.left!!)
return rightRotate(root)
}
}
if (balance < -1) {
if (key > root.right!!.key) {
return leftRotate(root)
} else {
root.right = rightRotate(root.right!!)
return leftRotate(root)
}
}
return root
}
fun delete(root: Node?, key: Int): Node? {
if (root == null) return root
if (key < root.key) {
root.left = delete(root.left, key)
} else if (key > root.key) {
root.right = delete(root.right, key)
} else {
if (root.left == null || root.right == null) {
var temp: Node? = null
temp = root.left ?: root.right
if (temp == null) {
temp = root
root = null
} else {
root = temp
}
} else {
val temp = minValueNode(root.right!!)
root.key = temp.key
root.right = delete(root.right, temp.key)
}
}
if (root == null) return root
updateHeight(root)
val balance = balanceFactor(root)
if (balance > 1) {
if (balanceFactor(root.left) >= 0) {
return rightRotate(root)
} else {
root.left = leftRotate(root.left!!)
return rightRotate(root)
}
}
if (balance < -1) {
if (balanceFactor(root.right) <= 0) {
return leftRotate(root)
} else {
root.right = rightRotate(root.right!!)
return leftRotate(root)
}
}
return root
}
private fun minValueNode(node: Node): Node {
var current = node
while (current.left != null) current = current.left!!
return current
}
fun preOrder(root: Node?) {
if (root != null) {
println(root.key)
preOrder(root.left)
preOrder(root.right)
}
}
}
// client code to test AVL Tree Implementation in Kotlin
fun main() {
var tree: Node? = null
val avlTree = AVLTree()
tree = avlTree.insert(tree, 10)
tree = avlTree.insert(tree, 20)
tree = avlTree.insert(tree, 30)
tree = avlTree.insert(tree, 40)
tree = avlTree.insert(tree, 50)
tree = avlTree.insert(tree, 25)
println("Preorder traversal of constructed AVL tree:")
avlTree.preOrder(tree)
tree = avlTree.delete(tree, 10)
println("\nPreorder traversal after deleting 10:")
avlTree.preOrder(tree)
}
Output:
Preorder traversal of constructed AVL tree: 30 20 10 25 40 50 Preorder traversal after deleting 10: 30 25 20 40 50
Explanation:
1. An AVL Tree is a self-balancing Binary Search Tree. The key property is that the balance factor (difference in height between left and right subtrees) of any node is either -1, 0, or 1.
2. Each Node contains data (key), height, and references to left and right children.
3. The AVLTree class contains several utility functions:
- height to get the height of a node.
- updateHeight to update the height of a node.
- balanceFactor to compute the balance factor of a node.
- Rotation methods (leftRotate, rightRotate, leftRightRotate, rightLeftRotate) to handle imbalances.
4. insert and delete methods recursively maintain the AVL property after insertion or deletion.
5. The main function demonstrates insertion and deletion operations and their effects on tree balance.
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