题解 P3369 【【模板】普通平衡树(Treap/SBT)】
北极鹅
2018-02-15 15:15:42
看了那么多Splay、Treap、SBT、替罪羊树的题解,是时候来一篇此题历史最快的代码了。
**红黑树**,同样是一种自平衡二叉搜索树,由Rudolf Bayer最先提出,当时被称为平衡二叉B树(其实红黑树本质就是一棵B-tree),后来被Leo J. Guibas和Robert Sedgewick修改为"红黑树"。
# 红黑树具有如下性质:
1.红黑树是一棵平衡二叉搜索树,其中序遍历单调不减。
2.节点是红色或黑色。
3.根节点是黑色。
4.每个叶节点(也有称外部节点的,目的是将红黑树变为真二叉树,即NULL节点,空节点)是黑色的。
5.每个红色节点的两个子节点都是黑色。(换句话说,从每个叶子到根的所有路径上不能有两个连续的红色节点)
6.从根节点到每个叶子的所有路径都包含相同数目的黑色节点(这个数值叫做黑高度)。
如下面一棵树就是红黑树(请自行脑补外部节点):
![](https://cdn.luogu.com.cn/upload/pic/14509.png)
而这几棵树就不是:
![](https://cdn.luogu.com.cn/upload/pic/14510.png)
红黑树有几个变种,如AA树等,就此题而言,我将使用自己实现的最常见的**红黑树模版**。
```cpp
#include <cstdio>
#include <cctype>
#include <cassert>
using namespace std;
//#define __REDBLACK_DEBUG
#define bro(x) (((x)->ftr->lc == (x)) ? ((x)->ftr->rc) : ((x)->ftr->lc))
#define islc(x) ((x) != NULL && (x)->ftr->lc == (x))
#define isrc(x) ((x) != NULL && (x)->ftr->rc == (x))
template<typename T>
class redblacktree {
protected:
struct Node;
Node* _root; ////根节点位置
Node* _hot; ////临时维护的节点
void init(T);
void connect34(Node*, Node*, Node*, Node*, Node*, Node*, Node*);
void SolveDoubleRed(Node*); ////双红修正
void SolveDoubleBlack(Node*); //双黑修正
Node* find(T, const int); ////允许重复的查找
Node* rfind(T, const int); ////不允许重复的查找
Node* findkth(int, Node*);
int find_rank(T, Node*);
#ifdef __REDBLACK_DEBUG
void checkconnect(Node*);
void previs(Node*, int);
void invis(Node*, int);
void postvis(Node*, int);
#endif
public:
struct iterator;
redblacktree() : _root(NULL), _hot(NULL) {}
int get_rank(T);
iterator insert(T);
bool remove(T);
int size();
bool empty();
iterator kth(int);
iterator lower_bound(T);
iterator upper_bound(T);
#ifdef __REDBLACK_DEBUG
void vis();
void correctlyconnected();
#endif
};
```
其中定义宏__REDBLACK_DEBUG是为了方便调试,提交的时候可以注释掉。
宏islc()、isrc()是用来判断是否为左右儿子节点的,宏bro(x)返回节点x的兄弟。
# 节点
下面,根据需要维护的信息,我们可以轻松写出节点Node的结构体:
```cpp
template <typename T>
struct redblacktree<T>::Node {
T val; ////节点信息
bool RBc; ////节点颜色,若为true,则节点为Red;否则节点为Black.
Node* ftr; ////父亲
Node* lc; ////左儿子
Node* rc; ////右儿子
int s; ////域
Node( T v = T(), bool RB = true,
Node* f = NULL, Node* l = NULL, Node* r = NULL ,int ss = 1 )
: val(v), RBc(RB), ftr(f), lc(l), rc(r), s(ss) {}
Node* succ() { ////删除节点时用到的替代节点
Node* ptn = rc;
while(ptn->lc != NULL) {
--(ptn->s);
ptn = ptn->lc;
}
return ptn;
}
Node* left_node() { ////直接前驱
Node* ptn = this;
if(!lc) {
while(ptn->ftr && ptn->ftr->lc == ptn)
ptn = ptn->ftr;
ptn = ptn->ftr;
} else {
ptn = ptn->lc;
while(ptn->rc) {
ptn = ptn->rc;
}
}
return ptn;
}
Node* right_node() { ////直接后继
Node* ptn = this;
if(!rc) {
while(ptn->ftr && ptn->ftr->rc == ptn)
ptn = ptn->ftr;
ptn = ptn->ftr;
} else {
ptn = ptn->rc;
while(ptn->lc) {
ptn = ptn->lc;
}
}
return ptn;
}
void maintain() { ////维护域s
s = 1;
if(lc) s += lc->s;
if(rc) s += rc->s;
}
};
```
# 迭代器
迭代器的结构体也很容易写出来啦:
```cpp
template <typename T>
struct redblacktree<T>::iterator {
private:
Node* _real__node;
public:
iterator& operator++() {
_real__node = _real__node->right_node();
return *this;
}
iterator& operator--() {
_real__node = _real__node->left_node();
return *this;
}
T operator*() {
return _real__node->val;
}
iterator(Node* node_nn = NULL) : _real__node(node_nn) {}
iterator(T const& val_vv) : _real__node(rfind(val_vv, 0)) {}
iterator(iterator const& iter) : _real__node(iter._real__node) {}
};
```
# 插入、双红现象及其修正
插入比较好写,只需要将节点作为红色节点插入(保证不违反性质6,但可能违反性质5,毕竟性质5比性质6容易修正),然后判断是否出现双红现象,修正该节点即可。
```cpp
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::insert(T v) {
Node* ptn = find(v, 1);
if(_hot == NULL) {
init(v);
return iterator(_root);
}
ptn = new Node(v, true, _hot, NULL, NULL, 1);
if( _hot->val <= v )
_hot->rc = ptn;
else
_hot->lc = ptn;
SolveDoubleRed(ptn);
return iterator(ptn);
}
template <typename T>
void redblacktree<T>::init(T v) {
_root = new Node(v, false, NULL, NULL, NULL, 1);
#ifdef __REDBLACK_DEBUG
++blackheight;
#endif
}
```
此处使用了函数find,和rfind一样,第一个参数是待寻找值,第二个参数是每个路过的节点域的增加值(插入为1,删除为-1,普通查找为0):
```cpp
template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::find(T v, const int op) {
Node* ptn = _root; ////从根节点开始查找
_hot = NULL; ////维护父亲节点
while(ptn != NULL) {
_hot = ptn;
ptn->s += op;
if(ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}
return ptn;
}
template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::rfind(T v, const int op) {
Node* ptn = _root;
_hot = NULL;
while(ptn != NULL && ptn->val != v) {
_hot = ptn;
ptn->s += op;
if(ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}
return ptn;
}
```
## 双红修正
至于双红修正,可以分为以下三种情况:
### 1.没有出现双红。
这一点很重要,一定要加在SolveDoubleRed()里面判断,因为不论是直接插入还是上溢都有可能出现这种情况。
![](https://cdn.luogu.com.cn/upload/pic/14511.png)
直接return返回就好,不解释……
### 2.父亲为红色(则父亲非根,祖父非空),叔叔bro(父亲)为黑色(注意:可能是叶子NULL,需要判断;祖父可能是根,需要判断)。(RR-1)
![](https://cdn.luogu.com.cn/upload/pic/14513.png)
若修正节点x是祖父g的左儿子的左儿子或右儿子的右儿子(即互为同向祖孙关系),将g单旋一次(将x的父亲p伸展到g位置),再将g染红、p染黑即可;若x不是g的同向孙子,需要将x的父亲p旋转一次,再旋转g一次(将x伸展到g位置),最后将g染红、x染黑即可。
### 3.父亲为红色,叔叔为红色。(RR-2)
![](https://cdn.luogu.com.cn/upload/pic/14516.png)
双红修正中唯一需要迭代或递归的情况。将祖父g染红、叔叔u和父亲p染黑,双红缺陷就会上溢两层,下一步就是修正g的双红缺陷啦!
但要注意的是,g有可能是树根。如果这种情况上溢到了树根,只需要将g再染黑即可,此时全树黑高度增加1。虽然这样可能会遍历整棵树的O(log n)个节点,但是分摊意义下,SolveDoubleRed()的时间复杂度为O(1)。可以用势能分析法证明。
### 因此可以轻松写出SolveDoubleRed()函数啦:
```cpp
template <typename T>
void redblacktree<T>::SolveDoubleRed(Node* nn) {
while((!(nn->ftr)) || nn->ftr->RBc) {
if(nn == _root) {
_root->RBc = false;
#ifdef __REDBLACK_DEBUG
++blackheight;
#endif
return;
}
Node* pftr = nn->ftr;
if(!(pftr->RBc)) return; ////No double-red
Node* uncle = bro(nn->ftr);
Node* grdftr = nn->ftr->ftr;
if(uncle != NULL && uncle->RBc) { ////RR-2
grdftr->RBc = true;
uncle->RBc = false;
pftr->RBc = false;
nn = grdftr;
} else { ////RR-1
if(islc(pftr)) {
if(islc(nn)) {
pftr->ftr = grdftr->ftr;
if(grdftr == _root) _root = pftr;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
else grdftr->ftr->rc = pftr;
connect34(pftr, nn, grdftr, nn->lc, nn->rc, pftr->rc, uncle);
pftr->RBc = false;
grdftr->RBc = true;
} else {
nn->ftr = grdftr->ftr;
if(grdftr == _root) _root = nn;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
else grdftr->ftr->rc = nn;
connect34(nn, pftr, grdftr, pftr->lc, nn->lc, nn->rc, uncle);
nn->RBc = false;
grdftr->RBc = true;
}
} else {
if(islc(nn)) {
nn->ftr = grdftr->ftr;
if(grdftr == _root) _root = nn;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
else grdftr->ftr->rc = nn;
connect34(nn, grdftr, pftr, uncle, nn->lc, nn->rc, pftr->rc);
nn->RBc = false;
grdftr->RBc = true;
} else {
pftr->ftr = grdftr->ftr;
if(grdftr == _root) _root = pftr;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
else grdftr->ftr->rc = pftr;
connect34(pftr, grdftr, nn, uncle, pftr->lc, nn->lc, nn->rc);
pftr->RBc = false;
grdftr->RBc = true;
}
}
return;
}
}
}
```
## 统一重平衡
为了简化代码,旋转操作都使用了统一重平衡函数connect34()
```cpp
template <typename T>
void redblacktree<T>::connect34( Node* nroot, Node* nlc, Node* nrc,
Node* ntree1, Node* ntree2, Node* ntree3, Node* ntree4) {
nlc->lc = ntree1;
if(ntree1 != NULL) ntree1->ftr = nlc;
nlc->rc = ntree2;
if(ntree2 != NULL) ntree2->ftr = nlc;
nrc->lc = ntree3;
if(ntree3 != NULL) ntree3->ftr = nrc;
nrc->rc = ntree4;
if(ntree4 != NULL) ntree4->ftr = nrc;
nroot->lc = nlc;
nlc->ftr = nroot;
nroot->rc = nrc;
nrc->ftr = nroot;
nlc->maintain();
nrc->maintain();
nroot->maintain();
}
```
# 两种bound
lower_bound(v)、upper_bound(v)两个函数,分别返回红黑树中不大于v的最大的元素、大于v的最小的元素。可以用rfind(v, 0)实现,但此处注重效率,可以另写查找算法:
```cpp
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::lower_bound(T v) {
Node* ptn = _root;
while(ptn) {
_hot = ptn;
if(ptn->val < v) {
ptn = ptn->rc;
} else {
ptn = ptn->lc;
}
}
if(_hot->val < v) {
ptn = _hot;
} else {
ptn = _hot->left_node();
}
return iterator(ptn);
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::upper_bound(T v) {
Node* ptn = _root;
while(ptn) {
_hot = ptn;
if(ptn->val > v) {
ptn = ptn->lc;
} else {
ptn = ptn->rc;
}
}
if(_hot->val > v) {
ptn = _hot;
} else {
ptn = _hot->right_node();
}
return iterator(ptn);
}
```
# 寻找第k大
就像快速选择一样,非常简单对不对?
```cpp
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::kth(int rank) {
return iterator(findkth(rank, _root));
}
template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::findkth(int rank, Node* ptn) {
if(!(ptn->lc)) {
if(rank == 1) {
return ptn;
} else {
return findkth(rank - 1, ptn->rc);
}
} else {
if(ptn->lc->s == rank - 1) return ptn;
else if(ptn->lc->s >= rank) return findkth(rank, ptn->lc);
else return findkth(rank - (ptn->lc->s) - 1, ptn->rc);
}
}
```
# 找到元素的名次
更简单了有木有?
```cpp
template <typename T>
int redblacktree<T>::get_rank(T v) {
return find_rank(v, _root);
}
template <typename T>
int redblacktree<T>::find_rank(T v, Node* ptn) {
if(!ptn) return 1;
else if(ptn->val >= v) return find_rank(v, ptn->lc);
else return (1 + ((ptn->lc) ? (ptn->lc->s) : 0) + find_rank(v, ptn->rc));
}
```
# 其他接口
介绍删除之前,我们可以做一些比较简单的接口操作,如size()、empty()。
```cpp
template <typename T>
int redblacktree<T>::size() {
return _root->s;
}
template <typename T>
bool redblacktree<T>::empty() {
return !_root;
}
```
# 删除、双黑现象及其修正
俗话说:老鼠拉木锨,大头在后边。删除和双黑修正是红黑树最令人恶心和窒息的操作,许多大学教材对此闭口不谈,连清华的《数据结构》也讲述地十分混乱(但编者邓俊辉教授绝对是我的恩人,2017提高组NOIP考试之前偶然瞥了一眼《数据结构》里面的希尔排序那一章,里面一个数论问题吸引了我的注意,于是我不经意间记下了那个公式:x(g, h) = g\*h - g - h,第二天看到题我笑了,AC了D1T1)。
不说我的故事了,也不说邓教授的书了,下面直接进删除:
```cpp
template <typename T>
bool redblacktree<T>::remove(T v) {
Node* ptn = rfind(v, -1);
if(!ptn) return false;
Node* node_suc;
while(ptn->lc || ptn->rc) { ////迭代寻找真后继
if(!(ptn->lc)) {
node_suc = ptn->rc;
} else if(!(ptn->rc)) {
node_suc = ptn->lc;
} else {
node_suc = ptn->succ();
}
--(ptn->s);
ptn->val = node_suc->val;
ptn = node_suc;
}
if(!(ptn->RBc)) {
--(ptn->s);
SolveDoubleBlack(ptn);
}
if(ptn == _root) {
_root = NULL;
delete ptn;
return true;
}
if(ptn->ftr->lc == ptn)
ptn->ftr->lc = NULL;
else
ptn->ftr->rc = NULL;
delete ptn;
return true;
}
```
看似非常简单对不对?只是因为我没有给出那一百来行的SolveDoubleBlack()代码……
## 双黑修正
双黑修正比较厉害,情况一共四种,同样只有一种情况需要迭代或递归。双黑修正不容易理解的就是SolveDoubleBlack(Node* x)的参数x。必黑的节点x代表,x的左右儿子黑高度均相等,即若以x作为根,子树x并不存在双黑缺陷,但x比兄弟bro(x)的黑高度少1,因此需要修正。
双黑修正的4种情况如下:
### 1.兄弟为红色(BB-1)
许多教材将此情况最后判断,同时也认为是需要递归的情况,但我认为不必,首先判断这个情况,可以兼顾效率和代码可读性。
![](https://cdn.luogu.com.cn/upload/pic/14521.png)
旋转父亲p,将b伸展到p位置,然后染黑b、染红p,于是将问题转化到了BB-2R或BB-3。
### 2.兄弟和父亲都为黑色,且兄弟没有红儿子(BB-2B)
根据我的跟踪记录,在一些插入操作居多的数据(如百科词条、医院药品记录、核电站控制系统等现实情况),此情况几乎不会发生,但只要出现全树黑高度减少1的情况,BB-2B就一定发生且下溢到根节点了。
![](https://cdn.luogu.com.cn/upload/pic/14523.png)
染红兄弟b,双黑缺陷下溢到了父亲p,问题转化为了BB-1、BB-2B、BB-2R或BB-3中的一个。
如果被修正节点为根节点,只需要直接返回即可,此时全树黑高度减少1。
### 3.兄弟是黑色,没有红儿子,父亲为红色(BB-2R)
相当简单了吧,不用我介绍,聪明的读者应该也能想到:
![](https://cdn.luogu.com.cn/upload/pic/14524.png)
染红b,染黑p,然后就完成修正了。
### 4.兄弟是黑色,有红儿子(BB-3)
同样不需要转化问题:
![](https://cdn.luogu.com.cn/upload/pic/14525.png)
如果侄子c是父亲p的同向孙子的话,旋转p使兄弟b伸展到p位置,并将b染为p的颜色,p、c染黑即可;如果c不是p的同向孙子,伸展c到p的位置,并将c染为p的颜色,然后染黑p即可。
### 于是双黑修正SolveDoubleBlack的代码也很容易写出啦:
```cpp
template <typename T>
void redblacktree<T>::SolveDoubleBlack(Node* nn) {
while(nn != _root) {
Node* pftr = nn->ftr;
Node* bthr = bro(nn);
if(bthr->RBc) { ////BB-1
bthr->RBc = false;
pftr->RBc = true;
if(_root == pftr) _root = bthr;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(islc(nn)) {
connect34(bthr, pftr, bthr->rc, nn, bthr->lc, bthr->rc->lc, bthr->rc->rc);
} else {
connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, nn);
}
bthr = bro(nn);
pftr = nn->ftr;
}
if(bthr->lc && bthr->lc->RBc) { ////BB-3
bool oldRBc = pftr->RBc;
pftr->RBc = false;
if(pftr->lc == nn) {
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr->lc;
else
pftr->ftr->rc = bthr->lc;
}
bthr->lc->ftr = pftr->ftr;
if(_root == pftr) _root = bthr->lc;
connect34(bthr->lc, pftr, bthr, pftr->lc, bthr->lc->lc, bthr->lc->rc, bthr->rc);
} else {
bthr->lc->RBc = false;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(_root == pftr) _root = bthr;
connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, pftr->rc);
}
pftr->ftr->RBc = oldRBc;
return;
} else if(bthr->rc && bthr->rc->RBc) { ////BB-3
bool oldRBc = pftr->RBc;
pftr->RBc = false;
if(pftr->lc == nn) {
bthr->rc->RBc = false;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(_root == pftr) _root = bthr;
connect34(bthr, pftr, bthr->rc, pftr->lc, bthr->lc, bthr->rc->lc, bthr->rc->rc);
} else {
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr->rc;
else
pftr->ftr->rc = bthr->rc;
}
bthr->rc->ftr = pftr->ftr;
if(_root == pftr) _root = bthr->rc;
connect34(bthr->rc, bthr, pftr, bthr->lc, bthr->rc->lc, bthr->rc->rc, pftr->rc);
}
pftr->ftr->RBc = oldRBc;
return;
}
if(pftr->RBc) { ////BB-2R
pftr->RBc = false;
bthr->RBc = true;
return;
} else { ////BB-2B
bthr->RBc = true;
nn = pftr;
}
}
#ifdef __REDBLACK_DEBUG
--blackheight;
#endif
}
```
# Debug的代码
为了方便调试,我在写红黑树板子的同时也写了一些调试代码:
```cpp
#ifdef __REDBLACK_DEBUG
int blackheight(0);
template <typename T> ////先序遍历
void redblacktree<T>::previs(Node* ptn, int cnt) {
if(ptn == NULL) {
if(blackheight == -1) blackheight = cnt;
assert(blackheight == cnt);
return;
}
printf("%d %s %d \n", ptn->val, ptn->RBc ? "Red" : "Black", ptn->s);
if(!(ptn->RBc)) ++cnt;
previs(ptn->lc, cnt);
previs(ptn->rc, cnt);
}
template <typename T> ////中序遍历
void redblacktree<T>::invis(Node* ptn, int cnt) {
if(ptn == NULL) {
if(blackheight == -1) blackheight = cnt;
assert(blackheight == cnt);
return;
}
if(!(ptn->RBc)) ++cnt;
invis(ptn->lc, cnt);
printf("%d %s %d \n", ptn->val, ptn->RBc ? "Red" : "Black", ptn->s);
invis(ptn->rc, cnt);
}
template <typename T> ////后序遍历
void redblacktree<T>::postvis(Node* ptn, int cnt) {
if(ptn == NULL) {
if(blackheight == -1) blackheight = cnt;
assert(blackheight == cnt);
return;
}
if(!(ptn->RBc)) ++cnt;
postvis(ptn->lc, cnt);
postvis(ptn->rc, cnt);
printf("%d %s %d \n", ptn->val, ptn->RBc ? "Red" : "Black", ptn->s);
}
template <typename T> ////输出所有序遍历的接口
void redblacktree<T>::vis() {
printf("BlackHeight:\t%d\n", blackheight);
printf("------pre-vis------\n");
previs(_root, 0);
printf("------in-vis------\n");
invis(_root, 0);
printf("------post-vis------\n");
postvis(_root, 0);
}
template <typename T> ////验证所有节点与父亲的连接是否正常、域s是否维护正常
void redblacktree<T>::checkconnect(Node* ptn) {
if(!ptn) return;
assert(ptn->s > 0);
if(ptn->lc && ptn->lc->ftr != ptn) {
printf("Oops! %d has a lc %d, but it failed to point its ftr!\n", ptn->val, ptn->lc->val);
}
if(ptn->rc && ptn->rc->ftr != ptn) {
printf("Oops! %d has a rc %d, but it failed to point its ftr!\n", ptn->val, ptn->rc->val);
}
int sss = ptn->s;
if(ptn->lc) sss -= ptn->lc->s;
if(ptn->rc) sss -= ptn->rc->s;
if(sss - 1) {
printf("Damn! %d's size is %d, but the sum of its children's size is %d!\n", ptn->val, ptn->s, ptn->s - sss);
}
checkconnect(ptn->lc);
checkconnect(ptn->rc);
}
template <typename T>
void redblacktree<T>::correctlyconnected() {
checkconnect(_root);
}
#endif
```
# 主程序
板子都有了,这个最好写了不是?
```cpp
inline
int readint() {
int ret(0);
int sgn(1);
char c;
while(isspace(c = getchar()));
if(c == '-') {
sgn = -1;
c = getchar();
}
while(isdigit(c)) {
ret = (ret << 3) + (ret << 1) + c - '0';
c = getchar();
}
return ret * sgn;
}
#define ri readint()
int opt, x;
int tot;
redblacktree<int> my_tree;
int main() {
register int i;
tot = ri;
redblacktree<int>::iterator it;
for(i = 0; i < tot; ++i) {
opt = ri;
x = ri;
switch(opt) {
case 1:
my_tree.insert(x);
break;
case 2:
my_tree.remove(x);
break;
case 3:
printf("%d\n", my_tree.get_rank(x));
break;
case 4:
it = my_tree.kth(x);
printf("%d\n", *it);
break;
case 5:
it = my_tree.lower_bound(x);
printf("%d\n", *it);
break;
case 6:
it = my_tree.upper_bound(x);
printf("%d\n", *it);
break;
default:
break;
}
}
return 0;
}
```
# 总结
红黑树应该是除哈希表外最快的搜索结构了(哈希表由于占内存太大,实际情况常常不用)。很多人认为红黑树太难写,就放弃学习它。我认为红黑树代码并不麻烦,和线段树的难度差不多,如果学会了会很容易写出来。
写于2018年2月15日,祝大家除夕快乐,拜个早年。