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

2.2 查找操作

查找逻辑与普通二叉搜索树一致，时间复杂度为 O(log N)。若找不到目标键值，返回 nullptr。

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;
}

3. 红黑树的插入

插入是红黑树最复杂的部分。新节点默认为红色，如果插入后违反规则（主要是连续红色），则需要通过变色或旋转来修复。

3.1 插入流程概览

1. 空树：直接插入黑色根节点。
2. 非空树：按 BST 规则找到位置插入红色节点。
3. 冲突处理：若父节点也是红色，则触发调整机制。此时需引入叔叔节点（Uncle）概念，分为三种情况讨论。

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; // 新节点默认红
    
    if (parent->_kv.first < kv.first)
        parent->_right = cur;
    else
        parent->_left = cur;
    
    cur->_parent = parent;

    // 开始调整平衡
    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;
}

3.2 旋转操作

旋转逻辑与 AVL 树类似，需注意更新父子指针关系。

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;
    else {
        if (ppnode->_left == parent) ppnode->_left = subl;
        else ppnode->_right = subl;
    }
    subl->_parent = ppnode;
}

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

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 << root->_kv.first << "存在连续的红色结点" << endl;
        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);
}

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<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) {}
};

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;
        else {
            if (ppnode->_left == parent) ppnode->_left = subl;
            else ppnode->_right = subl;
        }
        subl->_parent = ppnode;
    }

    void RotateL(Node* parent) {
        Node* subL = parent->_right;
        Node* subLL = subL->_left;
        parent->_right = subLL;
        if (subLL) subLL->_parent = parent;
        
        Node* ppnode = parent->_parent;
        subL->_left = parent;
        parent->_parent = subL;
        
        if (ppnode == nullptr) _root = subL;
        else {
            if (ppnode->_left == parent) ppnode->_left = subL;
            else ppnode->_right = 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;
        
        if (parent->_kv.first < kv.first)
            parent->_right = cur;
        else
            parent->_left = cur;
        
        cur->_parent = parent;

        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) {
                cout << "存在黑色结点的数量不相等的路径" << endl;
                return false;
            }
            return true;
        }
        if (root->_col == RED && root->_parent->_col == RED) {
            cout << root->_kv.first << "存在连续的红色结点" << endl;
            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);
    }

    int Height() { return _Height(_root); }
    int Size() { return _Size(_root); }

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 leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

private:
    Node* _root = nullptr;
};

void TestRBTree1() {
    RBTree<int, int> t;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) t.Insert({ e, e });
    t.InOrder();
    cout << t.IsBalance() << endl;
}

void TestRBTree2() {
    const int N = 1000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i++) v.push_back(rand() + i);
    
    size_t begin2 = clock();
    RBTree<int, int> t;
    for (auto e : v) t.Insert(make_pair(e, e));
    size_t end2 = clock();
    
    cout << t.IsBalance() << endl;
    cout << "RBTree Insert:" << end2 - begin2 << endl;
    cout << "RBTree Height:" << t.Height() << endl;
    cout << "RBTree Size:" << t.Size() << endl;
}
}

7. 总结

红黑树通过颜色约束和旋转操作，在保证 O(log N) 查找效率的同时，减少了频繁旋转带来的开销。理解其插入过程中的三种调整情况（变色、单旋、双旋）是掌握该数据结构的关键。在实际工程中，STL 容器已封装了这些细节，但深入源码有助于优化性能调优与故障排查。