题解 P3369 【【模板】普通平衡树(Treap/SBT)】

北极鹅

2018-02-15 15:15:42

Solution

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