洛谷 P3369：【模板】普通平衡树 ← “红黑树”实现

【题目来源】
https://www.luogu.com.cn/problem/P3369

【题目描述】
您需要动态地维护一个可重集合 M，并且提供以下操作：
（1）向 M 中插入一个数 x。
（2）从 M 中删除一个数 x（若有多个相同的数，应只删除一个）。
（3）查询 M 中有多少个数比 x 小，并且将得到的答案加一。
（4）查询如果将 M 从小到大排列后，排名位于第 x 位的数。
（5）查询 M 中 x 的前驱（前驱定义为小于 x，且最大的数）。
（6）查询 M 中 x 的后继（后继定义为大于 x，且最小的数）。
对于操作 3，5，6，不保证当前可重集中存在数 x。

【输入格式】
第一行为 n，表示操作的个数。
下面 n 行，每行有两个数 opt 和 x，opt 表示操作的序号（1≤opt≤6）。

【输出格式】
对于操作 3，4，5，6，每行输出一个数，表示对应答案。

【输入样例】
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

【输出样例】
106465
84185
492737

【数据范围】
对于 100% 的数据，1≤n≤10^5，∣x∣≤10^7。

【算法分析】
红黑树（Red Black Tree）简称 RB 树，是一种自平衡的二叉排序树。红黑树在平衡二叉树的基础上牺牲严格的平衡，降低对旋转的要求，通过少量的旋转操作达到平衡，从而提高性能。
红黑树于 1972 年由鲁道夫 • 拜耳（Rudolf Bayer）发明。当时被称为平衡二叉 B 树（红黑树本质上是一种 B 树）。B 树（又称 B- 树）中的 B 表示 Balanced，即平衡的意思。
红黑树自提出以来，经历了多次改进和优化，应用非常广泛。

下面关于红黑树的描述，来源于李冬梅、严蔚敏、吴伟民等编著的《数据结构（C语言版第3版）》。其 ISBN 为 9787115651259。

● 红黑树的性质
（1）每个结点的颜色不是黑色就是红色。
（2）根结点一定是黑色。
（3）每个叶子结点都是黑色的空结点，即虚构的外部结点、NULL结点。
（4）两个红色结点不能相邻，即红色结点的孩子结点一定是黑色。但是，两个黑色结点可以相邻。
（5）对任一结点，从该结点出发到叶子结点的任一路径所包含的黑色结点数目相同，即黑平衡。

● 红黑树的插入
在对红黑树进行插入操作时，首先需要考虑的一个问题是新插入红黑树的结点颜色是红色还是黑色？一般情况下，设置新插入结点的颜色为红色。主要原因是当新插入结点的颜色为黑色时，该结点所在的路径比其他路径多出一个黑色结点，破坏上文所述的性质 5，使得红黑树的调整变得比较麻烦；当新插入结点的颜色为红色时，所有路径上的黑色结点数目不会发生改变。只有出现连续两个红色结点时会破坏上文所述的性质 4，需要通过变色或者旋转进行调整，操作相对简单。
设结点 x 为新插入结点，插入过程描述如下：
（一）如果红黑树初始为空树，那么新结点 x 插入后是树的根结点，将结点 x 着色为黑色即可；
（二）新结点 x 的父结点为黑色，则不需要进行任何调整；
（三）新结点 x 的父结点为红色，叔结点也为红色，那么将其祖父结点，父结点，叔结点的颜色翻转，并检查其祖父结点是否为根结点；
（四）新结点 x 的父结点为红色，叔结点为黑色，该种情况较为复杂。
1. LL型（父结点为祖父结点的左孩子，新结点 x 为父结点的左孩子）：右旋祖父节点，之后将父结点与祖父结点的颜色翻转；
2. RR型（父结点为祖父结点的右孩子，新结点 x 为父结点的右孩子）：左旋祖父节点，之后将父结点与祖父结点的颜色翻转；
3. LR型（父结点为祖父结点的左孩子，新结点 x 为父结点的右孩子）：左旋新结点，右旋祖父节点，之后将新结点与祖父结点的颜色翻转；
4. RL型（父结点为祖父结点的右孩子，新结点 x 为父结点的左孩子）：右旋新结点，左旋祖父节点，之后将新结点与祖父结点的颜色翻转。

