C++红黑树Map完整实现：键值对存储与高效操作

在写代码时，常常需要在数组中查找值，在普通的数组中，查找一次的时间在最坏情况下是数组的长度，也就是$O(n)$，当需要大量查找时便会超时。

这时候就有了AVL树（平衡二叉树），能够将将查找、添加与删除的时间平摊为$logn$，但是在某些极端情况下，它的时间为$n$，而红黑树不管在任何情况下都是$logn$。

红黑树是一种自平衡二叉搜索树，也是一种高级数据结构，牺牲部分平衡性（不像AVL树那样严格平衡），换取了更高效的插入/删除操作，能够将查找、添加与删除的时间平摊为$logn$，时间复杂度为$O(logn)$。

红黑树整棵树的节点都分为红色与黑色，在构建红黑树时，需要遵循红黑树的规则：

• 根节点为黑
• 叶子节点（NIL）为黑
• 红节点的子节点必须为黑
• 从任一节点到其叶子的所有路径包含相同数量的黑节点
• 所有节点都为红或黑

红黑树保证最长路径不超过最短路径的二倍，因为最长为 黑-红-黑-红-黑，最短为 黑-黑-黑 因而近似平衡。

红黑树的基本节点：

• parent（父亲节点）
• brother（兄弟节点）
• uncle（父亲的兄弟节点）
• grandpa（祖父节点（父亲的父亲节点））
• nil（哨兵节点）

红黑树的基本操作有

• 左旋
• 右旋
• 插入
• 查找
• 删除
• 维护平衡等

用代码实现红黑树：

先创建节点的红黑性：

//先创建节点的红黑性
enum Color { RED, BLACK };//非黑即红

//C++万能模版
template <typename Key, typename Value>
//单个节点
class RBTreeNode {
	public:
	    Key key;//键
	    Value value;//值
	    Color color;//颜色（红黑）
	    RBTreeNode *left, *right, *parent;//兄弟节点，父亲节点
	
	    RBTreeNode(Key k, Value v, Color c = RED)//自动赋值函数
	        : key(k), value(v), color(c),//赋值
	        left(nullptr), right(nullptr), parent(nullptr) {}//默认节点
};

构造一棵红黑树

template <typename Key, typename Value>//C++万能模版
class RBTree {//构造一个类
	private://隐藏
		RBTreeNode<Key, Value>* root;//根节点
		RBTreeNode<Key, Value>* nil;// 哨兵节点
	public:
		
}

哨兵节点初始化

RBTree() {
    nil = new RBTreeNode<Key, Value>(Key(), Value(), BLACK);
    nil->left = nil->right = nil->parent = nil;
    root = nil;
}

功能：

• 创建哨兵节点（NIL节点）
• 初始化哨兵节点的指针指向自身
• 将根节点指向哨兵节点

关键点：

• 哨兵节点颜色为黑色（满足红黑树性质）
• 所有叶子节点都指向哨兵节点
• 简化边界条件处理
• 根节点初始化为哨兵节点（表示空树）

左旋操作（将节点的右子节点提升为新的父节点）

• 获取当前节点x的右子节点y
• 将x的右子节点指向y的左子节点
• 如果y的左子节点非空，设置其父节点为x
• 将y的父节点指向x的父节点
• 更新x父节点的子节点引用
• 将y的左子节点指向x
• 将x的父节点指向y

void leftRotate(RBTreeNode<Key, Value>* x) {
	// Step 1: 获取右子节点y
	RBTreeNode<Key, Value>* y = x->right;
	// Step 2: 将x的右子节点设为y的左子节点
	x->right = y->left;
	// Step 3: 如果y的左子节点非空，设置其父节点
	if (y->left != nil)
		y->left->parent = x;
	// Step 4: 将y的父节点指向x的父节点
	y->parent = x->parent;
	// Step 5: 更新父节点的子节点引用
	if (x->parent == nil)
		root = y;// x是根节点
	else if (x == x->parent->left)
		x->parent->left = y;
	else
		x->parent->right = y;
	// Step 6: 将y的左子节点指向x
	y->left = x;
	// Step 7: 将x的父节点指向y
	x->parent = y;
}

示意图：

      x                                   y
     / \                                 / \
    a   y      =左旋(x)=>          x    c
       / \                             / \
      b   c                           a   b

旋转后搜索树性质不变：c > y > b > x > a --> a < x < b < y < c

右旋（将节点的左子节点提升为新的父节点）

• 获取当前节点y的左子节点x
• 将y的左子节点指向x的右子节点
• 如果x的右子节点非空，设置其父节点为y
• 将x的父节点指向y的父节点
• 更新y父节点的子节点引用
• 将x的右子节点指向y
• 将y的父节点指向x

void rightRotate(RBTreeNode<Key, Value>* y) {
	// Step 1: 获取左子节点x
	RBTreeNode<Key, Value>* x = y->left;
	// Step 2: 将y的左子节点设为x的右子节点
	y->left = x->right;
	// Step 3: 如果x的右子节点非空，设置其父节点
	if (x->right != nil)
		x->right->parent = y;
	// Step 4: 将x的父节点指向y的父节点
	x->parent = y->parent;
	// Step 5: 更新父节点的子节点引用
	if(y->parent == nil)
		root = x;  // y是根节点
	else if(y == y->parent->left) 
		y->parent->left = x;
	else
		y->parent->right = x;
	// Step 6: 将x的右子节点指向y
	x->right = y;
	// Step 7: 将y的父节点指向x
	y->parent = x;
}

旋转示意图：

text
      y                             x
     / \                           / \
    x   c      =右旋(y)=>         a   y
   / \                               / \
  a   b                             b   c

左旋和右旋是互逆操作

