C++ 红黑树：插入与平衡修复的直观理解

红黑树是自平衡二叉查找树的一种，通过节点颜色和旋转维持近似平衡。实际用起来比 AVL 树省旋转，插入删除更轻量。

概念与性质

一棵合格的红黑树需要同时满足：

• 每个节点要么红要么黑。
• 根节点是黑色。
• 红色节点的两个子节点必须黑色（没有连续红）。
• 从任意节点到其后代所有叶子节点的简单路径上，黑色节点数量相同。
• 叶子节点（空节点）视为黑色。

这些规则共同保证了树的高度不会超过 2log(n+1)，也就是最长路径不会超过最短路径的两倍。直观理解：最短路径全黑，最长路径红黑交替。由于黑色节点数相等，红节点最多和黑节点一样多，所以最长路径最多是黑节点数的两倍，也就是最短路径的两倍。

节点结构及默认红色

enum Colour { RED, BLACK };

template<class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) {}
};

新节点默认染成红色，主要是为了减少对黑色路径计数的影响。如果插个黑节点，必然破坏'同路径黑节点数相等'的性质，修复起来很麻烦。红色节点只可能造成'连续红'冲突，处理起来大多只需变色或加少量旋转，调整成本更低。

插入过程

插入操作分为标准的 BST 插入和随后的红黑性质修复。

typedef RBTreeNode<K, V> Node;

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        }  {
             ;
        }
    }

    cur =  (kv);
    cur->_col = RED;
     (parent->_kv.first < kv.first) {
        parent->_right = cur;
    }  {
        parent->_left = cur;
    }
    cur->_parent = parent;

    
     (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        
         (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            
             (uncle && uncle->_col == RED) {
                
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            }  {
                
                 (cur == parent->_left) {
                    
                    (grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }  {
                    
                    (parent);
                    (grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                ;
            }
        }  {
            Node* uncle = grandfather->_left;
            
             (uncle && uncle->_col == RED) {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            }  {
                 (cur == parent->_right) {
                    
                    (grandfather);
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                }  {
                    
                    (parent);
                    (grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                ;
            }
        }
    }
    _root->_col = BLACK;
     ;
}