红黑树

算法概述

【红黑树】是一种自平衡的二叉搜索树，在ACM竞赛和实际应用中广泛使用，尤其是STL中的map和set容器就是基于红黑树实现的。红黑树通过对节点染色并维护特定的平衡性质，确保树的高度始终保持在O(log n)级别，从而保证查找、插入和删除操作的高效性。

红黑树的性质

红黑树有以下五个关键性质：

1. 节点颜色：每个节点要么是红色，要么是黑色
2. 根节点：根节点必须是黑色
3. 叶节点：所有叶节点（NIL或空节点）都是黑色
4. 红色节点的子节点：如果一个节点是红色，则其两个子节点都必须是黑色（即不能有两个连续的红色节点）
5. 黑色平衡：从任一节点到其每个叶节点的路径上，黑色节点数量相同（即黑色高度平衡）

这些性质共同确保了红黑树的平衡性，特别是性质5保证了从根到最远叶节点的路径长度不会超过最短路径的两倍，这是红黑树性能保证的关键。

红黑树的基本操作

节点结构

enum Color { RED, BLACK };

struct RBNode {
    int key;           // 键值
    Color color;       // 节点颜色
    RBNode* left;      // 左子节点
    RBNode* right;     // 右子节点
    RBNode* parent;    // 父节点

    // 其他可能的附加信息
    int size;          // 子树大小（用于排名查询）
    int count;         // 当前值出现次数（处理重复值）

    RBNode(int k, Color c = RED)
        : key(k), color(c), left(nullptr), right(nullptr), 
          parent(nullptr), size(1), count(1) {}
};

旋转操作

平衡调整的基础操作是旋转，包括左旋和右旋：

// 左旋操作：将x的右子节点升为x的位置，x成为其左子节点
void leftRotate(RBNode*& root, RBNode* x) {
    RBNode* y = x->right;  // y是x的右子节点

    // 将y的左子树变为x的右子树
    x->right = y->left;
    if (y->left != nullptr)
        y->left->parent = x;

    // 设置y的父节点
    y->parent = x->parent;

    // 将y放到原来x的位置
    if (x->parent == nullptr)
        root = y;  // x是根节点
    else if (x == x->parent->left)
        x->parent->left = y;  // x是左子节点
    else
        x->parent->right = y;  // x是右子节点

    // 将x设为y的左子节点
    y->left = x;
    x->parent = y;

    // 更新子树大小（如果需要）
    y->size = x->size;
    x->size = (x->left ? x->left->size : 0) + 
              (x->right ? x->right->size : 0) + 
              x->count;
}

// 右旋操作：将y的左子节点升为y的位置，y成为其右子节点
void rightRotate(RBNode*& root, RBNode* y) {
    RBNode* x = y->left;  // x是y的左子节点

    // 将x的右子树变为y的左子树
    y->left = x->right;
    if (x->right != nullptr)
        x->right->parent = y;

    // 设置x的父节点
    x->parent = y->parent;

    // 将x放到原来y的位置
    if (y->parent == nullptr)
        root = x;  // y是根节点
    else if (y == y->parent->left)
        y->parent->left = x;  // y是左子节点
    else
        y->parent->right = x;  // y是右子节点

    // 将y设为x的右子节点
    x->right = y;
    y->parent = x;

    // 更新子树大小（如果需要）
    x->size = y->size;
    y->size = (y->left ? y->left->size : 0) + 
              (y->right ? y->right->size : 0) + 
              y->count;
}

插入操作

红黑树的插入操作基本流程：

1. 以普通BST方式插入节点，初始颜色设为红色
2. 修复可能破坏的红黑树性质

void insert(RBNode*& root, int key) {
    // 1. 标准BST插入
    RBNode* z = new RBNode(key);
    RBNode* y = nullptr;
    RBNode* x = root;

    // 寻找插入位置
    while (x != nullptr) {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else if (z->key > x->key)
            x = x->right;
        else {
            // 键已存在，增加计数
            x->count++;
            x->size++;

            // 更新祖先节点的size
            RBNode* parent = x->parent;
            while (parent) {
                parent->size++;
                parent = parent->parent;
            }

            delete z;  // 释放新创建的节点
            return;
        }
    }

    // 设置z的父节点
    z->parent = y;

    if (y == nullptr)
        root = z;  // 树为空
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    // 更新祖先节点的size
    RBNode* parent = z->parent;
    while (parent) {
        parent->size++;
        parent = parent->parent;
    }

    // 2. 修复红黑树性质
    insertFixup(root, z);
}

