🎓 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
A Red-Black Tree is a self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black.
A Red-Black Tree satisfies the following properties:
1. Every node is either red or black.
2. The root is black.
3. All leaves (NIL nodes) are black.
4. If a red node has a child, the child is always black.
5. Every path from a node to its descendant NIL nodes contains the same number of black nodes.
These properties ensure that the tree remains approximately balanced, resulting in O(log n) time for most of its operations.
2. Implementation Steps
1. Define a Node class to represent individual nodes in the Red-Black Tree, containing the data, color, parent, left child, and right child.
2. Implement rotation methods (leftRotate and rightRotate) to maintain the Red-Black Tree properties.
3. Implement the insert and delete methods which will handle the tree's self-balancing.
4. Provide methods for tree traversal and other common operations.
3. Implementation in Kotlin Programming
enum class Color {
RED, BLACK
}
class Node(var key: Int, var color: Color, var parent: Node? = null) {
var left: Node? = null
var right: Node? = null
}
class RedBlackTree {
private var root: Node? = null
private fun leftRotate(x: Node) {
val y = x.right!!
x.right = y.left
if (y.left != null) {
y.left!!.parent = x
}
y.parent = x.parent
if (x.parent == null) {
root = y
} else if (x == x.parent!!.left) {
x.parent!!.left = y
} else {
x.parent!!.right = y
}
y.left = x
x.parent = y
}
private fun rightRotate(y: Node) {
val x = y.left!!
y.left = x.right
if (x.right != null) {
x.right!!.parent = y
}
x.parent = y.parent
if (y.parent == null) {
root = x
} else if (y == y.parent!!.right) {
y.parent!!.right = x
} else {
y.parent!!.left = x
}
x.right = y
y.parent = x
}
fun insert(key: Int) {
var z = Node(key, Color.RED)
var y: Node? = null
var x = root
while (x != null) {
y = x
if (z.key < x.key) {
x = x.left
} else {
x = x.right
}
}
z.parent = y
if (y == null) {
root = z
} else if (z.key < y.key) {
y.left = z
} else {
y.right = z
}
if (z.parent == null) {
z.color = Color.BLACK
return
}
if (z.parent!!.parent == null) {
return
}
fixViolations(z)
}
private fun fixViolations(z: Node) {
var z = z
while (z.parent != null && z.parent!!.color == Color.RED) {
var y: Node? = null
if (z.parent == z.parent!!.parent!!.left) {
y = z.parent!!.parent!!.right
if (y != null && y.color == Color.RED) {
z.parent!!.color = Color.BLACK
y.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
z = z.parent!!.parent!!
} else {
if (z == z.parent!!.right) {
z = z.parent!!
leftRotate(z)
}
z.parent!!.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
rightRotate(z.parent!!.parent!!)
}
} else {
y = z.parent!!.parent!!.left
if (y != null && y.color == Color.RED) {
z.parent!!.color = Color.BLACK
y.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
z = z.parent!!.parent!!
} else {
if (z == z.parent!!.left) {
z = z.parent!!
rightRotate(z)
}
z.parent!!.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
leftRotate(z.parent!!.parent!!)
}
}
}
root!!.color = Color.BLACK
}
fun inorder() = inorderHelper(root)
private fun inorderHelper(root: Node?) {
if (root == null) return
inorderHelper(root.left)
println("${root.key} - ${root.color}")
inorderHelper(root.right)
}
}
// client code to test Red-Black Tree Implementation in Kotlin
fun main() {
val tree = RedBlackTree()
tree.insert(7)
tree.insert(6)
tree.insert(5)
tree.insert(4)
tree.insert(3)
tree.insert(2)
tree.insert(1)
tree.inorder()
}
Output:
1 - BLACK 2 - RED 3 - BLACK 4 - RED 5 - BLACK 6 - RED 7 - BLACK
Explanation:
1. A Red-Black Tree ensures that the tree remains balanced after every insertion and deletion operation.
2. Each Node contains a key, color, and references to parent, left, and right child.
3. The tree class (RedBlackTree) provides utility functions:
- Rotation methods (leftRotate and rightRotate) to help in re-balancing.
- fixViolations method ensures that the Red-Black Tree properties are maintained after each insertion.
4. insert is a recursive function that places the new node in the correct position and then uses fixViolations to correct any color imbalances.
5. The inorder function is used for in-order traversal to display the tree's nodes.
6. The main function demonstrates the insertion of several nodes and then displays them using in-order traversal.
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