● 红黑树的删除
红黑树的删除操作比较复杂。下面关于删除操作的描述忽略外部结点 NULL。删除过程描述如下：
（一）待删结点有两个孩子结点。首先找到待删结点的中序后继结点，然后与待删结点进行交换，此时待删结点就变成了叶子结点或只有一个右孩子结点。即问题就转换为了删除叶子结点或待删结点只有一个孩子结点的情况；
（二）待删结点只有一个孩子结点。那么待删结点必为黑色，子结点必为红色，此时只需将子结点顶上去，再着成黑色即可；
（三）待删结点没有子结点，即删除叶子结点。
1.待删叶子结点为红色：直接删除，不需要进行任何调整。
2.待删叶子结点为黑色，且其兄弟结点有红色孩子结点。
（1）LL型（待删叶子结点的兄弟是其父结点的左孩子，兄弟结点的左孩子为红色）：交换兄弟结点及父结点的颜色，且将兄弟结点的左孩子着为黑色后，右旋父结点，删除叶子结点。
（2）RR型（待删叶子结点的兄弟是其父结点的右孩子，兄弟结点的右孩子为红色）：交换兄弟结点及父结点的颜色，且将兄弟结点的右孩子着为黑色后，左旋父结点，删除叶子结点。
（3）LR型（待删叶子结点的兄弟是其父结点的左孩子，兄弟结点的右孩子为红色）：首先将兄弟结点变成红色，兄弟结点的右孩子变成黑色，然后左旋兄弟结点的右孩子。。
（4）RL型（待删叶子结点的兄弟是其父结点的右孩子，兄弟结点的左孩子为红色）：首先将兄弟结点变成红色，兄弟结点的左孩子变成黑色，然后右旋兄弟结点的左孩子。
3.待删叶子结点为黑色，且其兄弟结点没有红色孩子结点。
（1）待删叶子结点的父结点为红色：将父结点变为黑色，将兄弟结点变为红色，删除叶子结点。
（2）待删叶子结点的父结点为黑色：将父结点变为红色，将兄弟结点变为黑色，左旋父结点，删除叶子结点。

● 从某个结点出发（不含该结点）到达一个叶子结点的任意一条简单路径上的黑色结点个数称为该结点的黑高。根结点的黑高，称为红黑树的黑高度。

● this->root->left‌ 的涵义
‌this->root->left‌ 表示访问当前对象的根节点（root）的左子节点（left）。在 C++ 中，这种表达方式用于访问类的成员变量。
具体来说，this 关键字用于指向当前对象的实例，而 -> 操作符用于通过指针访问对象的成员。因此，this->root->left 表示访问当前对象的根节点的左子节点。

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int black=1;
const int red=0;

struct Node { //Red Black Tree's node
    Node *left,*right;
    int key,vol;
    int color;
    Node(int x):key(x),vol(1),color(red) {};
};

class RBTree {
    private:
        int vol;
        Node *root,*next;
        bool ans;

    public:
        RBTree() {
            root = new Node(0);
            root->color = black;
            root->left = root->right = root;
            root->vol = 0;
            next = nullptr;
            vol = 0;
        }

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

        bool isBalance() {
            Node *root = this->root->left;
            if(root->color == red) return false;
            int cnt = 0; //number of black nodes in the leftmost path
            auto left = root;
            while(left != this->root) {
                if(left->color == black) cnt++;
                left = left->left;
            }
            int blackNum = 0;
            return _isBalance(root, this->root,cnt,blackNum);
        }

        bool insert(int x) {
            ans = false;
            insert(root->left, x);
            root->left->color = black;
            return ans;
        }

