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

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

前言

在深入平衡二叉搜索树的学习中，AVL 树让我们理解了高度平衡的重要性。而红黑树（Red-Black Tree）则是另一种更为实用且高效的平衡方案，它是 C++ STL 中 map 和 set 等容器的底层实现核心。相比 AVL 树严格的平衡要求，红黑树通过颜色标记来近似平衡，牺牲了部分查询效率换取了更少的旋转操作，从而在插入和删除场景下表现更佳。

1. 红黑树的概念

1.1 什么是红黑树

红黑树是一种自平衡的二叉搜索树。除了每个节点存储键值对外，它还增加了一个颜色属性，节点颜色只能是红色或黑色。通过对路径上节点颜色的约束，确保没有一条路径会比其他路径长出两倍，从而实现近似平衡。

1.2 红黑树的五条规则

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

注：这里的叶子节点通常指空指针，而非传统意义上的终端节点。《算法导论》中常将 NULL 视为外部节点。

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

根据规则 4，每条路径上的黑色节点数量（黑高 bh）是固定的。最短路径即为全黑节点路径，长度为 bh。由于规则 3 限制了红色节点不能连续出现，最长路径必然是红黑交替，长度约为 2bh。因此，红黑树的最长路径不会超过最短路径的两倍。

1.4 效率分析

假设节点数为 N，最短路径长度为 h。由 2^h - 1 <= N < 2^(2h) - 1 可知，h 约等于 logN。因此，红黑树的查找、插入、删除时间复杂度均为 O(logN)。虽然比 AVL 树略慢，但插入时的旋转次数更少，整体性能更优。

2. 红黑树的实现

2.1 节点结构

红黑树采用三叉链表结构，每个节点需要记录父节点、左右孩子以及颜色信息。默认新插入节点为红色。

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

2.2 查找操作

红黑树的查找逻辑与二叉搜索树完全一致，利用 Key 进行比较，时间复杂度 O(logN)。

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，需进行变色或旋转。

设当前节点为 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 容器及底层算法设计。后续可进一步研究删除操作的复杂性。