旋转操作非常有用，其本质是通过改变树的高度分布来维护红黑树的平衡性，还减少最长路径的长度，其时间复杂度为$O(1)$。

deepseek样例：

     z (新节点-RED)//这里的z不是根节点
    /
   p (RED)
  /
 g (BLACK)

1. 将父节点p设为BLACK
2. 将祖父节点g设为RED
3. 对g进行右旋

      p (BLACK)
     / \
    z   g (RED)这里的z，g不是叶子节点

插入

void insert(const Key& key, const Value& value) {
    RBTreeNode<Key, Value>* z = root;
    RBTreeNode<Key, Value>* parent = nil;

    // 1. 查找插入位置并检查是否已存在
    while (z != nil) {
        parent = z;
        if (key == z->key) {
            // 键已存在，更新值
            z->value = value;
            return;
        }
        else if (key < z->key)
            z = z->left;
        else
            z = z->right;
    }

    // 2. 创建新节点（初始为红色）
    z = new RBTreeNode<Key, Value>(key, value);
    z->parent = parent;
    z->left = z->right = nil;

    // 3. 将新节点连接到树中
    if (parent == nil)
        root = z;
    else if (key < parent->key)
        parent->left = z;
    else
        parent->right = z;

    // 4. 修复红黑树性质
    fixInsert(z);
}

标准BST插入

• 从根节点开始遍历
• 如果键已存在，更新值并返回
• 找到合适的插入位置（叶子节点）

2. 创建新节点

• 新节点初始化为红色（默认构造函数）
• 设置父节点指针
• 左右子节点指向哨兵nil

3. 连接新节点

• 空树处理：新节点成为根节点
• 非空树：根据键值大小连接到左/右子树

4. 修复红黑树性质

fixInsert(z); // 关键修复操作

因为插入红色节点可能违反红黑树的规则，特别是"红色节点的子节点必须为黑色"这一约束，所以我们要进行修复。

void fixInsert(RBTreeNode<Key, Value>* z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            // 父节点是祖父节点的左子
            RBTreeNode<Key, Value>* uncle = z->parent->parent->right;
            
            // Case 1: 叔节点为红色
            if (uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } 
            else {
                // Case 2: 叔节点为黑且z是右子
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(z);
                }
                // Case 3: 叔节点为黑且z是左子
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(z->parent->parent);
            }
        } 
        else { 
            // 对称情况：父节点是祖父节点的右子
            RBTreeNode<Key, Value>* uncle = z->parent->parent->left;
            
            if (uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } 
            else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(z->parent->parent);
            }
        }
    }
    root->color = BLACK; // 确保根节点为黑
}

修复操作的三种情况

情况1：叔节点为红色

       祖父(B)                祖父(R)//不是根
       /    \                 /    \
    父(R)  叔(R)   =>      父(B)  叔(B)
     /                     /
   z(R)                 z(R)//不是叶

处理步骤：

1. 将父节点和叔节点设为黑色
2. 将祖父节点设为红色
3. 将当前节点指向祖父节点
4. 继续向上检查

代码实现：

z->parent->color = BLACK;
uncle->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; // 向上追溯

情况2：叔节点为黑且z是右子

       祖父(B)               祖父(B)
       /                   /
    父(R)       =>       z(R)
       \               /
        z(R)        父(R)

处理步骤：

1. 将当前节点指向父节点
2. 对父节点进行左旋
3. 转为情况3处理

代码实现：

z = z->parent;
leftRotate(z);
// 转为情况3

情况3：叔节点为黑且z是左子

       祖父(B)               父(B)
       /                   /    \
    父(R)       =>       z(R)  祖父(R)
     /
   z(R)

处理步骤：

1. 将父节点设为黑色
2. 将祖父节点设为红色
3. 对祖父节点进行右旋

代码实现：

z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);

插入修复流程图

插入操作的时间复杂度

1. BST插入：O(log n)
   • 树的高度决定查找路径长度
2. 修复操作：O(log n)
   • 最多进行3次旋转
   • 颜色修改操作最多向上追溯O(log n)层
3. 总体复杂度：O(log n)

插入操作的特点

1. 新节点总是红色

   • 避免违反"从根到叶子的路径包含相同黑色节点"约束
   • 可能违反"红色节点不能有红色子节点"约束

2. 修复是局部的

   • 最多影响三代节点（父、祖父、叔）
   • 修复后子树的黑高不变

3. 向上递归

   • 情况1可能导致问题向上传播
   • 最多传播到根节点

4. 根节点特殊处理

   • 最后确保根节点为黑色
   • 可能增加整棵树的黑高

deepseek示例

插入序列：10, 20, 30, 15, 25

步骤1：插入10（根节点）

    10(B)

步骤2：插入20

    10(B)
      \
       20(R) -> 修复完成

步骤3：插入30（触发情况1）

情况1前:
    10(B)
      \
       20(R)
         \
          30(R)

情况1后:
    20(B)
   /    \
10(R)   30(R)

步骤4：插入15

    20(B)
   /    \
10(R)   30(R)
  \
   15(R) -> 无冲突

步骤5：插入25（触发情况2和3）

插入后:
       20(B)
      /    \
   10(B)   30(R)
     \      /
     15(R)25(R)

情况2（左旋30）:
       20(B)
      /    \
   10(B)   25(R)
     \       \
     15(R)   30(R)

情况3（右旋20）:
       25(B)
      /    \
   20(R)   30(R)
   /  
10(B)
   \
    15(R)

红黑树的插入操作将新节点初始化为红色，通过有限的旋转和重新着色操作高效地维护了树的平衡性

红黑树查找操作详解

红黑树的查找操作是其最基础也是最高效的操作之一。作为自平衡二叉搜索树，红黑树在插入和删除后自动调整结构，从而保证了查找操作的高效性。

