红黑树插入修复全记录：从旋转到颜色调整

红黑树插入修复全记录：从旋转到颜色调整

红黑树的五条规则不算复杂，但动手实现插入时，修复逻辑会一直向上蔓延。下面结合 C++ 代码，把关键步骤走一遍。

五条规则

• 节点非红即黑。
• 根节点黑色。
• 红色节点的子节点必须黑色（不能连续红）。
• 任意节点到其叶子节点的路径上黑色节点数相同。
• 叶子（NIL）视为黑色。

这些约束靠颜色和旋转维持，保证树高 O(log n)，从而查找、插入、删除最坏也是对数级。

高度边界

黑色高度 bh 是从根到叶路径上的黑节点数。最短路径全黑，长度 bh；最长路径红黑交替，长度 2*bh。因此树高 ≤ 2 log(n+1)，这就是 O(log n) 的来源。

节点结构

enum Colour { RED, BLACK };

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

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

父指针方便向上回溯调整颜色，这是修复逻辑的骨架。

插入与修复

插入分两步：二叉查找插入，然后着色修复。新节点默认红色 —— 因为如果默认黑色，立刻破坏规则 4，需要全局调整，代价太大；红色只可能违反规则 3（连续红），局部处理就行。

修复的核心在于叔叔节点的颜色：

1. 叔叔红色：父、叔变黑，祖父变红，当前节点跳到祖父继续检查。
2. 叔叔黑色或不存在：需要旋转。根据节点、父、祖父的位置关系，可能单旋或双旋，并配合变色。

下面这段代码同时处理了左右对称的情况：

bool Insert( pair<K, V>& kv) {
     (_root == ) {
        _root =  (kv);
        _root->_col = BLACK;
         ;
    }

    Node* parent = ;
    Node* cur = _root;
     (cur) {
         (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        }   (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);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }  {
                    (parent);
                    (grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                ;
            }
        }
    }
    _root->_col = BLACK;
     ;
}