Red-Black Trees 🎯

Welcome to our deep dive into Red-Black Trees! This lesson is perfect for beginners and intermediates who want to understand this efficient data structure. Let's get started!

What is a Red-Black Tree? 💡

A Red-Black Tree is a self-balancing binary search tree, which means it maintains a balance that ensures quick search, insert, and delete operations. This tree has additional nodes to maintain balance, and it uses colors to keep track of them.

Why Red-Black Trees? 📝

Red-Black Trees are a popular choice because they provide a good balance between efficiency and simplicity. They offer average time complexity of O(log n) for various operations like search, insert, and delete, just like other balanced binary search trees. However, they are easier to implement and more resilient to imbalances than AVL trees.

Basic Rules and Colors 💡

All nodes are either red or black.
The root node is always black.
Leaf nodes (null or empty nodes) are also black.
Every red node must have two black children.
From any node, the number of red nodes on the path from the node to any of its descendants' leaf nodes is at most 1.

Key Operations 💡

Insert: We insert a new node and then perform some balance operations to ensure the tree remains balanced.
Delete: We remove a node and again balance the tree to maintain its properties.
Search: We traverse the tree using standard binary search tree operations to find a specific node.

Example: Inserting a Node ✅

python

class Node:
    def __init__(self, key, color):
        self.key = key
        self.color = color
        self.left = None
        self.right = None

class RedBlackTree:
    def insert(self, root, key):
        if not root:
            return Node(key, 'red')

        if root.color == 'red':
            root = self.rotateLeft(root)

        if key < root.key:
            root.left = self.insert(root.left, key)
            self.fixViolation(root)
        else:
            root.right = self.insert(root.right, key)
            self.fixViolation(root)

        return root

Quick Quiz

Question 1 of 1

What is the time complexity of the insert operation in a Red-Black Tree?


## Example: Deleting a Node ✅

```python
class RedBlackTree:
    def delete(self, root, key):
        if not root:
            return None

        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            if root.left is None:
                return root.right

            if root.right is None:
                return root.left

            temp = self.minValueNode(root.right)
            root.key = temp.key
            root.right = self.delete(root.right, temp.key)

        if self.isRed(root.left) and self.isRed(root.right):
            root.color = 'red'
            root = self.rotateLeft(root)
            root = self.rotateRight(root)
            root.color = 'black'

        return root

Quick Quiz

Question 1 of 1

What is the time complexity of the delete operation in a Red-Black Tree?


## Balancing the Tree 💡

After performing an insert or delete operation, the tree may become unbalanced. To fix this, we apply a series of rotations and color flips to bring the tree back to its balanced state.

## Wrapping Up 📝

Red-Black Trees are a powerful data structure that offers efficient search, insert, and delete operations. They are easier to implement than AVL trees and are a great choice for self-balancing binary search trees.

Now that you've learned the basics, try your hand at [this quiz](#red-black-tree-quiz) to test your understanding! Happy coding! 🤓💻