C++ 红黑树核心原理与实战实现

3. 红黑树的插入与平衡

插入新节点时，默认将其设为红色。若违反规则（如父节点也是红色），则需要通过变色和旋转来恢复平衡。我们定义三个关键节点：当前节点 c(cur)、父节点 p(parent)、祖父节点 g(grandfather)，以及叔叔节点 u(uncle)。

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;
    // 连接节点
    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;
        // ... 分情况处理 ...
    }
    _root->_col = BLACK;
    return true;
}

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

当 c 和 p 均为红色，且叔叔 u 也为红色时，将 p 和 u 染黑，g 染红。此时 g 可能违反规则，需将 g 视为新的 c 继续向上调整。

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 情况二：叔叔节点不存在或为黑色（单旋 + 变色）

当 p 是 g 的左孩子，c 是 p 的左孩子（左左型），以 g 为轴右旋，p 变黑，g 变红。反之亦然（右右型左旋）。

if (uncle == nullptr || uncle->_col == BLACK) {
    if (parent->_left == cur) { // 左左型
        RotateR(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
    } else { // 左右型，见情况三
        // ...
    }
}

3.4 情况三：叔叔节点不存在或为黑色（双旋 + 变色）

当 p 是 g 的左孩子，但 c 是 p 的右孩子（左右型），先以 p 为轴左旋，再以 g 为轴右旋。最后调整颜色。

// 左右双旋转
RotateL(parent);
RotateR(gradfather);
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 << root->_kv.first << "存在连续的红色结点" << 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;
        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;
        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->_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) 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);
    }

private:
    Node* _root = nullptr;
};
}

7. 小结

红黑树通过颜色约束和旋转操作，在插入删除频繁的场景下提供了稳定的性能表现。掌握其插入逻辑是理解平衡树的关键一步。后续可进一步研究删除操作的复杂情形。