What is a Red-Black Tree?

A Red-Black Tree is another type of self-balancing binary search tree. It maintains balance by ensuring a set of properties are met, which involve coloring each node either red or black. These properties ensure that the longest path from the root to any leaf is no more than twice as long as the shortest path.

What are the properties of a Red-Black Tree?

The five key properties are: 1. Every node is either red or black. 2. The root is black. 3. Every leaf (NIL) is black. 4. If a node is red, then both its children are black. 5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Data Structures

Red-Black Tree

A widely-used self-balancing binary search tree that guarantees logarithmic time complexity for all major operations through a clever node-coloring system.

Red-Black Tree Conceptual Overview

Implementing a Red-Black Tree from scratch is a significant undertaking and rarely expected in a standard coding interview. The focus is usually on understanding its properties and performance characteristics.

# Red-Black Tree implementation is complex and typically not required in interviews.
# Below are the core properties that define a Red-Black Tree.

class RedBlackNode:
    def __init__(self, key, color='RED'):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

# Key Properties:
# 1. Every node is either Red or Black.
# 2. The root is always Black.
# 3. There are no two adjacent Red nodes (A Red node cannot have a Red parent or Red child).
# 4. Every path from a node to any of its descendant NIL nodes has the same number of Black nodes.
# 5. All NIL leaves are Black.

AI Coach Hint: While AVL trees are more strictly balanced, Red-Black trees require fewer rotations on average for insertions and deletions. This makes them a better choice in write-heavy scenarios. This trade-off is why they are used in many standard library implementations, like `std::map` and `std::set` in C++.