红黑树

红黑树（Red-Black Tree）介绍

红黑树（Red-Black Tree）是一种 自平衡二叉搜索树（BST），用于 高效的插入、删除和查找操作，广泛应用于 STL的map/set、数据库索引、文件系统等。

---

红黑树的性质

红黑树是一棵满足以下 五条性质 的二叉搜索树：

1. 每个节点要么是红色，要么是黑色。
2. 根节点必须是黑色。
3. 红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。
4. 每个叶子节点（NIL，即空节点）都是黑色。
5. 从任意节点到其所有叶子节点的路径上，经过的黑色节点数必须相同。

这些性质保证了红黑树的平衡性，使得树的最长路径不超过最短路径的两倍，从而保证了 O(log n) 的操作时间复杂度。

---

红黑树的基本操作

1. 旋转操作

红黑树的调整主要依赖 左旋（Left Rotation） 和 右旋（Right Rotation）：

• 左旋（Left Rotate）：将某个节点旋转到其右子树的位置。
• 右旋（Right Rotate）：将某个节点旋转到其左子树的位置。

旋转的作用：用于调整红黑树的结构，维持平衡性，通常配合插入和删除操作进行。

2. 插入操作

插入一个新节点可能会破坏红黑树的平衡性，因此需要调整：

• 新节点默认标记为 红色。

• 如果新节点的 父节点是黑色，则无需调整，红黑树性质不变。

• 如果新节点的

  父节点是红色

  ，则需要调整：

  1. 叔叔节点（父亲的兄弟）也是红色：

     • 变色操作：父节点和叔叔节点变黑，祖父节点变红。
     • 继续检查祖父节点，可能需要递归调整。

  2. 叔叔节点是黑色：

     • 可能需要 旋转 和 变色 操作来恢复平衡。

3. 删除操作

删除一个节点可能会影响红黑树的平衡，调整步骤较复杂：

• 若删除的节点是红色，不影响红黑树性质，直接删除即可。
• 若删除的节点是黑色，则可能破坏性质 （路径上的黑色节点数量减少），需要进行 变色和旋转 来恢复平衡。

---

红黑树的 C++ 实现

#include <iostream>

enum Color { RED, BLACK };

struct Node {
    int data;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int val) : data(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

class RedBlackTree {
private:
    Node* root;

    // 左旋
    void leftRotate(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        if (y->left) y->left->parent = x;
        y->parent = x->parent;

        if (!x->parent)
            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(Node* x) {
        Node* y = x->left;
        x->left = y->right;
        if (y->right) y->right->parent = x;
        y->parent = x->parent;

        if (!x->parent)
            root = y;
        else if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;

        y->right = x;
        x->parent = y;
    }

    // 插入修复
    void fixInsert(Node* z) {
        while (z->parent && z->parent->color == RED) {
            Node* grandparent = z->parent->parent;

            if (z->parent == grandparent->left) {
                Node* uncle = grandparent->right;
                if (uncle && uncle->color == RED) {
                    // 情况1：叔叔是红色，变色处理
                    z->parent->color = BLACK;
                    uncle->color = BLACK;
                    grandparent->color = RED;
                    z = grandparent; // 继续向上修复
                } else {
                    if (z == z->parent->right) {
                        // 情况2：叔叔是黑色，且z是右子节点，先左旋
                        z = z->parent;
                        leftRotate(z);
                    }
                    // 情况3：叔叔是黑色，且z是左子节点，右旋+变色
                    z->parent->color = BLACK;
                    grandparent->color = RED;
                    rightRotate(grandparent);
                }
            } else {
                Node* uncle = grandparent->left;
                if (uncle && uncle->color == RED) {
                    z->parent->color = BLACK;
                    uncle->color = BLACK;
                    grandparent->color = RED;
                    z = grandparent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        rightRotate(z);
                    }
                    z->parent->color = BLACK;
                    grandparent->color = RED;
                    leftRotate(grandparent);
                }
            }
        }
        root->color = BLACK; // 确保根节点是黑色
    }

public:
    RedBlackTree() : root(nullptr) {}

    // 插入新节点
    void insert(int val) {
        Node* newNode = new Node(val);
        if (!root) {
            root = newNode;
            root->color = BLACK;
            return;
        }

        Node* parent = nullptr;
        Node* curr = root;

        while (curr) {
            parent = curr;
            if (val < curr->data)
                curr = curr->left;
            else
                curr = curr->right;
        }

        newNode->parent = parent;
        if (val < parent->data)
            parent->left = newNode;
        else
            parent->right = newNode;

        fixInsert(newNode); // 调整红黑树
    }

    // 中序遍历
    void inorder(Node* node) {
        if (!node) return;
        inorder(node->left);
        std::cout << node->data << (node->color == RED ? " (R) " : " (B) ") << " ";
        inorder(node->right);
    }

    void display() {
        inorder(root);
        std::cout << std::endl;
    }
};

// 测试
int main() {
    RedBlackTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(15);
    tree.insert(25);
    tree.insert(5);
    tree.insert(1);
    tree.insert(12);
    
    tree.display();
    return 0;
}

---

总结

1. 红黑树的核心机制：
   • 通过 变色 和 旋转 来保持平衡。
   • 红色节点不能连续，以保证树的高度不会增长过快。
2. 插入操作：
   • 可能涉及 变色、旋转或递归修复，确保红黑树的五大性质不被破坏。
3. 删除操作（未实现）：
   • 需要考虑 替换节点的颜色变化，通常比插入更复杂。

红黑树广泛应用于数据库索引、操作系统调度、STL的map/set等数据结构中！