2024年11月18日：正在更新中；目前更新到前3章。

Written by f(x)=Asin(ωx+φ)，Reprint must be indicated.

众所周知，二叉搜索树具有良好的性能，其增加，查询或删除等操作都仅需$O(logn)$时间。但倘若我们在构建二叉树时插入的数据足够有序，则二叉树会变得极不平衡，甚至退化成一个链表。对于这个问题，人们先后提出了很多方法，例如平衡二叉树（AVL树）。AVL树在每次增加数据后都会检查二叉树是否严格平衡，并且通过旋转来调整不平衡的树。然而，无尽的旋转对时间亦是一笔极大的开销，因此，红黑树便应运而生。

红黑树是二叉搜索树的一种。其保证从根节点到最远的叶子节点的距离不会超过到最近的叶子节点的两倍，维持了其平衡性；又通过节点颜色规则来规范旋转，使其插入仅需最多两次旋转，删除仅需最多三次旋转。由于其性能的高效性，红黑树成为当下最风靡的数据结构之一，STL中的set便是用红黑树实现的。今笔者将尝试撰文讲述之。

一、性质

红黑树是一种自平衡的二叉搜索树。相对于普通的二叉树，红黑树的每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡。同时，每个叶子节点不储存数据，被称为空叶子节点(NIL节点)。

一棵合法的红黑树必须遵循以下五条性质：

• 1.节点为红色或黑色。
• 2.根节点为黑色。
• 3.NIL节点为黑色。
• 4.红色节点的子节点为黑色。
• 5.从根节点到 NIL 节点的每条路径上的黑色节点数量相同。

以下是一棵合法的红黑树：

（图片来自OI Wiki）

每个节点都具有以下信息：

• 节点颜色color，红色或黑色。
• 键值key。
• 父节点parent。
• 左子节点left。
• 右子节点right。
• 卫星数据value（可选）。

据此，便可写出节点类的代码：

enum Color { RED, BLACK };              //定义一个枚举，用于储存节点的颜色
template<typename T>
class Node {
public:
    T key;                              //节点的键值
    Color color;                        //节点的颜色
    Node<T>* left, * right, * parent;   //指向左右子节点和父节点的指针

    Node(T key)                         //构造函数，默认颜色是红色（原因会在之后讲解插入时提及）
        : key(key), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

二、查询

首先，我们来温习一下二叉搜索树的性质：一个节点的左子树的键值一定小于该节点，右子树一定大于该节点。所以，如果我们要查询一个节点是否存在，只需要从根开始，层层二分查找即可。

由于红黑树亦是二叉搜索树的一种，所以其查询和普通二叉搜索树的查询别无二致。先从根开始，将待查数据与节点的键值比较，共有三种情况：

• 待查数据等于节点的键值：查询成功，返回该节点。
• 待查数据小于节点的键值：在这个节点的左子树继续搜索。
• 待查数据大于节点的键值：在这个节点的右子树继续搜索。

直到遇见一个没有左右子树的叶子节点。此时说明待查数据不存在于树中，查询失败。

以下是查询的函数。

    Node<T>* search(T key) {
        Node<T>* x = root;              //从根开始查找
        while (x != NIL && key != x->key) {
            if (key = x->key) {
                return x;
            }                           //如果相等，则返回该节点
            if (key < x->key) {
                x = x->left;
            }                           //如果小于该节点，则前往该节点的左子节点继续搜索
            else {
                x = x->right;
            }                           //如果大于该节点，则前往该节点的右子节点继续搜索
        }
        return NIL;                     //如果没有找到，则返回一个空节点
    }

三、旋转

红黑树靠旋转节点来调整自己的结构，保证树的平衡。旋转分为左旋和右旋。

    //左旋
    void leftRotate(Node<T>* x) {
        Node<T>* 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(Node<T>* y) {
        Node<T>* 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->right) {
            y->parent->right = x;
        }
        else {
            y->parent->left = x;
        }
        x->right = y;
        y->parent = x;
    }

四、插入

五、删除

六、完整的红黑树模板

包括结点模板类和红黑树模板类；各种函数已封装好，可直接使用。

enum Color { RED, BLACK };              //定义一个枚举，用于储存节点的颜色
template<typename T>
class Node {
public:
    T key;                              //节点的键值
    Color color;                        //节点的颜色
    Node<T>* left, * right, * parent;   //指向左右子节点和父节点的指针

