C++ 红黑树设计与实现详解

3. 红黑树的插入

插入是红黑树最复杂的部分。插入后需调整以满足红黑性质。新节点默认为红色，若父节点为黑色则无需调整；若父节点为红色，则违反规则 3，需进行变色或旋转。

设当前节点为 cur，父节点为 p，祖父节点为 g，叔叔节点为 u。

3.1 插入流程概览

1. 若树为空，直接插入黑色根节点。
2. 若树非空，按 BST 规则找到位置插入红色节点。
3. 检查是否违反规则，若父节点为红色，进入调整循环。

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->_left;
        } else if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false; // 重复节点不插入
        }
    }

    cur = new Node(kv);
    cur->_col = RED;
    cur->_parent = parent;

    if (parent->_kv.first < kv.first) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }

    // 开始调整
    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        // ... 后续调整逻辑
    }
    _root->_col = BLACK;
    return true;
}

3.2 情况一：叔叔节点存在且为红色

此时 cur 和 p 为红，g 为黑，u 为红。策略是将 p 和 u 变为黑色，g 变为红色。然后将 g 视为新的 cur 继续向上检查。若 g 为根节点，最后将其染黑。

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

3.3 情况二：叔叔节点不存在或为黑色（单旋 + 变色）

当 u 为黑或不存在时，需结合旋转。若 cur 和 p 同侧（如左左），以 g 为轴右旋，变色后结束；若不同侧（如左右），先左旋再右旋。

左左情况（右单旋）：

if (parent->_left == cur) {
    RotateR(grandfather);
    parent->_col = BLACK;
    grandfather->_col = RED;
    break;
}

3.4 情况三：双旋 + 变色

当 cur 和 p 异侧时（如 p 是 g 左，cur 是 p 右），需先对 p 左旋，再对 g 右旋，最后变色。

RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;

4. 红黑树的验证

编写代码时需验证四条规则，特别是黑高一致性。

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nullptr) {
        if (refNum != blackNum) {
            cout << "黑高不一致" << endl;
            return false;
        }
        return true;
    }
    if (root->_col == RED && root->_parent->_col == RED) {
        cout << "连续红色节点" << endl;
        return false;
    }
    if (root->_col == BLACK) {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum) && 
           Check(root->_right, blackNum, refNum);
}

5. 关于删除

红黑树的删除逻辑比插入更为复杂，涉及多种旋转和颜色调整情况。本文主要聚焦于插入实现，删除操作建议参考专业文献或后续深入学习。

6. 完整代码

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
#include<ctime>

namespace wang {
using namespace std;

enum Colour { RED, BLACK };

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

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

template<class K, class V>
class RBTree {
    typedef RBTreeNode<K, V> Node;
private:
    void RotateR(Node* parent) {
        Node* subl = parent->_left;
        Node* sublR = subl->_right;
        parent->_left = sublR;
        if (sublR) sublR->_parent = parent;
        Node* ppnode = parent->_parent;
        subl->_right = parent;
        parent->_parent = subl;
        if (ppnode == nullptr) {
            _root = subl;
            subl->_parent = nullptr;
        } else {
            if (subl->_kv.first > ppnode->_kv.first) ppnode->_right = subl;
            else ppnode->_left = subl;
            subl->_parent = ppnode;
        }
    }

    void RotateL(Node* parent) {
        Node* subL = parent->_right;
        Node* subLL = subL->_left;
        Node* ppnode = parent->_parent;
        parent->_right = subLL;
        if (subLL) subLL->_parent = parent;
        subL->_left = parent;
        parent->_parent = subL;
        if (ppnode == nullptr) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (subL->_kv.first > ppnode->_kv.first) ppnode->_right = subL;
            else ppnode->_left = subL;
            subL->_parent = ppnode;
        }
    }

    void _InOrder(Node* root) {
        if (!root) return;
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }

public:
    bool Insert(const pair<K, V>& kv) {
        if (!_root) {
            _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->_left;
            } else if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else {
                return false;
            }
        }
        cur = new Node(kv);
        cur->_col = RED;
        cur->_parent = parent;
        if (parent->_kv.first < kv.first) parent->_right = cur;
        else parent->_left = cur;

        while (parent && parent->_col == RED) {
            Node* grandfather = parent->_parent;
            if (grandfather->_left == parent) {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED) {
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    if (parent->_left == cur) {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            } else {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED) {
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    if (parent->_right == cur) {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return true;
    }

    Node* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_kv.first > key) cur = cur->_left;
            else if (cur->_kv.first < key) cur = cur->_right;
            else return cur;
        }
        return nullptr;
    }

    void InOrder() { _InOrder(_root); }

    bool Check(Node* root, int blackNum, const int refNum) {
        if (!root) {
            if (refNum != blackNum) return false;
            return true;
        }
        if (root->_col == RED && root->_parent->_col == RED) return false;
        if (root->_col == BLACK) blackNum++;
        return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
    }

    bool IsBalance() {
        if (!_root) return true;
        if (_root->_col == RED) return false;
        int refNum = 0;
        Node* cur = _root;
        while (cur) {
            if (cur->_col == BLACK) ++refNum;
            cur = cur->_left;
        }
        return Check(_root, 0, refNum);
    }

protected:
    int _Size(Node* root) {
        if (!root) return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;
    }
    int _Height(Node* root) {
        if (!root) return 0;
        int l = _Height(root->_left);
        int r = _Height(root->_right);
        return l > r ? l + 1 : r + 1;
    }

private:
    Node* _root = nullptr;
};
}

7. 小结

红黑树通过颜色约束和旋转操作维持平衡，是工程实践中非常高效的数据结构。掌握其插入原理有助于深入理解 STL 容器及底层算法设计。后续可进一步研究删除操作的复杂性。