查找操作的两种形式

1. find 方法：安全查找

Value* find(const Key& key) {
    RBTreeNode<Key, Value>* node = root;
    while (node != nil) {
        if (key == node->key)
            return &node->value;  // 返回值的指针
        else if (key < node->key)
            node = node->left;    // 向左子树搜索
        else
            node = node->right;   // 向右子树搜索
    }
    return nullptr; // 未找到
}

特点：

• 返回指向值的指针（找到时）
• 返回 nullptr（未找到时）
• 不会修改树结构
• 时间复杂度：O(log n)

使用示例：

int* score = tree.find("Alice");
if (score) {
    cout << "Alice的分数: " << *score << endl;
} else {
    cout << "未找到Alice" << endl;
}

2. operator[]：便捷访问（可能插入）

Value& operator[](const Key& key) {
    // 尝试查找键
    RBTreeNode<Key, Value>* node = root;
    RBTreeNode<Key, Value>* parent = nil;
    
    while (node != nil) {
        parent = node;
        if (key == node->key)
            return node->value;  // 直接返回值
        else if (key < node->key)
            node = node->left;
        else
            node = node->right;
    }
    
    // 键不存在：创建新节点
    node = new RBTreeNode<Key, Value>(key, Value());
    node->parent = parent;
    node->left = node->right = nil;
    
    // 连接新节点
    if (parent == nil)
        root = node;
    else if (key < parent->key)
        parent->left = node;
    else
        parent->right = node;
    
    // 修复红黑树性质
    fixInsert(node);
    return node->value;
}

特点：

• 返回值的引用
• 未找到时自动插入新节点（使用默认值）
• 可用于读取和修改值
• 时间复杂度：查找O(log n)，插入O(log n)

使用示例：

tree["Alice"] = 95;  // 插入或修改
int score = tree["Bob"];  // 读取（未找到则插入默认值）

查找操作详解

查找过程图示

        20(B)
       /    \
    10(B)   30(B)
    /  \    /  \
  5(R)15(R)25(R)35(R)
  
查找键25：
1. 20 < 25 → 右子树
2. 30 > 25 → 左子树
3. 25 == 25 → 找到

查找算法步骤

1. 从根节点开始：

   RBTreeNode<Key, Value>* node = root;
   

2. 循环搜索：

   while (node != nil) {
       // 比较键值
       if (key == node->key)
           return ...; // 找到
       else if (key < node->key)
           node = node->left; // 向左子树搜索
       else
           node = node->right; // 向右子树搜索
   }
   

3. 终止条件：

   • 找到目标键：返回结果
   • 到达哨兵节点 nil：未找到

查找操作特点

特性	说明
时间复杂度	O(log n)
空间复杂度	O(1)
平衡依赖性	依赖红黑树的平衡性
不修改树结构	纯查找不改变树
键值比较次数	等于路径长度

查找操作的时间复杂度分析

红黑树的高度始终保持在 O(log n)，这保证了查找效率：

1. 数学证明：

   • 设黑高为 $h$
   • 最短路径：$h$（全黑节点）
   • 最长路径：$2h$（红黑交替）
   • 节点数 $n\ge 2^h-1\to h\le lo{g}_2(n+1)$
   • 因此高度 $h=O(logn)$

2. 实际性能：

   • 100万个节点：最多比较约 24 次
   • 10亿个节点：最多比较约 32 次

查找操作的最佳实践

1. 只读访问用 find：

   // 安全，不会意外插入
   if (auto ptr = tree.find(key)) {
       // 使用*ptr
   }
   

2. 读写访问用 operator[]：

   // 简洁，但可能意外插入
   tree[key] = value; // 更新或插入
   int val = tree[key]; // 读取或插入默认值
   

3. 避免不必要的默认插入：

   // 错误做法：可能意外插入
   if (tree[key] > 0) { ... }
   
   // 正确做法
   if (auto ptr = tree.find(key)) {
       if (*ptr > 0) { ... }
   }
   

查找与其他操作的关系

1. 插入的基础：

   • 插入前先查找位置
   • 如果键存在则更新值

2. 删除的前提：

   • 删除前先定位节点
   • 查找失败则直接返回

3. 遍历的核心：

   • 中序遍历使用递归查找

   void inorderHelper(RBTreeNode<Key, Value>* node) {
       if (node == nil) return;
       inorderHelper(node->left);    // 查找左子树
       cout << node->key;            // 访问节点
       inorderHelper(node->right);   // 查找右子树
   }
   

性能对比：红黑树 vs 其他数据结构

数据结构	平均查找	最坏查找	是否有序
红黑树	O(log n)	O(log n)	是
哈希表	O(1)	O(n)	否
二叉搜索树	O(log n)	O(n)	是
跳表	O(log n)	O(n)	是

适用场景：

• 需要有序数据：选择红黑树
• 需要最高性能：选择哈希表
• 需要简单实现：选择二叉搜索树

实际应用示例

字典实现

RBTree<string, string> dictionary;

// 添加词条
dictionary.insert("algorithm", "解决特定问题的步骤");
dictionary["data structure"] = "存储和组织数据的方式";

// 查找释义
if (auto def = dictionary.find("algorithm")) {
    cout << "algorithm: " << *def << endl;
}

// 输出所有词条（按字典序）
dictionary.inorder();

缓存系统

RBTree<int, CacheEntry> cache;

// 查找缓存项
CacheEntry* entry = cache.find(request_id);
if (!entry) {
    // 缓存未命中，从数据库加载
    entry = load_from_database(request_id);
    cache.insert(request_id, *entry);
}

