Red-Black Trees are a type of self-balancing binary search tree (BST) that enforce a set of coloring rules to maintain approximate balance, ensuring efficient search, insertion, and deletion operations. Their properties guarantee that the longest path from root to leaf is no more than twice the length of the shortest path.

The core rules of a Red-Black Tree are:

1. Every node is either RED or BLACK.
2. The root node is always BLACK.
3. No two adjacent RED nodes can exist (a RED node cannot have a RED parent or RED child).
4. For every path from a node to its descendant NULL nodes, the number of BLACK nodes must be the same.

These rules collective enforce the critical balance condition, limiting tree height.

Node Structure Definition

template <class Key, class Val>
struct RBNode {
    enum class NodeColor { RED, BLACK };

    std::pair<Key, Val> data;
    RBNode* left_child;
    RBNode* right_child;
    RBNode* parent_node;
    NodeColor color;

    RBNode(const std::pair<Key, Val>& element)
        : data(element),
          left_child(nullptr),
          right_child(nullptr),
          parent_node(nullptr),
          color(NodeColor::RED) {}
};

Insertion Logic and Rebalancing

New nodes are always inserted with a RED color. If the parent of the new node is BLACK, the insertion is complete. However, if the parent is RED, it violates rule 3, requiring rebalancing. The specific handling depends on the color of the 'uncle' node (the sibling of the parent).

Let cur be the newly inserted RED node, par its RED parent, grand its BLACK grandparent, and unc the uncle.

Case 1: Uncle Exists and is RED

Perform a color flip:

• Change par and unc to BLACK.
• Change grand to RED.
• If grand is the root, change it back to BLACK.
• If grand is not the root, set cur = grand and continue checking upwards.

Case 2: Uncle is BLACK or Absent

This case requires tree rotations. The specific rotation depends on the alignment of cur, par, and grand.

Subcase A: par is the left child of grand.

• If cur is the left child of par, perform a right rotation on grand. After rotation, par becomes BLACK and grand becomes RED.
• If cur is the right child of par, perform a left-right double rotation. First, left rotate par, then right rotate grand. After rotations, cur becomes BLACK and grand becomes RED.

Subcase B: par is the right child of grand.

• If cur is the right child of par, perform a left rotation on grand. After rotation, par becomes BLACK and grand becomes RED.
• If cur is the left child of par, perform a right-left double rotation. First, right rotate par, then left rotate grand. After rotations, cur becomes BLACK and grand becomes RED.

After handling Case 2, the tree is balanced, and no further upward propagation is needed.

Insertion Implementation

template <class K, class V>
bool RBTree<K, V>::insertElement(const std::pair<K, V>& keyVal) {
    // Standard BST insertion
    if (treeRoot == nullptr) {
        treeRoot = new RBNode<K, V>(keyVal);
        treeRoot->color = NodeColor::BLACK;
        return true;
    }

    RBNode<K, V>* newNode = treeRoot;
    RBNode<K, V>* parentNode = nullptr;

    while (newNode) {
        parentNode = newNode;
        if (keyVal.first < newNode->data.first) {
            newNode = newNode->left_child;
        } else if (keyVal.first > newNode->data.first) {
            newNode = newNode->right_child;
        } else {
            return false; // Duplicate key
        }
    }

    newNode = new RBNode<K, V>(keyVal);
    if (keyVal.first < parentNode->data.first) {
        parentNode->left_child = newNode;
    } else {
        parentNode->right_child = newNode;
    }
    newNode->parent_node = parentNode;

    // Rebalancing after insertion
    RBNode<K, V>* current = newNode;
    while (parentNode && parentNode->color == NodeColor::RED) {
        RBNode<K, V>* grandParent = parentNode->parent_node;
        bool parentIsLeftChild = (parentNode == grandParent->left_child);
        RBNode<K, V>* uncleNode = parentIsLeftChild ? grandParent->right_child : grandParent->left_child;

        // Case 1: Red Uncle
        if (uncleNode && uncleNode->color == NodeColor::RED) {
            parentNode->color = NodeColor::BLACK;
            uncleNode->color = NodeColor::BLACK;
            grandParent->color = NodeColor::RED;
            current = grandParent;
            parentNode = current->parent_node;
        } else { // Case 2: Black or Null Uncle
            if (parentIsLeftChild) {
                if (current == parentNode->right_child) { // Left-Right Case
                    rotateLeft(parentNode);
                    std::swap(current, parentNode); // After rotation, roles swap
                }
                rotateRight(grandParent);
                grandParent->color = NodeColor::RED;
                parentNode->color = NodeColor::BLACK;
            } else {
                if (current == parentNode->left_child) { // Right-Left Case
                    rotateRight(parentNode);
                    std::swap(current, parentNode);
                }
                rotateLeft(grandParent);
                grandParent->color = NodeColor::RED;
                parentNode->color = NodeColor::BLACK;
            }
            break; // Rebalancing complete for Case 2
        }
    }
    treeRoot->color = NodeColor::BLACK; // Ensure root is black
    return true;
}

Tree Validation

A valid Red-Black Tree must satisfy all its core rules. The validation process checks:

1. The root node is BLACK.
2. No RED node has a RED child.
3. All root-to-leaf paths contain the same number of BLACK nodes.

template <class K, class V>
bool RBTree<K, V>::isValidRBTree() const {
    if (treeRoot == nullptr) return true;
    if (treeRoot->color != NodeColor::BLACK) return false;

    // Calculate the reference black count from the leftmost path
    int referenceBlackCount = 0;
    RBNode<K, V>* nodePtr = treeRoot;
    while (nodePtr) {
        if (nodePtr->color == NodeColor::BLACK) referenceBlackCount++;
        nodePtr = nodePtr->left_child;
    }
    return validateSubtree(treeRoot, 0, referenceBlackCount);
}

template <class K, class V>
bool RBTree<K, V>::validateSubtree(RBNode<K, V>* node, int currentBlackCount, int referenceCount) const {
    if (node == nullptr) {
        return currentBlackCount == referenceCount;
    }
    // Check for consecutive red nodes
    if (node->color == NodeColor::RED) {
        if (node->left_child && node->left_child->color == NodeColor::RED) return false;
        if (node->right_child && node->right_child->color == NodeColor::RED) return false;
    }
    // Update black node count for this path
    int updatedCount = currentBlackCount;
    if (node->color == NodeColor::BLACK) updatedCount++;
    // Recursively validate left and right subtrees
    return validateSubtree(node->left_child, updatedCount, referenceCount) &&
           validateSubtree(node->right_child, updatedCount, referenceCount);
}