C++ 红黑树核心原理与插入实现详解

C++ 红黑树设计与实现

1. 红黑树的概念

1.1 什么是红黑树

红黑树是一种自平衡的二叉搜索树。它在每个节点上增加了一个存储位来表示颜色（红色或黑色）。通过对从根到叶子路径上节点颜色的约束，红黑树确保没有一条路径会比其他路径长出两倍，从而保持近似平衡。

它是一棵被严格规则束缚的二叉搜索树，这些规则保证了树的相对平衡性。下面我们来详细看看这些规则。

1.2 红黑树的五条性质

1. 每个节点要么是红色，要么是黑色。
2. 根节点必须是黑色。
3. 如果一个节点是红色的，则它的两个子节点都必须是黑色的（即不能有两个连续的红色节点）。
4. 对任意节点而言，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。
5. 所有的叶子节点（NULL 指针）都是黑色的。

注意：这里的'叶子节点'通常指 NULL 指针，有些书籍称之为外部节点。引入 NULL 节点是为了方便准确地标记路径边界。

1.3 为什么最长路径不超过最短路径的两倍

根据性质 4，每条路径上的黑色节点数量是固定的，记为 bh（Black Height）。

• 最短路径：全由黑色节点组成，长度为 bh。
• 最长路径：在满足性质 3（无连续红节点）的前提下，红黑交替出现，长度最多为 2 * bh。

因此，红黑树的最长路径不会超过最短路径的两倍，这保证了树的高度约为 log N。

1.4 效率分析

假设节点数为 N，高度为 h。由于 2^h - 1 <= N < 2^(2h) - 1，可推导出 h ≈ log N。这意味着红黑树的查找、插入和删除操作的时间复杂度均为 O(log N)。

相比于 AVL 树，红黑树对平衡性的要求稍宽松，因此在插入和删除时旋转次数更少，整体性能更稳定。

2. 红黑树的实现

2.1 节点结构

在编写代码前，我们需要定义节点结构。红黑树通常采用三叉链表，节点需包含父节点指针、左右孩子指针以及颜色属性。我们使用 Key-Value 结构存储数据，Key 用于比较大小，Value 为实际数据。

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:
    Node* _root = nullptr;
    // ... 后续方法
};

2.2 查找操作

红黑树的查找逻辑与普通二叉搜索树一致，时间复杂度为 O(log N)。

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. 红黑树的插入

插入是红黑树中最复杂的部分之一。新节点默认插入为红色，以不破坏性质 4（黑色节点高度）。如果插入后违反性质 3（双红冲突），则需要通过变色和旋转来修复。

3.1 插入流程概览

1. 若树为空，直接插入黑色根节点。
2. 若树非空，按 BST 规则找到位置，插入红色节点。
3. 检查是否违反性质 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; // 新节点默认为红
    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 均为红色，且叔叔节点 u 存在且为红色时，说明祖父节点 g 必然为黑色。此时将 p 和 u 变为黑色，g 变为红色，并将 g 视为新的当前节点继续向上检查。

若 g 变为根节点，则必须将其染回黑色。

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 {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED) {
            grandfather->_col = RED;
            parent->_col = BLACK;
            uncle->_col = BLACK;
            cur = grandfather;
            parent = cur->_parent;
        }
    }
}

3.3 情况二：叔叔节点为黑色 + 同侧（单旋 + 变色）

当叔叔节点不存在或为黑色，且当前节点与父节点位于同一侧（如左左或右右）时，进行单旋并交换颜色。

• 左左：以祖父为轴右旋，父变黑，祖父变红。
• 右右：以祖父为轴左旋，父变黑，祖父变红。

if (grandfather->_left == parent) {
    Node* uncle = grandfather->_right;
    if (!uncle || uncle->_col == BLACK) {
        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 == BLACK) {
        if (parent->_right == cur) {
            // 右右 -> 左旋
            RotateL(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
        } else {
            // 右左 -> 双旋
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
        }
        break;
    }
}

3.4 情况三：叔叔节点为黑色 + 异侧（双旋 + 变色）

当叔叔节点为黑色，且当前节点与父节点位于异侧（如左右或右左）时，先对父节点进行单旋，再对祖父节点进行反向单旋，最后变色。

• 左右：先左旋父，再右旋祖父，当前节点变黑，祖父变红。
• 右左：先右旋父，再左旋祖父，当前节点变黑，祖父变红。

(注：上述代码片段已涵盖此逻辑)

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 == nullptr) 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>

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;
            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 == nullptr) 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 == 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;
            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 == 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 == nullptr) 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 == nullptr) return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;
    }
    int _Height(Node* root) {
        if (root == nullptr) return 0;
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

private:
    Node* _root = nullptr;
};

7. 小结

红黑树通过严格的颜色约束实现了高效的自平衡。虽然删除操作较为复杂，但掌握插入过程中的三种调整情况（变色、单旋、双旋）足以理解其核心平衡机制。在实际开发中，STL 的 map 和 set 底层正是基于红黑树实现的，理解其原理有助于更好地利用标准库容器。