红黑树的查找操作结合了二叉搜索树的效率和自平衡树的稳定性，使其成为需要高效查找和有序访问场景的理想选择。理解其实现原理和特性有助于在实际开发中更好地利用这一数据结构。

红黑树删除操作详解

红黑树的删除操作是红黑树实现中最复杂的部分，它需要在删除节点后维护红黑树的平衡和红黑树性质。

删除函数完整实现

void remove(const Key& key) {
    // 1. 查找目标节点
    RBTreeNode<Key, Value>* z = root;
    while (z != nil) {
        if (z->key == key) break;
        z = (key < z->key) ? z->left : z->right;
    }
    if (z == nil) return;  // 未找到

    // 2. 确定实际删除节点
    RBTreeNode<Key, Value>* y = z;
    Color yOriginalColor = y->color;
    RBTreeNode<Key, Value>* x;

    // 3. 处理三种删除情况
    if (z->left == nil) {
        // Case 1: 左子为空
        x = z->right;
        transplant(z, z->right);
    } else if (z->right == nil) {
        // Case 2: 右子为空
        x = z->left;
        transplant(z, z->left);
    } else {
        // Case 3: 有两个子节点
        y = minimum(z->right); // 找到后继节点
        yOriginalColor = y->color;
        x = y->right;

        // 处理后继节点的子树
        if (y->parent == z) {
            x->parent = y;
        } else {
            transplant(y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }

        // 用后继节点替换z
        transplant(z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }

    // 4. 删除节点
    delete z;
    
    // 5. 如果删除的原始颜色是黑色，修复平衡
    if (yOriginalColor == BLACK)
        fixDelete(x);
}

删除操作步骤详解

1. 查找目标节点

RBTreeNode<Key, Value>* z = root;
while (z != nil) {
    if (z->key == key) break;
    z = (key < z->key) ? z->left : z->right;
}
if (z == nil) return;  // 未找到

• 从根节点开始查找目标节点
• 如果未找到，直接返回

2. 确定实际删除节点

RBTreeNode<Key, Value>* y = z;
Color yOriginalColor = y->color;

• y 是实际被删除的节点
• 记录被删除节点的原始颜色（关键）

3. 处理三种删除情况

Case 1: 左子为空

x = z->right;
transplant(z, z->right);

   [z]        删除后
     \    =>     [x]
     [x]

Case 2: 右子为空

x = z->left;
transplant(z, z->left);

   [z]        删除后
  /      =>   [x]
[x]

Case 3: 有两个子节点（最复杂）

y = minimum(z->right); // 找到后继节点
yOriginalColor = y->color;
x = y->right;

// 处理后继节点的子树
if (y->parent == z) {
    x->parent = y;
} else {
    transplant(y, y->right);
    y->right = z->right;
    y->right->parent = y;
}

// 用后继节点替换z
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color; // 保持原节点颜色

处理逻辑：

1. 找到右子树的最小节点（后继节点）
2. 记录后继节点的颜色和右子节点
3. 如果后继节点不是直接右子，移植其右子树
4. 用后继节点替换被删除节点
5. 继承左子树
6. 保持原节点颜色

4. 删除节点

delete z; // 释放内存

5. 修复平衡（关键）

if (yOriginalColor == BLACK)
    fixDelete(x);

• 只有删除黑色节点才需要修复
• 修复从替换节点x开始

修复操作(fixDelete)详解

void fixDelete(RBTreeNode<Key, Value>* x) {
    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            // 处理左子情况
            RBTreeNode<Key, Value>* sibling = x->parent->right;

            // Case 1: 兄弟节点为红色
            if (sibling->color == RED) {
                sibling->color = BLACK;
                x->parent->color = RED;
                leftRotate(x->parent);
                sibling = x->parent->right;
            }

            // Case 2: 兄弟节点的两个子节点均为黑色
            if (sibling->left->color == BLACK && sibling->right->color == BLACK) {
                sibling->color = RED;
                x = x->parent;
            } else {
                // Case 3: 兄弟节点的右子为黑
                if (sibling->right->color == BLACK) {
                    sibling->left->color = BLACK;
                    sibling->color = RED;
                    rightRotate(sibling);
                    sibling = x->parent->right;
                }
                // Case 4: 兄弟节点的右子为红
                sibling->color = x->parent->color;
                x->parent->color = BLACK;
                sibling->right->color = BLACK;
                leftRotate(x->parent);
                x = root;  // 终止循环
            }
        } else { 
            // 对称处理右子情况
            // ...（代码结构对称）
        }
    }
    x->color = BLACK;
}

删除修复的四种情况

情况1：兄弟节点为红色

      P(B)                S(B)
     /   \               /   \
   X(B) S(R)   =>     P(R)   C(B)
         / \          /   \
       A(B) C(B)    X(B) A(B)

处理步骤：

1. 将兄弟节点设为黑色
2. 将父节点设为红色
3. 对父节点左旋
4. 更新兄弟节点指针
5. 转入情况2、3或4

情况2：兄弟节点的两个子节点均为黑色

      P(?)                P(?)
     /   \               /   \
   X(B) S(B)   =>     X(B) S(R)
         / \                 / \
       A(B) B(B)           A(B) B(B)

处理步骤：

1. 将兄弟节点设为红色
2. 将当前节点指向父节点
3. 继续向上修复

情况3：兄弟节点的右子为黑

      P(?)                P(?)
     /   \               /   \
   X(B) S(B)   =>     X(B) A(B)
         / \                   \
       A(R) B(B)               S(R)
                                \
                                B(B)

处理步骤：

1. 将兄弟节点的左子设为黑色
2. 将兄弟节点设为红色
3. 对兄弟节点右旋
4. 更新兄弟节点指针
5. 转入情况4