        bool erase(int x) {
            ans = false;
            next = nullptr;
            erase(root->left,x);
            root->left->color = black;
            return ans;
        }

        int get_rank(int x) {
            Node *cur = root->left;
            int rank = 1;
            while(cur != root && cur != nullptr) {
                if(x <= cur->key) cur = cur->left;
                else {
                    rank += cur->left->vol+1;
                    cur = cur->right;
                }
            }
            return rank;
        }

        int get_val(int rank) {
            Node *cur = root->left;
            while(cur != root && cur != nullptr) {
                if(cur->left->vol+1 == rank) break;
                else if(cur->left->vol >= rank) cur = cur->left;
                else {
                    rank -= cur->left->vol+1;
                    cur = cur->right;
                }
            }
            return cur->key;
        }

        int get_pre(int x) {
            Node *p = root->left;
            int pre;
            while(p != root && p != nullptr) {
                if(p->key<x) {
                    pre = p->key;
                    p = p->right;
                } else p = p->left;
            }
            return pre;
        }

        int get_next(int x) {
            Node *p = root->left;
            int next;
            while(p != root && p != nullptr) {
                if(p->key>x) {
                    next = p->key;
                    p = p->left;
                } else p = p->right;
            }
            return next;
        }

    private:
        bool _isBalance(Node *root, Node *parent, int base, int blackNum) {
            if(root == this->root) {
                if(base != blackNum) return false;
                return true;
            }
            if(root->color == red && parent->color == red) return false;
            if(root->color == black) blackNum++;
            return _isBalance(root->left, root, base, blackNum) && _isBalance(root->right, root, base, blackNum);
        }

        void left_rotate(Node *&T) {
            Node *right = T->right;
            T->right = right->left;
            right->left = T;
            T = right;
            update(T->left), update(T);
        }

        void right_rotate(Node *&T) {
            Node *left = T->left;
            T->left = left->right;
            left->right = T;
            T = left;
            update(T->right), update(T);
        }

        bool hasRedChild(Node *&T) {
            if(T == root) return false;
            return T->left->color == red || T->right->color == red;
        }

        void update(Node *cur) {
            if(cur == root) return;
            cur->vol = cur->left->vol+cur->right->vol+1;
        }

        bool precursor(Node *&cur, int &key) {
            bool needSave = false;
            if(cur->right == root) {
                Node *temp = cur;
                key = cur->key;
                cur = cur->left;
                if(temp->color == red) needSave = false;
                else if(cur->color == red) {
                    cur->color = black;
                    needSave = false;
                } else {
                    next = cur;
                    needSave = true;
                }
                delete temp;
                return needSave;
            }
            needSave = precursor(cur->right, key);

            if(needSave) return _erase(cur);
            update(cur);
            return needSave;
        }

        bool erase(Node *&cur, int &key) {
            bool needSave = false;
            if(cur == root) return ans=false;
            else if(cur->key < key)
                needSave = erase(cur->right, key);
            else if(cur->key > key) needSave = erase(cur->left, key);
            else {
                ans = true;
                if(cur->left == root) {
                    Node *temp = cur;
                    cur = cur->right;
                    if(temp->color == red) needSave = false;
                    else if(cur->color == red) {
                        cur->color = black;
                        needSave = false;
                    } else {
                        next = cur;
                        needSave = true;
                    }

                    delete temp;
                    return needSave;
                } else if(cur->right == root) {
                    Node *temp = cur;
                    cur = cur->left;
                    if(temp->color == red) needSave = false;
                    else if(cur->color == red) {
                        cur->color = black;
                        needSave = false;
                    } else {
                        next = cur;
                        needSave = true;
                    }

                    delete temp;
                    return needSave;
                }

                needSave = precursor(cur->left, cur->key);
            }

            if(needSave) return _erase(cur);
            update(cur);
            return needSave;
        }