void insertFixup(RBNode*& root, RBNode* z) {
    // 父节点存在且为红色时需要修复
    while (z->parent && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            // 父节点是祖父节点的左子节点
            RBNode* y = z->parent->parent->right;  // 叔叔节点

            if (y && y->color == RED) {
                // 情况1：叔叔节点是红色
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    // 情况2：叔叔节点是黑色，当前节点是右子节点
                    z = z->parent;
                    leftRotate(root, z);
                }
                // 情况3：叔叔节点是黑色，当前节点是左子节点
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else {
            // 父节点是祖父节点的右子节点（对称情况）
            RBNode* y = z->parent->parent->left;  // 叔叔节点

            if (y && y->color == RED) {
                // 情况1：叔叔节点是红色
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    // 情况2：叔叔节点是黑色，当前节点是左子节点
                    z = z->parent;
                    rightRotate(root, z);
                }
                // 情况3：叔叔节点是黑色，当前节点是右子节点
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    // 确保根节点是黑色
    root->color = BLACK;
}

删除操作

删除操作比插入操作更复杂，基本流程：

1. 标准BST删除操作找到要删除的节点
2. 如果被删除的节点或其替代节点是黑色，需要修复红黑树性质

void remove(RBNode*& root, int key) {
    RBNode* z = search(root, key);
    if (!z) return;  // 键不存在

    // 如果键有多个实例，仅减少计数
    if (z->count > 1) {
        z->count--;
        z->size--;

        // 更新祖先节点的size
        RBNode* parent = z->parent;
        while (parent) {
            parent->size--;
            parent = parent->parent;
        }
        return;
    }

    RBNode* y = z;  // y是将被删除或移动的节点
    RBNode* x = nullptr;  // x是y的替代节点
    Color y_original_color = y->color;

    // 更新祖先节点的size
    RBNode* parent = z->parent;
    while (parent) {
        parent->size--;
        parent = parent->parent;
    }

    if (z->left == nullptr) {
        // z没有左子节点
        x = z->right;
        transplant(root, z, z->right);
    } else if (z->right == nullptr) {
        // z没有右子节点
        x = z->left;
        transplant(root, z, z->left);
    } else {
        // z有两个子节点
        // 找到z的后继（右子树中的最小节点）
        y = minimum(z->right);
        y_original_color = y->color;
        x = y->right;

        if (y->parent == z) {
            if (x) x->parent = y;
        } else {
            transplant(root, y, y->right);
            y->right = z->right;
            if (y->right) y->right->parent = y;
        }

        transplant(root, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;

        // 更新y的size
        y->size = (y->left ? y->left->size : 0) + 
                  (y->right ? y->right->size : 0) + 
                  y->count;
    }

    if (y_original_color == BLACK) {
        // 如果删除的是黑色节点，需要修复红黑树性质
        removeFixup(root, x);
    }

    delete z;
}

void transplant(RBNode*& root, RBNode* u, RBNode* v) {
    if (u->parent == nullptr)
        root = v;
    else if (u == u->parent->left)
        u->parent->left = v;
    else
        u->parent->right = v;

    if (v) v->parent = u->parent;
}

void removeFixup(RBNode*& root, RBNode* x) {
    // 调整红黑树平衡的复杂逻辑，处理各种情况
    // 完整代码较长，这里略去，详见参考资料
}

查找操作

查找操作与标准BST相同：

RBNode* search(RBNode* root, int key) {
    while (root != nullptr && key != root->key) {
        if (key < root->key)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

查找第k小元素

通过维护子树大小，红黑树可以高效地查找第k小元素：

RBNode* findKth(RBNode* root, int k) {
    if (!root) return nullptr;

    int leftSize = root->left ? root->left->size : 0;

    if (k <= leftSize) {
        // 第k小在左子树中
        return findKth(root->left, k);
    } else if (k <= leftSize + root->count) {
        // 当前节点就是第k小
        return root;
    } else {
        // 第k小在右子树中
        return findKth(root->right, k - leftSize - root->count);
    }
}

红黑树的复杂度分析

• 空间复杂度：O(n)，每个元素需要一个节点
• 时间复杂度：
  • 查找：O(log n)
  • 插入：O(log n)
  • 删除：O(log n)
  • 查找第k小：O(log n)（需要额外维护子树大小）

红黑树保证了上述操作在最坏情况下的性能，这是它在实际应用中广泛使用的主要原因。

红黑树的优缺点

优点

1. 保证最坏情况下O(log n)的操作时间复杂度
2. 插入和删除操作的平均旋转次数少于AVL树，调整成本更低
3. 内存占用相对适中
4. 可以方便地扩展实现排序和统计功能

缺点

1. 实现复杂，特别是删除操作和修复过程
2. 相比一些特殊用途的数据结构（如跳表），常数因子较大
3. 不直接支持区间操作，需要额外设计

红黑树在ACM竞赛中的应用

在ACM竞赛中，红黑树主要用于以下场景：

1. 动态集合维护：需要频繁插入、删除和查找元素时
2. 多重集合：处理重复元素的有序集合
3. 排名统计：查找第k小/大元素，或确定元素排名
4. 前驱/后继查询：查找比某值小的最大元素或比某值大的最小元素
5. 区间统计：维护区间内的元素信息，如范围计数或求和

红黑树与STL

在C++标准库中，set、map、multiset和multimap通常基于红黑树实现，提供了高效的有序集合和映射功能。在大多数ACM题目中，可以直接使用这些容器而不必手动实现红黑树。

#include <set>
#include <map>
#include <iostream>
using namespace std;

int main() {
    // 使用set维护有序集合
    set<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(30);

    auto it = s.lower_bound(15);  // 返回>=15的第一个元素(20)
    cout << *it << endl;

    // 使用map维护键值映射
    map<string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 89;

    // 使用multiset允许重复元素
    multiset<int> ms;
    ms.insert(10);
    ms.insert(10);  // 允许重复
    cout << ms.count(10) << endl;  // 输出2

    return 0;
}

红黑树实现注意事项

1. 哨兵节点（Sentinel）技巧

在红黑树实现中，使用哨兵节点（通常是一个空的黑色节点）代替nullptr可以简化边界处理：

// 全局哨兵节点，表示NIL
RBNode* NIL = new RBNode(0, BLACK);

// 初始化红黑树时
void initTree(RBNode*& root) {
    root = NIL;
}

// 判断节点是否为NIL
bool isNil(RBNode* node) {
    return node == NIL;
}

2. 维护附加信息

根据题目需要，可以在节点中维护额外信息：

struct RBNode {
    // 基本属性
    int key;
    Color color;
    RBNode *left, *right, *parent;

    // 附加信息
    int size;    // 子树大小，用于排名查询
    int sum;     // 子树所有节点值的和
    int max;     // 子树中的最大值

    // 在旋转和插入/删除操作中需要相应更新这些信息
};

3. 内存管理

在竞赛环境中，可以使用静态数组和节点池来避免动态内存分配的开销：

const int MAXN = 100005;
RBNode nodes[MAXN];
int nodeCount = 0;

RBNode* createNode(int key, Color color = RED) {
    nodes[nodeCount].key = key;
    nodes[nodeCount].color = color;
    nodes[nodeCount].left = nodes[nodeCount].right = nodes[nodeCount].parent = nullptr;
    nodes[nodeCount].size = 1;
    nodes[nodeCount].count = 1;
    return &nodes[nodeCount++];
}

典型例题分析

例题：查询排名

问题：维护一个数据集合，支持以下操作：

1. 插入一个数
2. 删除一个数
3. 查询一个数的排名（集合中比它小的数的个数+1）
4. 查询排名为k的数
5. 查询一个数的前驱（小于该数的最大值）
6. 查询一个数的后继（大于该数的最小值）

思路：

• 使用红黑树并在每个节点中维护子树大小
• 对于排名查询，通过累加左子树大小来计算
• 对于前驱和后继，可以通过中序遍历找到

// 查询x的排名（比x小的数的个数+1）
int getRank(RBNode* root, int x) {
    if (root == NIL) return 1;

    if (x <= root->key) {
        return getRank(root->left, x);
    } else {
        int leftSize = root->left->size;
        return leftSize + root->count + getRank(root->right, x);
    }
}

// 查询排名为k的数
RBNode* getKthElement(RBNode* root, int k) {
    if (root == NIL) return NIL;

    int leftSize = root->left->size;

    if (k <= leftSize) {
        return getKthElement(root->left, k);
    } else if (k <= leftSize + root->count) {
        return root;
    } else {
        return getKthElement(root->right, k - leftSize - root->count);
    }
}

// 查询x的前驱（小于x的最大数）
RBNode* getPredecessor(RBNode* root, int x) {
    RBNode* result = NIL;
    RBNode* current = root;

    while (current != NIL) {
        if (current->key < x) {
            result = current;
            current = current->right;
        } else {
            current = current->left;
        }
    }

    return result;
}

// 查询x的后继（大于x的最小数）
RBNode* getSuccessor(RBNode* root, int x) {
    RBNode* result = NIL;
    RBNode* current = root;

    while (current != NIL) {
        if (current->key > x) {
            result = current;
            current = current->left;
        } else {
            current = current->right;
        }
    }

    return result;
}

总结

红黑树是一种应用广泛的自平衡二叉搜索树，其特点是在保证最坏情况下操作时间复杂度为O(log n)的同时，实现相对简单且内存使用高效。在ACM竞赛中，虽然大多数时候可以直接使用C++ STL中的set和map，但了解红黑树的原理有助于解决更复杂的问题。

红黑树的核心思想是通过颜色标记和一系列平衡规则，确保树的黑色高度平衡，从而保证树的最大高度不会超过平衡高度的两倍，这就保证了各种操作的对数时间复杂度。

当处理涉及有序集合的动态维护、排名统计等问题时，红黑树是一个强大而可靠的数据结构选择。