情况4：兄弟节点的右子为红

      P(?)                S(?)
     /   \               /   \
   X(B) S(B)   =>     P(B)  B(B)
         / \         /   \
        ?  B(R)    X(B)   ?

处理步骤：

1. 将兄弟节点设为父节点的颜色
2. 将父节点设为黑色
3. 将兄弟节点的右子设为黑色
4. 对父节点左旋
5. 设置当前节点为根节点（终止循环）

删除操作流程图

删除操作的时间复杂度

1. BST删除：O(log n)
2. 查找后继节点：O(log n)
3. 修复操作：O(log n)
   • 最多进行3次旋转
   • while循环最多执行O(log n)次
4. 总体复杂度：O(log n)

删除操作的特点

1. 颜色关键：

   • 只有删除黑色节点才需要修复
   • 修复的核心是补偿缺失的黑色节点

2. 替换策略：

   • 对于有两个子节点的节点，实际删除的是后继节点
   • 后继节点最多有一个子节点

3. 修复是局部的：

   • 最多影响三代节点（父、兄弟、侄子）
   • 修复后子树的黑高恢复

4. 修复终止条件：

   • 当前节点变为红色（可染黑补偿）
   • 当前节点变为根节点

5. 最坏情况：

   • 情况2可能导致修复向上传播
   • 最多传播到根节点

实际删除示例

删除节点示例（删除黑色节点）：

        10(B)
       /    \
     5(B)   30(B)
    /  \    /  \
  2(B) 7(R)25(B)40(B)

删除节点5（有两个黑色子节点）：

1. 找到后继节点7（红色）
2. 用7替换5的位置
3. 删除原始节点5（黑色）
4. 调用fixDelete(7的右子-nil)

修复过程：

• 情况1：兄弟节点为黑（不适用）
• 情况2：兄弟的子节点全黑 -> 兄弟变红，向上追溯
• 新当前节点：7的位置（红色）-> 染黑终止

最终结果：

        10(B)
       /    \
     7(B)   30(B)
    /  \    /  \
  2(B) nil 25(B)40(B)

红黑树的删除操作通过节点替换和对四种修复情况的处理，在O(log n)时间内维护了树的平衡性和红黑树性质。

子树移植(transplant)

void transplant(RBTreeNode<Key, Value>* u, RBTreeNode<Key, Value>* v) {
    if (u->parent == nil)
        root = v;
    else if (u == u->parent->left)
        u->parent->left = v;
    else
        u->parent->right = v;
    v->parent = u->parent;
}

功能：

• 用子树v替换子树u
• 维护树结构的完整性

参数：

• u: 被替换的节点
• v: 替换节点

操作过程：

1. 判断u的位置（根节点/左子节点/右子节点）
2. 更新u父节点的对应指针
3. 设置v的父节点指针

使用场景：

• 删除操作中（当节点只有一个子节点时）
• 简化树结构调整

查找最小节点(minimum)

RBTreeNode<Key, Value>* minimum(RBTreeNode<Key, Value>* node) {
    while (node->left != nil)
        node = node->left;
    return node;
}

功能：

• 查找子树中的最小键值节点
• 通过不断向左子树遍历实现

参数：

• node: 子树根节点

返回值：

• 子树中最左侧节点（键值最小的节点）

使用场景：

• 删除操作中（当删除节点有两个子节点时）
• 查找后继节点

树复制(copyTree)

RBTreeNode<Key, Value>* copyTree(RBTreeNode<Key, Value>* src, 
                                 RBTreeNode<Key, Value>* srcNil) {
    if (src == srcNil)
        return nil;
    
    RBTreeNode<Key, Value>* node = new RBTreeNode<Key, Value>(
        src->key, src->value, src->color);
    
    node->left = copyTree(src->left, srcNil);
    if (node->left != nil)
        node->left->parent = node;
    
    node->right = copyTree(src->right, srcNil);
    if (node->right != nil)
        node->right->parent = node;
    
    node->parent = nil; // 将在上层设置
    return node;
}

功能：

• 递归复制整棵红黑树
• 深度复制所有节点
• 维护节点间的父子关系

参数：

• src: 源树当前节点
• srcNil: 源树的哨兵节点

关键点：

• 递归复制左右子树
• 设置复制节点的父指针
• 处理哨兵节点的边界条件
• 新树使用自己的哨兵节点

使用场景：

• 拷贝构造函数
• 赋值运算符

树清理(clearTree)

void clearTree(RBTreeNode<Key, Value>* node) {
    if (node != nil) {
        clearTree(node->left);
        clearTree(node->right);
        delete node;
    }
}

功能：

• 递归释放整棵树的内存
• 深度删除所有节点
• 避免内存泄漏

参数：

• node: 当前子树根节点

操作过程：

1. 递归释放左子树
2. 递归释放右子树
3. 删除当前节点

关键点：

• 跳过哨兵节点（node != nil）
• 后序遍历（先子节点后父节点）
• 安全释放内存

使用场景：

• 析构函数

拷贝构造函数

RBTree(const RBTree& other) {
    nil = new RBTreeNode<Key, Value>(Key(), Value(), BLACK);
    nil->left = nil->right = nil->parent = nil;
    root = nil;

    if (other.root != other.nil) {
        root = copyTree(other.root, other.nil);
        root->parent = nil;
    }
}

功能：

• 创建当前树的深拷贝
• 复制源树的所有节点
• 初始化自己的哨兵节点

关键点：

• 创建新的哨兵节点
• 仅当源树非空时才进行复制
• 设置复制后根节点的父指针为哨兵节点
• 深度复制保证两棵树独立

赋值运算符

