题解 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.从根节点到每个叶子的所有路径都包含相同数目的黑色节点(这个数值叫做黑高度)。

如下面一棵树就是红黑树(请自行脑补外部节点):

而这几棵树就不是:

红黑树有几个变种,如AA树等,就此题而言,我将使用自己实现的最常见的红黑树模版

#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的结构体:


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

迭代器

迭代器的结构体也很容易写出来啦:

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容易修正),然后判断是否出现双红现象,修正该节点即可。

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):

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()里面判断,因为不论是直接插入还是上溢都有可能出现这种情况。

直接return返回就好,不解释……

2.父亲为红色(则父亲非根,祖父非空),叔叔bro(父亲)为黑色(注意:可能是叶子NULL,需要判断;祖父可能是根,需要判断)。(RR-1)

若修正节点x是祖父g的左儿子的左儿子或右儿子的右儿子(即互为同向祖孙关系),将g单旋一次(将x的父亲p伸展到g位置),再将g染红、p染黑即可;若x不是g的同向孙子,需要将x的父亲p旋转一次,再旋转g一次(将x伸展到g位置),最后将g染红、x染黑即可。

3.父亲为红色,叔叔为红色。(RR-2)

双红修正中唯一需要迭代或递归的情况。将祖父g染红、叔叔u和父亲p染黑,双红缺陷就会上溢两层,下一步就是修正g的双红缺陷啦!

但要注意的是,g有可能是树根。如果这种情况上溢到了树根,只需要将g再染黑即可,此时全树黑高度增加1。虽然这样可能会遍历整棵树的O(log n)个节点,但是分摊意义下,SolveDoubleRed()的时间复杂度为O(1)。可以用势能分析法证明。

因此可以轻松写出SolveDoubleRed()函数啦:

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()


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)实现,但此处注重效率,可以另写查找算法:

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大

就像快速选择一样,非常简单对不对?

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

找到元素的名次

更简单了有木有?

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()。

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)。

不说我的故事了,也不说邓教授的书了,下面直接进删除:

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)

许多教材将此情况最后判断,同时也认为是需要递归的情况,但我认为不必,首先判断这个情况,可以兼顾效率和代码可读性。

旋转父亲p,将b伸展到p位置,然后染黑b、染红p,于是将问题转化到了BB-2R或BB-3。

2.兄弟和父亲都为黑色,且兄弟没有红儿子(BB-2B)

根据我的跟踪记录,在一些插入操作居多的数据(如百科词条、医院药品记录、核电站控制系统等现实情况),此情况几乎不会发生,但只要出现全树黑高度减少1的情况,BB-2B就一定发生且下溢到根节点了。

染红兄弟b,双黑缺陷下溢到了父亲p,问题转化为了BB-1、BB-2B、BB-2R或BB-3中的一个。

如果被修正节点为根节点,只需要直接返回即可,此时全树黑高度减少1。

3.兄弟是黑色,没有红儿子,父亲为红色(BB-2R)

相当简单了吧,不用我介绍,聪明的读者应该也能想到:

染红b,染黑p,然后就完成修正了。

4.兄弟是黑色,有红儿子(BB-3)

同样不需要转化问题:

如果侄子c是父亲p的同向孙子的话,旋转p使兄弟b伸展到p位置,并将b染为p的颜色,p、c染黑即可;如果c不是p的同向孙子,伸展c到p的位置,并将c染为p的颜色,然后染黑p即可。

于是双黑修正SolveDoubleBlack的代码也很容易写出啦:

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的代码

为了方便调试,我在写红黑树板子的同时也写了一些调试代码:

#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

主程序

板子都有了,这个最好写了不是?

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日,祝大家除夕快乐,拜个早年。