前言#
建议先对红黑树的五条基本性质有一个整体认识，这样再看代码时会更容易把“旋转”和“染色”放回到对应的约束里。
这篇文章重点不在定义本身，而在实现策略：插入时怎样理解双红冲突，删除时怎样处理双黑，递归写法下应该在什么时机检查祖父节点或父节点，以及这些规则如何落成一份可运行的完整模板。
首先明确定义：
// 1.每个节点非黑即红
// 2.根为黑
// 3.叶子节点(nullptr)为黑
// 4.红色节点的子节点为黑
// 5.从任何一个节点出发,并达到这个节点下面的所有叶子节点的所有路径.这些路径中,含有的黑色节点个数相同.
有三个有趣的问题：
1.为什么根为黑？ 答：这由性质4和性质5决定，若只有一个节点，那么根节点是黑还是红无所谓，但是两个节点以上根节点就必须为黑。
2.为什么没有第六条性质：一个红黑树的左右子树均为红黑树？答：根节点为黑，但是每个节点非黑即红，这会导致每个节点都是黑色。
3.为什么红黑树高度最高为 2log2(n)+1 ？答：他等价于一个四阶B-树
还要思考的几个问题：
1..黑色节点的孩子有几种可能的情况？答：一黑一红，一红，两红，空
2..红色节点的孩子有几种可能的情况？答：两黑，空
3.红黑树在插入时什么时候高度加一？个人想法：当染色波及至根结点时。
强烈推荐一个数据结构可视化的网站：Data Structure Visualization (USFCA)
关于红黑树有一些疑问的话去这里可以清晰地看到策略到底是怎么样的。我在写的时候，网上讲的不同人有不同的策略，让人有些迷惑。
我这里用的是递归式的，原因是想运用写AVL树的时候总结的范式（递归，递过去引用型传递寻找位置，归回来的时候依次检查。），常数可能较大。
// 方法论：
// 1.插入调整看祖父
// 2.删除调整看父亲
看定义：#
const bool black = 1;
const bool red = 0;
struct RBnode
{
RBnode *left, *right;
int key, Size;
bool color;
RBnode(int x) : key(x), Size(1), color(red) {}
};
class RBTree
{
private:
unsigned int Size;
RBnode *root, *double_black; // double_black指向被删除节点的继任节点，用来判断是在父亲的左还是右，这样不用把double_black当做color的一种，让结构体中的color使用bool，一个字节。
bool reslut; // 作为返回值
RBTree()
{
root = new RBnode(0);
// 设置一个头结点，同时把所有空指针全部指向头结点。
// 头结点设置为黑，这与红黑树定义中的叶子结点为黑色是一致的。
root->color = black;
root->left = root->right = root; // 为了全部都指向头结点
root->Size = 0;
double_black = nullptr; // 初始时指向空，这样不会出现冲突
Size = 0;
}看search函数：
public:
RBnode *search(int x)
{
return search(root->left, x);
}
private:
RBnode *search(RBnode *&now, int &key)
{
if (now == root)
return nullptr;
else if (now->key > key)
return search(now->left, key);
else if (now->key < key)
return search(now->right, key);
else
return now;
}看辅助函数：
private:
void Lrotate(RBnode *&T)//注意使用引用型参数
{
RBnode *right = T->right;
T->right = right->left;
right->left = T;
T = right;
update(T->left), update(T); // 别忘了更新Size
}
void Rrotate(RBnode *&T)
{
RBnode *left = T->left;
T->left = left->right;
left->right = T;
T = left;
update(T->right), update(T);
}
bool hasRedChild(RBnode *&T)
{
if (T == root) // 空节点，返回false
return false;
return T->left->color == red || T->right->color == red;
}
void update(RBnode *now)
{
if (now == root) // 头结点，不管
return;
now->Size = now->left->Size + now->right->Size + 1;
}开始讲插入函数：#
插入策略：
1.插入的节点颜色为红色，这是容易理解的，因为黑色会影响性质5，但红色不会。
2.如果插入节点的父节点为黑色，不需要调整
3.如果插入节点的父节点为红色，需要调整，但需要站在祖父节点调整。下面以祖父视角判断情况并调整。
4.如果没有红孩子，不需要调整。
5.如果左右均为红孩子，判断是否存在红孙子，如果存在红孙子，则把两个孩子染成黑色，本身染成红色，递归继续调整；如果不存在红孙子，不需要调整。
6.如果左边为红孩子，判断左边是否存在红孙子，如果不存在，不需要调整；如果存在红孙子，判断红孙子是否是左孩子的右孩子（即是否是LR型），是则先左旋左孩子，不然不左旋，但之后均要右旋本身，然后新节点染黑，新右孩子染红。//这种情况在插入时，其实是不会有右孩子的，否则这不满足性质5，但是在情况5的递归染色下，可能会出现存在黑色右孩子的情况。
7.如果右边为红孩子，和6同理。
8.注意检查函数中，如果当前站在的是插入节点的父亲节点，应该让检查函数不作任何事情返回，并告知祖父，下次应该检查。
代码（为了尽可能减少检查函数的调用，使用了一个NeedMaintain变量返回，交给递归时交给父亲节点，告知它是否需要继续调整。感觉这个NeedMaintain应该是我的自创吧，看别的文章的时候没看到，启示是AVL中check函数其实有很多时候不需要旋转。）
public:
bool insert(int x)
{
reslut = false;
insert(root->left, x);
root->left->color = black; // 根节点始终为黑色
return reslut;
}
private:
bool insert_maintain(RBnode *&now) // 解决双红现象，返回值为NeedMaintain
{
// 插入策略，因为站在祖父节点，所以理应在父亲的时候会出现直接返回true的情况
update(now);
if (!hasRedChild(now)) // 祖父节点没有红孩子，不再需要调整，直接false
return false;
else if (now->left->color == red && now->right->color == red) // 左右均为红
{
if (!hasRedChild(now->left) && !hasRedChild(now->right)) // 没有红色孙子，不需要调整
return false;
now->left->color = now->right->color = black; // 交换颜色
now->color = red; // 父亲染成红色（根节点这个时候可能为红，之后会在inset进行处理）
return true;
}
else if (now->left->color == red) // 左孩子为红
{
if (!hasRedChild(now->left)) // 但是没有红孙子，说明这个时候可能是站在父亲节点，所以return true再次进行调整
return true;
if (now->left->left->color == black) // 说明LR型红孙子，需要左旋
Lrotate(now->left);
Rrotate(now);
now->color = black; // 父亲，孩子交换染色
now->right->color = red;
return false;
}
else if (now->right->color == red)
{
if (!hasRedChild(now->right))
return true;
if (now->right->right->color == black) // 说明是RL型红孙子，需要右旋
Rrotate(now->right);
Lrotate(now);
now->color = black;
now->left->color = red;
return false;
}
return true;
}
bool insert(RBnode *&now, int &key)
{
bool NeedMaintain = false; // 定义变量NeedMaintain表示该节点的父节点是否需要调整，用于降低常数
if (now == root)
{
now = new RBnode(key); // 默认为红色
now->left = now->right = root;
++Size;
reslut = true;
return true; // 插入，
}
else if (key > now->key)
NeedMaintain = insert(now->right, key);
else // 这里允许了重复插入
NeedMaintain = insert(now->left, key);
if (NeedMaintain) // 需要调整，调用insertmaintain
return insert_maintain(now);
update(now); // 不需要调整，更新一下节点的Size值
return NeedMaintain;
}开始讲删除函数：#
策略：
1.如果删除节点有两个孩子，则找前驱，转化为单个孩子的。下面的讨论均基于删除节点的孩子个数小于等于1。
2.如果删除节点为红色，直接让孩子替代，不需要调整。//因为红色节点只可能为空或者有两个黑孩子，所以这个时候必然为终端非叶子节点，即没有孩子。
3.如果删除节点为黑色，但是有红孩子，则红孩子染黑，然后替代，不需要调整。
上面两种因为不需要调整，所以是站在删除节点的角度考虑的，下面的讨论均站在 删除节点的继任者（指删除节点已经被删除过了） 的 父节点 考虑。这时称 父节点为P ， 删除节点的继任者为N，删除节点的兄弟为B ，为了方便，把N当做P的左孩子。
- B黑色，有红孩子，如果它在B的左孩子，则先右旋B，但之后均左旋P，把新的P染成原来的P的颜色，把新P的左右孩子均染成黑色，之后不再需要调整。
5.B黑色，无红孩子，但父亲为红色，把父亲染成黑色，B染成红色，之后不再需要调整。
6.B黑色，无红孩子，父亲为黑色。把B染成红色，P不动，可以看到这个时候以P为根的子树满足红黑树性质5，但是相比变化前这个子树减少了一个黑色路径个数（原来为2，现在为1），所以需要向P的父亲去询问，所以递归调整P的父亲节点。
7.B为红色，其实这个情况应该最先判断，因为这个情况给的信息太多了。第一点，父亲为黑；第二点，B无红孩子；第三点，被删除节点为黑色，所以B一定有两个黑色孩子，但不知道B的两个黑色孩子是否存在红孩子。做法：把B染成黑色，P染成红色，然后左旋P。之后把新的P节点左孩子的左孩子（即LL孙子）当做N节点，调整新P节点的左孩子。实际上这个时候预期只会再变成情况5和情况4，这两种情况都不需要在进行调整。
8.如果N在P的右孩子，做法对称。
代码时的技巧：
1.使用引用型参数，这样不需要再判断当前是在上层的左孩子还是右孩子
2.使用一个double_black指针指示当前情况下那个是被删除节点的继任者。
3.使用NeedMaintain来告诉上一层是否需要继续调整。
4.情况2,3均在erase_maintain函数外进行处理，erase_maintain只处理黑色叶子节点的情况。
代码：
public:
bool erase(int x)
{
reslut = false;
double_black = nullptr; // 先置空
erase(root->left, x);
root->left->color = black; // 根染黑
return reslut;
}
private:
bool erase_maintain(RBnode *&now) // 返回值为是否需要继续调整
{
update(now);
if (double_black == nullptr)
return false; // 处理特殊情况
else if (now->left == double_black) // 在左边的情况，下面的在右边情况一致
{
double_black = nullptr; // 直接至为空，
if (now->right->color == red)
// 处理最难的情况，实际上，兄弟为红给了很多信息，
// 1.父亲为黑 2.因为被删除节点为黑色叶子，所以兄弟必有两个黑色叶子节点 3.兄弟的两个孩子可能还有红色叶子结点
{
now->right->color = black; // 交换颜色
now->color = red;
Lrotate(now); // 左旋当前节点
double_black = now->left->left; // 这个时候把被删除节点当做左孙子，实际上左孙子必为空
return erase_maintain(now->left); // 然后当做左孩子被删
}
if (hasRedChild(now->right)) // 有红孩子，可以借。兄弟为红可能会转移到这里。
{
bool color = now->color; // 父亲颜色
if (now->right->right->color == black) // 说明是RL型红孩子，先右旋
Rrotate(now->right);
Lrotate(now); // 左旋
now->color = color; // 当前继任原父亲节点颜色，
now->left->color = now->right->color = black; // 孩子染黑
return false; // 不需要调整
}
else if (now->color == red) // 父亲为红，双子为黑，并且左为叶子，简单的互换颜色即可。兄弟为红可能会转移到这里
{
now->color = black;
now->right->color = red;
return false;
}
else if (now->color == black)
// 父亲为黑，兄弟为黑并且没有红孩子，这个时候把兄弟染红之后相当于当前子树少了一个黑色节点，交给祖父处理，
{
now->right->color = red;
double_black = now; // double_black设置为当前
return true;
}
}
else if (now->right == double_black)
{
double_black = nullptr;
if (now->left->color == red)
{
now->left->color = black;
now->color = red;
Rrotate(now);
double_black = now->right->right;
return erase_maintain(now->right);
}
if (hasRedChild(now->left))
{
bool color = now->color;
if (now->left->left->color == black)
Lrotate(now->left);
Rrotate(now);
now->color = color;
now->left->color = now->right->color = black;
return false;
}
else if (now->color == red)
{
now->color = black;
now->left->color = red;
return false;
}
else if (now->color == black)
{
double_black = now;
now->left->color = red;
return true;
}
}
return false;
}
bool SuccessOr(RBnode *&now, int &key) // 寻找前驱，并且替代key值
{
bool NeedMaintain = false; // 还是判断是否需要删除调整
if (now->right == root) // 找到了前驱
{
RBnode *temp = now;
key = now->key; // 值替代
now = now->left; // 注意写法，引用型参数，这里会直接修改父亲的左孩子或者右孩子的指针
if (temp->color == red)
NeedMaintain = false; // 红色，不需要
else if (now->color == red) // 继任者为红色，不需要
{
now->color = black;
NeedMaintain = false;
}
else // 不然，doubleblack指向
{
double_black = now;
NeedMaintain = true;
}
delete temp;
return NeedMaintain;
}
NeedMaintain = SuccessOr(now->right, key);
if (NeedMaintain)
return erase_maintain(now);
update(now);
return NeedMaintain;
}
bool erase(RBnode *&now, int &key)
{
bool NeedMaintain = false; // 表示是否需要删除调整，降低一些常数
if (now == root)
return reslut = false;
else if (now->key < key)
NeedMaintain = erase(now->right, key);
else if (now->key > key)
NeedMaintain = erase(now->left, key);
else
{
reslut = true;
if (now->left == root) // 先判断度是否已经小于等于1
{
RBnode *temp = now;
now = now->right;
if (temp->color == red)
NeedMaintain = false; // 红色，不需要调整
else if (now->color == red) // 有红孩子，不需要调整
{
now->color = black; // 染红
NeedMaintain = false;
}
else // 黑色叶子节点
{
double_black = now; // double_black指向继任者，需要调整
NeedMaintain = true;
}
delete temp; // 删除
return NeedMaintain;
}
else if (now->right == root)
{
RBnode *temp = now;
now = now->left;
if (temp->color == red)
NeedMaintain = false;
else if (now->color == red)
{
now->color = black;
NeedMaintain = false;
}
else
{
double_black = now;
NeedMaintain = true;
}
delete temp;
return NeedMaintain;
}
// 度为2的节点，先去寻找前驱，并且注意这个地方不能return
NeedMaintain = SuccessOr(now->left, now->key);
}
if (NeedMaintain)
return erase_maintain(now);
update(now);
return NeedMaintain;
}#
全部代码：
#include <iostream>
#include <cmath>
#include <string>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const bool black = 1;
const bool red = 0;
// 插入站在祖父节点考虑，删除站在父节点考虑
// 红黑树定义：
// 1.每个节点非黑即红
// 2.根为黑
// 3.叶子节点(nullptr)为黑
// 4.红色节点的子节点为黑
// 5.从根触发的到所有叶子节点的路径上，黑色节点个数相同
// 方法论：
// 1.插入调整看祖父(从节点角度考虑，A插入至B孩子，A的祖父即B的父亲，也就是说对变动节点B来说，还是要看父亲节点)
// 2.删除节点看父亲
// 3.插入，删除的情况处理共五种
// PS：对于一个节点，如果其为黑色，其两个子节点均为红色，
// 这时，把两个子节点染成黑色，这个节点染成红色，之后这个子树仍然是红黑树，但是其上面的树可能需要调整，比如父节点如果是红色
// 对当前节点只涂黑不涂红，
struct RBnode
{
RBnode *left, *right;
int key, Size;
bool color;
RBnode(int x) : key(x), Size(1), color(red) {}
};
class RBTree
{
private:
unsigned int Size;
RBnode *root, *double_black; // double_black指向被删除节点的继任节点，用来判断是在父亲的左还是右
bool reslut; // 作为返回值
public:
bool IsBalance() // 判断平衡否
{
RBnode *root = this->root->left;
if (root->color == red)
{
cout << "black" << endl; // 为了测试
return false;
}
// 最左路径黑色结点数量做基准值
int banchmark = 0; // 保存最左侧路径中黑色结点的个数
auto left = root;
while (left != this->root)
{
if (left->color == black)
++banchmark;
left = left->left;
}
int blackNum = 0; // 递归遍历时记录黑色结点的个数
return _IsBalance(root, this->root, banchmark, blackNum);
}
bool _IsBalance(RBnode *root, RBnode *parent, int banchmark, int blackNum)
{
// 走到null之后，判断banchmark和blackNum是否相等
if (root == this->root)
{
if (banchmark != blackNum)
{
cout << "black not" << endl; // 为了测试
return false;
}
return true;
}
if (root->color == red && parent->color == red)
{
cout << "red not" << endl; // 为了测试
return false;
}
if (root->color == black) // 统计黑色节点的个数
{
++blackNum;
}
return _IsBalance(root->left, root, banchmark, blackNum) && _IsBalance(root->right, root, banchmark, blackNum);
}
RBTree()
{
root = new RBnode(0);
// 设置一个头结点，同时把所有空指针全部指向头结点。
// 头结点设置为黑，这与红黑树定义中的叶子结点为黑色是一致的。
root->color = black;
root->left = root->right = root; // 为了全部都指向头结点
root->Size = 0;
double_black = nullptr; // 初始时指向空，这样不会出现冲突
Size = 0;
}
bool insert(int x)
{
reslut = false;
insert(root->left, x);
root->left->color = black; // 根节点始终为黑色
return reslut;
}
RBnode *search(int x)
{
return search(root->left, x);
}
bool erase(int x)
{
reslut = false;
double_black = nullptr; // 先置空
erase(root->left, x);
root->left->color = black; // 根染黑
return reslut;
}
int get_rank(int x)
{
RBnode *now = root->left;
int rank = 1;
while (now != root && now != nullptr)
{
if (x <= now->key)
now = now->left;
else
{
rank += now->left->Size + 1;
now = now->right;
}
}
return rank;
}
int get_val(int rank)
{
RBnode *now = root->left;
while (now != root && now != nullptr)
{
if (now->left->Size + 1 == rank)
break;
else if (now->left->Size >= rank)
now = now->left;
else
{
rank -= now->left->Size + 1;
now = now->right;
}
}
return now->key;
}
int get_pre(int x)
{
RBnode *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)
{
RBnode *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 erase_maintain(RBnode *&now) // 返回值为是否需要继续调整
{
update(now);
if (double_black == nullptr)
return false; // 处理特殊情况
else if (now->left == double_black) // 在左边的情况，下面的在右边情况一致
{
double_black = nullptr; // 直接至为空，
if (now->right->color == red)
// 处理最难的情况，实际上，兄弟为红给了很多信息，
// 1.父亲为黑 2.因为被删除节点为黑色叶子，所以兄弟必有两个黑色叶子节点 3.兄弟的两个孩子可能还有红色叶子结点
{
now->right->color = black; // 交换颜色
now->color = red;
Lrotate(now); // 左旋当前节点
double_black = now->left->left; // 这个时候把被删除节点当做左孙子，实际上左孙子必为空
return erase_maintain(now->left); // 然后当做左孩子被删
}
if (hasRedChild(now->right)) // 有红孩子，可以借。兄弟为红可能会转移到这里。
{
bool color = now->color; // 父亲颜色
if (now->right->right->color == black) // 说明是RL型红孩子，先右旋
Rrotate(now->right);
Lrotate(now); // 左旋
now->color = color; // 当前继任原父亲节点颜色，
now->left->color = now->right->color = black; // 孩子染黑
return false; // 不需要调整
}
else if (now->color == red) // 父亲为红，双子为黑，并且左为叶子，简单的互换颜色即可。兄弟为红可能会转移到这里
{
now->color = black;
now->right->color = red;
return false;
}
else if (now->color == black)
// 父亲为黑，兄弟为黑并且没有红孩子，这个时候把兄弟染红之后相当于当前子树少了一个黑色节点，交给祖父处理，
{
now->right->color = red;
double_black = now; // double_black设置为当前
return true;
}
}
else if (now->right == double_black)
{
double_black = nullptr;
if (now->left->color == red)
{
now->left->color = black;
now->color = red;
Rrotate(now);
double_black = now->right->right;
return erase_maintain(now->right);
}
if (hasRedChild(now->left))
{
bool color = now->color;
if (now->left->left->color == black)
Lrotate(now->left);
Rrotate(now);
now->color = color;
now->left->color = now->right->color = black;
return false;
}
else if (now->color == red)
{
now->color = black;
now->left->color = red;
return false;
}
else if (now->color == black)
{
double_black = now;
now->left->color = red;
return true;
}
}
return false;
}
bool SuccessOr(RBnode *&now, int &key) // 寻找前驱，并且替代key值
{
bool NeedMaintain = false; // 还是判断是否需要删除调整
if (now->right == root) // 找到了前驱
{
RBnode *temp = now;
key = now->key; // 值替代
now = now->left; // 注意写法，引用型参数，这里会直接修改父亲的左孩子或者右孩子的指针
if (temp->color == red)
NeedMaintain = false; // 红色，不需要
else if (now->color == red) // 继任者为红色，不需要
{
now->color = black;
NeedMaintain = false;
}
else // 不然，doubleblack指向
{
double_black = now;
NeedMaintain = true;
}
delete temp;
return NeedMaintain;
}
NeedMaintain = SuccessOr(now->right, key);
if (NeedMaintain)
return erase_maintain(now);
update(now);
return NeedMaintain;
}
bool erase(RBnode *&now, int &key)
{
bool NeedMaintain = false; // 表示是否需要删除调整，降低一些常数
if (now == root)
return reslut = false;
else if (now->key < key)
NeedMaintain = erase(now->right, key);
else if (now->key > key)
NeedMaintain = erase(now->left, key);
else
{
reslut = true;
if (now->left == root) // 先判断度是否已经小于等于1
{
RBnode *temp = now;
now = now->right;
if (temp->color == red)
NeedMaintain = false; // 红色，不需要调整
else if (now->color == red) // 有红孩子，不需要调整
{
now->color = black; // 染红
NeedMaintain = false;
}
else // 黑色叶子节点
{
double_black = now; // double_black指向继任者，需要调整
NeedMaintain = true;
}
delete temp; // 删除
return NeedMaintain;
}
else if (now->right == root)
{
RBnode *temp = now;
now = now->left;
if (temp->color == red)
NeedMaintain = false;
else if (now->color == red)
{
now->color = black;
NeedMaintain = false;
}
else
{
double_black = now;
NeedMaintain = true;
}
delete temp;
return NeedMaintain;
}
// 度为2的节点，先去寻找前驱，并且注意这个地方不能return
NeedMaintain = SuccessOr(now->left, now->key);
}
if (NeedMaintain)
return erase_maintain(now);
update(now);
return NeedMaintain;
}
bool insert_maintain(RBnode *&now) // 解决双红现象，返回值为NeedMaintain
{
// 插入策略，因为站在祖父节点，所以理应在父亲的时候会出现直接返回true的情况
update(now);
if (!hasRedChild(now)) // 祖父节点没有红孩子，不再需要调整，直接false
return false;
else if (now->left->color == red && now->right->color == red) // 左右均为红
{
if (!hasRedChild(now->left) && !hasRedChild(now->right)) // 没有红色孙子，不需要调整
return false;
now->left->color = now->right->color = black; // 交换颜色
now->color = red; // 父亲染成红色（根节点这个时候可能为红，之后会在inset进行处理）
return true;
}
else if (now->left->color == red) // 左孩子为红
{
if (!hasRedChild(now->left)) // 但是没有红孙子，说明这个时候可能是站在父亲节点，所以return true再次进行调整
return true;
if (now->left->left->color == black) // 说明LR型红孙子，需要左旋
Lrotate(now->left);
Rrotate(now);
now->color = black; // 父亲，孩子交换染色
now->right->color = red;
return false;
}
else if (now->right->color == red)
{
if (!hasRedChild(now->right))
return true;
if (now->right->right->color == black) // 说明是RL型红孙子，需要右旋
Rrotate(now->right);
Lrotate(now);
now->color = black;
now->left->color = red;
return false;
}
return true;
}
bool insert(RBnode *&now, int &key)
{
bool NeedMaintain = false; // 定义变量NeedMaintain表示该节点的父节点是否需要调整，用于降低常数
if (now == root)
{
now = new RBnode(key); // 默认为红色
now->left = now->right = root;
++Size;
reslut = true;
return true; // 插入，
}
else if (key > now->key)
NeedMaintain = insert(now->right, key);
else // 这里允许了重复插入
NeedMaintain = insert(now->left, key);
if (NeedMaintain) // 需要调整，调用insertmaintain
return insert_maintain(now);
update(now); // 不需要调整，更新一下节点的Size值
return NeedMaintain;
}
RBnode *search(RBnode *&now, int &key)
{
if (now == root)
return nullptr;
else if (now->key > key)
return search(now->left, key);
else if (now->key < key)
return search(now->right, key);
else
return now;
}
void Lrotate(RBnode *&T)
{
RBnode *right = T->right;
T->right = right->left;
right->left = T;
T = right;
update(T->left), update(T); // 别忘了更新Size
}
void Rrotate(RBnode *&T)
{
RBnode *left = T->left;
T->left = left->right;
left->right = T;
T = left;
update(T->right), update(T);
}
bool hasRedChild(RBnode *&T)
{
if (T == root) // 空节点，返回false
return false;
return T->left->color == red || T->right->color == red;
}
void update(RBnode *now)
{
if (now == root) // 头结点，不管
return;
now->Size = now->left->Size + now->right->Size + 1;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
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) << '\n';
}
else if (op == 4)
{
cout << it.get_val(x) << '\n';
}
else if (op == 5)
{
cout << it.get_pre(x) << '\n';
}
else if (op == 6)
{
cout << it.get_next(x) << '\n';
}
else if (op == 7)
{
cout << it.search(x)->key << '\n';
}
}
cout << endl;
system("pause");
return 0;
}洛谷P3369AC记录（常数较大，未开O2）：#