RBTree& operator=(const RBTree& other) {
    if (this != &other) {
        // 创建临时副本
        RBTree temp(other);
        // 交换内容
        swap(root, temp.root);
        swap(nil, temp.nil);
    }
    return *this;
}

功能：

• 安全实现赋值操作
• 避免自赋值问题
• 提供强异常安全性保证

关键点：

1. 检查自赋值（this != &other）
2. 创建临时副本（调用拷贝构造函数）
3. 交换当前对象和临时副本的内容
4. 返回当前对象的引用
5. 临时副本在退出作用域时自动析构

优点：

• 异常安全：即使拷贝失败也不会破坏当前对象
• 代码复用：利用拷贝构造函数实现
• 资源管理：自动释放旧树内存

析构函数

~RBTree() {
    clearTree(root);
    delete nil;
}

功能：

• 释放整棵树的内存
• 删除所有节点
• 删除哨兵节点

操作过程：

1. 递归释放所有树节点
2. 删除哨兵节点
3. 防止内存泄漏

关键点：

• 先释放树节点，再释放哨兵节点
• 安全处理空树情况
• 完整的资源清理

遍历函数

层次遍历(levelOrder)

void levelOrder() const {
    if (root == nil) {
        cout << "Empty tree" << endl;
        return;
    }

    queue<RBTreeNode<Key, Value>*> q;
    q.push(root);

    while (!q.empty()) {
        RBTreeNode<Key, Value>* curr = q.front();
        q.pop();

        cout << curr->key << ":" << curr->value
             << "(" << (curr->color == RED ? "R" : "B") << ") ";

        if (curr->left != nil) q.push(curr->left);
        if (curr->right != nil) q.push(curr->right);
    }
    cout << endl;
}

功能：

• 按层次遍历红黑树
• 输出节点键值对和颜色信息
• 用于调试和可视化树结构

实现方式：

• 使用队列辅助遍历
• 从根节点开始，逐层处理节点
• 跳过哨兵节点

输出示例：

Alice:92(B) Bob:90(R) David:88(R) Eva:0(B)

中序遍历(inorder)

void inorder() const {
    inorderHelper(root);
    cout << endl;
}

private:
void inorderHelper(RBTreeNode<Key, Value>* node) const {
    if (node == nil) return;
    inorderHelper(node->left);
    cout << "[" << node->key << ": " << node->value << "] ";
    inorderHelper(node->right);
}

功能：

• 按键值顺序遍历树
• 输出排序后的键值对
• 验证二叉搜索树性质

实现方式：

• 递归实现（左-根-右）
• 深度优先遍历
• 跳过哨兵节点

输出示例：

[Alice: 92] [Bob: 90] [David: 88] [Eva: 0]

函数关系图

关键设计要点

1. 哨兵节点统一处理：

   • 所有叶子节点指向同一个哨兵节点
   • 简化空指针判断
   • 统一处理边界条件

2. 递归算法应用：

   • 树复制（深度优先）
   • 树清理（后序遍历）
   • 中序遍历（左-根-右）

3. 资源管理：

   • RAII原则管理内存
   • 构造函数分配资源
   • 析构函数释放资源

4. 异常安全：

   • 拷贝交换惯用法
   • 保证赋值操作异常安全
   • 避免内存泄漏

5. 调试支持：

   • 层次遍历可视化结构
   • 中序遍历验证排序性质
   • 输出节点颜色信息

完整代码实现

#include <bits/stdc++.h>

/*
如果没有用，改为
#include <iostream>
#include <queue>
#include <stdexcept>
*/
using namespace std;

enum Color { RED, BLACK };

// 红黑树键值对节点
template <typename Key, typename Value>
class RBTreeNode {
	public:
		Key key;
		Value value;
		Color color;
		RBTreeNode *left, *right, *parent;
	
		RBTreeNode(Key k, Value v, Color c = RED)
			: key(k), value(v), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
};

template <typename Key, typename Value>
class RBTree {
	private:
		RBTreeNode<Key, Value>* root;
		RBTreeNode<Key, Value>* nil;  // 哨兵节点
	
		// 左旋操作
		void leftRotate(RBTreeNode<Key, Value>* x) {
			RBTreeNode<Key, Value>* y = x->right;
			x->right = y->left;
	
			if (y->left != nil)
				y->left->parent = x;
	
			y->parent = x->parent;
	
			if (x->parent == nil)
				root = y;
			else if (x == x->parent->left)
				x->parent->left = y;
			else
				x->parent->right = y;
	
			y->left = x;
			x->parent = y;
		}
	
		// 右旋操作
		void rightRotate(RBTreeNode<Key, Value>* y) {
			RBTreeNode<Key, Value>* x = y->left;
			y->left = x->right;
	
			if (x->right != nil)
				x->right->parent = y;
	
			x->parent = y->parent;
	
			if (y->parent == nil)
				root = x;
			else if (y == y->parent->left)
				y->parent->left = x;
			else
				y->parent->right = x;
	
			x->right = y;
			y->parent = x;
		}
	
		// 插入后修复平衡
		void fixInsert(RBTreeNode<Key, Value>* z) {
			while (z->parent->color == RED) {
				if (z->parent == z->parent->parent->left) {
					RBTreeNode<Key, Value>* uncle = z->parent->parent->right;
	
					// Case 1: 叔节点为红色
					if (uncle->color == RED) {
						z->parent->color = BLACK;
						uncle->color = BLACK;
						z->parent->parent->color = RED;
						z = z->parent->parent;
					} else {
						// Case 2: 叔节点为黑且z为右子
						if (z == z->parent->right) {
							z = z->parent;
							leftRotate(z);
						}
						// Case 3: 叔节点为黑且z为左子
						z->parent->color = BLACK;
						z->parent->parent->color = RED;
						rightRotate(z->parent->parent);
					}
				} else {  // 对称情况
					RBTreeNode<Key, Value>* uncle = z->parent->parent->left;
	
					if (uncle->color == RED) {
						z->parent->color = BLACK;
						uncle->color = BLACK;
						z->parent->parent->color = RED;
						z = z->parent->parent;
					} else {
						if (z == z->parent->left) {
							z = z->parent;
							rightRotate(z);
						}
						z->parent->color = BLACK;
						z->parent->parent->color = RED;
						leftRotate(z->parent->parent);
					}
				}
			}
			root->color = BLACK;  // 根节点始终为黑
		}
	