        bool _erase(Node *&cur) {
            update(cur);
            if(next == nullptr) return false;
            else if(cur->left == next) {
                next = nullptr;
                if(cur->right->color == red) {
                    cur->right->color = black;
                    cur->color = red;
                    left_rotate(cur);
                    next = cur->left->left;
                    return _erase(cur->left);
                }

                if(hasRedChild(cur->right)) {
                    bool color = cur->color;
                    if(cur->right->right->color == black) right_rotate(cur->right);
                    left_rotate(cur);
                    cur->color = color;
                    cur->left->color = cur->right->color = black;
                    return false;
                } else if (cur->color == red) {
                    cur->color = black;
                    cur->right->color = red;
                    return false;
                } else if (cur->color == black) {
                    cur->right->color = red;
                    next = cur;
                    return true;
                }
            } else if(cur->right == next) {
                next = nullptr;
                if(cur->left->color == red) {
                    cur->left->color = black;
                    cur->color = red;
                    right_rotate(cur);
                    next = cur->right->right;
                    return _erase(cur->right);
                }

                if(hasRedChild(cur->left)) {
                    bool color = cur->color;
                    if(cur->left->left->color == black) left_rotate(cur->left);
                    right_rotate(cur);
                    cur->color = color;
                    cur->left->color = cur->right->color = black;
                    return false;
                } else if(cur->color == red) {
                    cur->color = black;
                    cur->left->color = red;
                    return false;
                } else if(cur->color == black) {
                    next = cur;
                    cur->left->color = red;
                    return true;
                }
            }
            return false;
        }

        bool insert(Node *&cur, int &key) {
            bool needSave = false;
            if(cur == root) {
                cur = new Node(key);
                cur->left = cur->right = root;
                vol++;
                ans = true;
                return true;
            } else if(key > cur->key) needSave = insert(cur->right, key);
            else needSave = insert(cur->left, key);

            if(needSave) return _insert(cur);
            update(cur);
            return needSave;
        }

        bool _insert(Node *&cur) { //double red
            update(cur);
            if(!hasRedChild(cur)) return false;
            else if(cur->left->color == red && cur->right->color == red) {
                if(!hasRedChild(cur->left) && !hasRedChild(cur->right)) return false;
                cur->left->color = cur->right->color = black;
                cur->color = red;
                return true;
            } else if(cur->left->color == red) {
                if(!hasRedChild(cur->left)) return true;
                if(cur->left->left->color == black) left_rotate(cur->left);
                right_rotate(cur);
                cur->color = black;
                cur->right->color = red;
                return false;
            } else if(cur->right->color == red) {
                if(!hasRedChild(cur->right)) return true;
                if(cur->right->right->color == black) right_rotate(cur->right);
                left_rotate(cur);
                cur->color = black;
                cur->left->color = red;
                return false;
            }
            return true;
        }
};

int main() {
    RBTree it;
    int n;
    cin>>n;
    while(n--) {
        int op,x;
        cin>>op>>x;
        if(op==1) it.insert(x);
        else if(op==2) it.erase(x);
        else if(op==3) cout<<it.get_rank(x)<<endl;
        else if(op==4) cout<<it.get_val(x)<<endl;
        else if(op==5) cout<<it.get_pre(x)<<endl;
        else if(op==6) cout<<it.get_next(x)<<endl;
    }
    cout<<endl;
    return 0;
}

/*
in:
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

out:
106465
84185
492737
*/

【参考文献】
https://blog.csdn.net/Worthy_Wang/article/details/113853780
https://www.cnblogs.com/fush/p/18639446/RBT-AAT
https://www.cnblogs.com/jcwy/p/18513114
https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/
https://www.sanfoundry.com/cpp-program-implement-red-black-tree/
https://codeofcode.org/lessons/red-black-trees-in-cpp/
https://www.geeksforgeeks.org/red-black-tree-in-cpp/
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
https://blog.csdn.net/qq_16762209/article/details/134561421
https://blog.csdn.net/qq_16762209/article/details/134431094