    Node(T key)                         //构造函数，默认颜色是红色（原因会在之后讲解插入时提及）
        : key(key), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

template<typename T>
class RedBlackTree {
public:
    Node<T>* root;                      //根节点
    Node<T>* NIL;                       //空叶子节点，无论是根的父节点还是最底下的叶子节点都由这一个节点代表
private:
    //左旋
    void leftRotate(Node<T>* x) {
        Node<T>* 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(Node<T>* y) {
        Node<T>* 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->right) {
            y->parent->right = x;
        }
        else {
            y->parent->left = x;
        }
        x->right = y;
        y->parent = x;
    }

    //插入纠错
    void insertFixup(Node<T>* z) {
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                Node<T>* y = z->parent->parent->right;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                }
                else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        leftRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    rightRotate(z->parent->parent);
                }
            }
            else {
                Node<T>* y = z->parent->parent->left;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->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;
    }

    //交换
    void transplant(Node<T>* u, Node<T>* 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 deleteFixup(Node<T>* x) {
        while (x != root && x->color == BLACK) {
            if (x == x->parent->left) {
                Node<T>* w = x->parent->right;
                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    leftRotate(x->parent);
                    w = x->parent->right;
                }
                if (w->left->color == BLACK && w->right->color == BLACK) {
                    w->color = RED;
                    x = x->parent;
                }
                else {
                    if (w->right->color == BLACK) {
                        w->left->color = BLACK;
                        w->color = RED;
                        rightRotate(w);
                        w = x->parent->right;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->right->color = BLACK;
                    leftRotate(x->parent);
                    x = root;
                }
            }
            else {
                Node<T>* w = x->parent->left;
                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    rightRotate(x->parent);
                    w = x->parent->left;
                }
                if (w->right->color == BLACK && w->left->color == BLACK) {
                    w->color = RED;
                    x = x->parent;
                }
                else {
                    if (w->left->color == BLACK) {
                        w->right->color = BLACK;
                        w->color = RED;
                        leftRotate(w);
                        w = x->parent->left;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->left->color = BLACK;
                    rightRotate(x->parent);
                    x = root;
                }
            }
        }
        x->color = BLACK;
    }

    //最小值
    Node<T>* minimum(Node<T>* x) {
        while (x->left != NIL) {
            x = x->left;
        }
        return x;
    }

public:
    //构造函数，声明了红黑树的共用NIL节点
    RedBlackTree() {
        NIL = new Node<T>(0);
        NIL->color = BLACK;
        root = NIL;
    }

    //增加
    void insert(T key) {
        Node<T>* z = new Node<T>(key);
        Node<T>* y = NIL;
        Node<T>* x = root;

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

        z->parent = y;
        if (y == NIL) {
            root = z;
        }
        else if (z->key < y->key) {
            y->left = z;
        }
        else {
            y->right = z;
        }

        z->left = NIL;
        z->right = NIL;
        z->color = RED;

        insertFixup(z);
    }

    //查询
    Node<T>* search(T key) {
        Node<T>* x = root;              //从根开始查找
        while (x != NIL && key != x->key) {
            if (key = x->key) {
                return x;
            }                           //如果相等，则返回该节点
            if (key < x->key) {
                x = x->left;
            }                           //如果小于该节点，则前往该节点的左子节点继续搜索
            else {
                x = x->right;
            }                           //如果大于该节点，则前往该节点的右子节点继续搜索
        }
        return NIL;                     //如果没有找到，则返回一个空节点
    }

    //删除
    void remove(int key) {
        Node<T>* z = search(key);
        if (z == NIL) {
            return;
        }

        Node<T>* y = z;
        Node<T>* x;
        Color yOriginalColor = y->color;

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

        if (yOriginalColor == BLACK) {
            deleteFixup(x);
        }

        delete z;
    }

    //前序遍历
    void inorderTraversal(Node<T>* x) {
        if (x != NIL) {
            inorderTraversal(x->left);
            cout << x->key << " ";
            inorderTraversal(x->right);
        }
    }

    //打印
    void printTree() {
        inorderTraversal(root);
        cout << endl;
    }
};