		// 查找最小节点
		RBTreeNode<Key, Value>* minimum(RBTreeNode<Key, Value>* node) {
			while (node->left != nil)
				node = node->left;
			return node;
		}
	
		// 子树移植（用v替换u）
		void transplant(RBTreeNode<Key, Value>* u, RBTreeNode<Key, Value>* v) {
			if (u->parent == nil)
				root = v;
			else if (u == u->parent->left)
				u->parent->left = v;
			else
				u->parent->right = v;
			v->parent = u->parent;
		}
	
		// 删除后修复平衡
		void fixDelete(RBTreeNode<Key, Value>* x) {
			while (x != root && x->color == BLACK) {
				if (x == x->parent->left) {
					RBTreeNode<Key, Value>* sibling = x->parent->right;
	
					// Case 1: 兄弟节点为红色
					if (sibling->color == RED) {
						sibling->color = BLACK;
						x->parent->color = RED;
						leftRotate(x->parent);
						sibling = x->parent->right;
					}
	
					// Case 2: 兄弟节点的两个子节点均为黑色
					if (sibling->left->color == BLACK && sibling->right->color == BLACK) {
						sibling->color = RED;
						x = x->parent;
					} else {
						// Case 3: 兄弟节点的右子为黑
						if (sibling->right->color == BLACK) {
							sibling->left->color = BLACK;
							sibling->color = RED;
							rightRotate(sibling);
							sibling = x->parent->right;
						}
						// Case 4: 兄弟节点的右子为红
						sibling->color = x->parent->color;
						x->parent->color = BLACK;
						sibling->right->color = BLACK;
						leftRotate(x->parent);
						x = root;  // 终止循环
					}
				} else {  // 对称情况
					RBTreeNode<Key, Value>* sibling = x->parent->left;
	
					if (sibling->color == RED) {
						sibling->color = BLACK;
						x->parent->color = RED;
						rightRotate(x->parent);
						sibling = x->parent->left;
					}
	
					if (sibling->right->color == BLACK && sibling->left->color == BLACK) {
						sibling->color = RED;
						x = x->parent;
					} else {
						if (sibling->left->color == BLACK) {
							sibling->right->color = BLACK;
							sibling->color = RED;
							leftRotate(sibling);
							sibling = x->parent->left;
						}
	
						sibling->color = x->parent->color;
						x->parent->color = BLACK;
						sibling->left->color = BLACK;
						rightRotate(x->parent);
						x = root;
					}
				}
			}
			x->color = BLACK;
		}
	
		// 递归复制树
		RBTreeNode<Key, Value>* copyTree(RBTreeNode<Key, Value>* src, RBTreeNode<Key, Value>* srcNil) {
			if (src == srcNil)
				return nil;
			RBTreeNode<Key, Value>* node = new RBTreeNode<Key, Value>(src->key, src->value, src->color);
			node->left = copyTree(src->left, srcNil);
	
			if (node->left != nil)
				node->left->parent = node;
			node->right = copyTree(src->right, srcNil);
			if (node->right != nil)
				node->right->parent = node;
			node->parent = nil; // 将在上层设置
			return node;
		}
	
		// 递归释放树
		void clearTree(RBTreeNode<Key, Value>* node) {
			if (node != nil) {
				clearTree(node->left);
				clearTree(node->right);
				delete node;
			}
		}
	
	public:
		// 构造函数
		RBTree() {
			nil = new RBTreeNode<Key, Value>(Key(), Value(), BLACK);
			nil->left = nil->right = nil->parent = nil;
			root = nil;
		}
	
		// 拷贝构造函数
		RBTree(const RBTree& other) {
			nil = new RBTreeNode<Key, Value>(Key(), Value(), BLACK);
			nil->left = nil->right = nil->parent = nil;
			root = nil;
	
			if (other.root != other.nil) {
				root = copyTree(other.root, other.nil);
				root->parent = nil;
			}
		}
	
		// 赋值运算符
		RBTree& operator=(const RBTree& other) {
			if (this != &other) {
				// 创建临时副本
				RBTree temp(other);
				// 交换内容
				swap(root, temp.root);
				swap(nil, temp.nil);
			}
			return *this;
		}
	
		// 析构函数
		~RBTree() {
			clearTree(root);
			delete nil;
		}
	
		// 插入键值对（若存在则更新）
		void insert(const Key& key, const Value& value) {
			RBTreeNode<Key, Value>* z = root;
			RBTreeNode<Key, Value>* parent = nil;
	
			// 查找插入位置并检查是否已存在
			while (z != nil) {
				parent = z;
				if (key == z->key) {
					// 键已存在，更新值
					z->value = value;
					return;
				}
				else if (key < z->key)
					z = z->left;
				else
					z = z->right;
	
			}
	
			// 创建新节点
			z = new RBTreeNode<Key, Value>(key, value);
			z->parent = parent;
	
			if (parent == nil)
				root = z;
			else if (key < parent->key)
				parent->left = z;
			else
				parent->right = z;
	
	
			z->left = z->right = nil;
			z->color = RED;
			fixInsert(z);
		}
	
