Red-Black Tree

How Red-Black Tree Works

A Red-Black Tree is a self-balancing binary search tree with an extra bit of data per node: its color, which can be either red or black. By constraining the way nodes can be colored, Red-Black Trees ensure that the tree remains approximately balanced during insertions and deletions.

Properties of Red-Black Trees:

• Every node is either red or black.
• The root is always black.
• Every leaf (NIL) is black.
• If a node is red, then both its children are black.
• For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Key operations:

• Insertion: O(log n)
• Deletion: O(log n)
• Search: O(log n)

Balancing in Red-Black Trees is achieved through color changes and rotations. After insertion or deletion, the tree may need to be adjusted to maintain its properties. This is done by recoloring nodes and performing rotations.

Red-Black Trees are widely used in computer science, particularly in implementations of associative arrays, such as the map and set data structures in many programming languages.

class Node:
    value
    left
    right
    color

class RedBlackTree:
    root

    function insert(value):
        root = insertRecursive(root, value)
        root.color = BLACK
        visualize()

    function insertRecursive(node, value):
        if node is null:
            return new Node(value, RED)
        if value < node.value:
            node.left = insertRecursive(node.left, value)
        else if value > node.value:
            node.right = insertRecursive(node.right, value)
        else:
            return node

        if isRed(node.right) and !isRed(node.left):
            node = rotateLeft(node)
        if isRed(node.left) and isRed(node.left.left):
            node = rotateRight(node)
        if isRed(node.left) and isRed(node.right):
            flipColors(node)

        return node

    function rotateLeft(node):
        x = node.right
        node.right = x.left
        x.left = node
        x.color = node.color
        node.color = RED
        return x

    function rotateRight(node):
        x = node.left
        node.left = x.right
        x.right = node
        x.color = node.color
        node.color = RED
        return x

    function flipColors(node):
        node.color = RED
        node.left.color = BLACK
        node.right.color = BLACK