		// 查找键对应的值（指针）
		Value* find(const Key& key) {
			RBTreeNode<Key, Value>* node = root;
			while (node != nil){
				if (key == node->key)
					return &node->value;
				else if (key < node->key)
					node = node->left;
				else
					node = node->right;
			}
			return nullptr; // 未找到
		}
	
		// 下标访问运算符（若不存在则插入默认值）
		Value& operator[](const Key& key) {
			RBTreeNode<Key, Value>* node = root;
			RBTreeNode<Key, Value>* parent = nil;
	
			while (node != nil) {
				parent = node;
				if (key == node->key)
					return node->value;
				else if (key < node->key)
					node = node->left;
				else 
					node = node->right;
	
			}
	
			// 键不存在，创建新节点
			node = new RBTreeNode<Key, Value>(key, Value());
			node->parent = parent;
			node->left = node->right = nil;
	
			if (parent == nil)
				root = node;
			else if (key < parent->key)
				parent->left = node;
			else
				parent->right = node;
	
			fixInsert(node);
			return node->value;
		}
	
		// 删除键
		void remove(const Key& key) {
			RBTreeNode<Key, Value>* z = root;
			// 查找目标节点
			while (z != nil) {
				if (z->key == key) break;
				z = (key < z->key) ? z->left : z->right;
			}
			if (z == nil) return;  // 未找到
	
			RBTreeNode<Key, Value>* y = z;
			Color yOriginalColor = y->color;
			RBTreeNode<Key, Value>* x;
	
			if (z->left == nil) {
				x = z->right;
				transplant(z, z->right);
			} else if (z->right == nil) {
				x = z->left;
				transplant(z, z->left);
			} else {
				y = minimum(z->right);
				yOriginalColor = y->color;
				x = y->right;
	
				if (y->parent == z)
					x->parent = y;
				else {
					transplant(y, y->right);
					y->right = z->right;
					y->right->parent = y;
				}
	
				transplant(z, y);
				y->left = z->left;
				y->left->parent = y;
				y->color = z->color;
			}
	
			delete z;
			if (yOriginalColor == BLACK)
				fixDelete(x);
		}
	
		// 层次遍历（用于调试）
		void levelOrder() const {
			if (root == nil) {
				cout << "Empty tree" << endl;
				return;
			}
	
			queue<RBTreeNode<Key, Value>*> q;
			q.push(root);
	
			while (!q.empty()) {
				RBTreeNode<Key, Value>* curr = q.front();
				q.pop();
	
				cout << curr->key << ":" << curr->value
					 << "(" << (curr->color == RED ? "R" : "B") << ") ";
	
				if (curr->left != nil) q.push(curr->left);
				if (curr->right != nil) q.push(curr->right);
			}
			cout << endl;
		}
	
		// 中序遍历（按键排序）
		void inorder() const {
			inorderHelper(root);
			cout << endl;
		}
	
	private:
		void inorderHelper(RBTreeNode<Key, Value>* node) const {
			if (node == nil) return;
			inorderHelper(node->left);
			cout << "[" << node->key << ": " << node->value << "] ";
			inorderHelper(node->right);
		}

};

// 测试用例
int main() {
    // 测试插入和查找功能
    RBTree<string, int> scoreTree;
    scoreTree.insert("Alice", 92);
    scoreTree.insert("Bob", 85);
    scoreTree.insert("Charlie", 95);

    cout << "Bob的分数: " << *scoreTree.find("Bob") << endl;

    // 测试[]运算符
    scoreTree["David"] = 88;             // 插入新键值对
    scoreTree["Bob"] = 90;               // 更新Bob的分数
    cout << "更新后Bob的分数: " << scoreTree["Bob"] << endl;
    cout << "Eva的分数(默认值): " << scoreTree["Eva"] << endl;

    // 测试遍历功能
    cout << "\n层次遍历:" << endl;
    scoreTree.levelOrder();

    cout << "\n中序遍历(按键排序):" << endl;
    scoreTree.inorder();

    // 测试删除功能
    scoreTree.remove("Charlie");
    cout << "\n删除Charlie后:" << endl;
    scoreTree.inorder();  // 显示删除后的树结构

    // 测试赋值运算符
    RBTree<string, int> copyTree = scoreTree;
    cout << "\n复制树的中序遍历:" << endl;
    copyTree.inorder();  // 显示复制树的内容

    // 修改副本不影响原树
    copyTree["Alice"] = 100;
    cout << "\n原树中Alice的分数: " << scoreTree["Alice"] << endl;
    cout << "复制树中Alice的分数: " << copyTree["Alice"] << endl;

    // 测试查找未存在键的情况
    int* unknown = scoreTree.find("Unknown");
    if (unknown) {
        cout << "找到Unknown的分数: " << *unknown << endl;
    } else {
        cout << "未找到Unknown" << endl;
    }

    return 0;
}

测试结果

Bob的分数: 85
更新后Bob的分数: 90
Eva的分数(默认值): 0

层次遍历:
Bob:90(B) Alice:92(B) David:88(R) Eva:0(R) 

中序遍历(按键排序):
[Alice: 92] [Bob: 90] [David: 88] [Eva: 0]

删除Charlie后:
[Alice: 92] [Bob: 90] [David: 88] [Eva: 0]

复制树的中序遍历:
[Alice: 92] [Bob: 90] [David: 88] [Eva: 0]

原树中Alice的分数: 92
复制树中Alice的分数: 100
未找到Unknown

总结

本文展示了红黑树的核心操作：

1. 使用哨兵节点（nil）简化边界处理
2. 通过旋转和重新着色维护平衡
3. 支持高效的插入、删除和查找操作
4. 实现深拷贝和内存安全管理
5. 提供类似map的下标访问接口