C++学习之旅【C++伸展树介绍以及红黑树的实现】
🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法》
✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介:
引言:前篇文章,小编已经介绍了关于C++AVL树的实现!相信大家应该有所收获!接下来我将带领大家继续深入学习C++的相关内容!本篇文章着重介绍关于C++伸展树介绍以及红黑树的实现!伸展树与红黑树是两类极具代表性的BBST,且在工程实践中各有不可替代的价值:伸展树摒弃了"严格平衡”的执念,通过“伸展”操作将最近访问的节点移至根节点,利用“局部性原理”优化频繁访问的场景,实现均摊O(logn)的时间复杂度,适合缓存、热点数据查询等场景;红黑树则通过给节点着色并遵守严格的颜色规则,确保树的最长路径不超过最短路径的两倍,以 “弱平衡” 换稳定的最坏O(logn)性能,是C++ STL 中 std::map、std::set 等容器的底层实现核心,也是工业界最常用的平衡BST 之一.那么这里面到底有哪些知识需要我们去学习的呢?废话不多说,带着这些疑问,下面跟着小编的节奏🎵一起去疯狂的学习吧！
目录
1.伸展树介绍
一种与AVL树类似的改进的二叉搜索树,称为伸展树.是由John Edward Hopcroft和Robert EndreTarjan于1985年共同发明的.与AVL树以及在第7章介绍并查集时的父指针表示的树的路径压缩一样,同属于自调整数据结构.在讨论AVL树时,主要关注点在于保持树的高度平衡,不要倾斜向一方,理想情况下使叶结点只出现在最低的一层或两层上.因此,如果一个新插入的结点破坏了树的平衡,就需要通过平衡旋转来加以调整.然而,是否这种重新调整总是必要的呢?对于二叉搜索树来说,它主要用于内存中目录的编制,因此,快速插入、搜索、删除元素才是我们关心的问题,而不是树的形状.通过平衡树可以提高效率,但这不是唯一的方法.
伸展树就是另一种提高搜索效率的方法.它参照了以下两种想法:
⑴单一旋转:其目的是将经常访问的结点最终上移到靠近根的地方,使得以后的访问比以前更快.为此,除根结点外,只要访问子女结点,就将它围绕它的父结点进行旋转.
⑵移动到根部:假设正在访问的结点将以很高的概率再次被访问,因此,对它反复进行子女—父结点旋转,直到被访问的结点位于根部为止.这样,即使下一次没有访问此结点,它仍然还在靠近根部的地方.
伸展树发展了上述想法,它提出了一组改进二叉搜索树性能的一组规则,每当执行搜索、插入、删除等操作时,就要依据这些规则调整二叉搜索树,从而保证操作的时间代价.
每当访问(包括搜索、插入或删除)一个结点s时,伸展树就执行一次叫做“展开”的过程.“展开”将结点s移到二叉搜索树的根部.当删除结点s时,“展开”把结点s的父结点上移到根结点.就像AVL树,一次“展开”由一组旋转组成.旋转有三种类型:单旋转、一字形旋转和之字形旋转.一次旋转的目的是通过调整结点s与它的父结点p和祖父结点g之间位置,把它上移到树的更高层.下面分情况讨论.①情况1:被访问结点s的父结点是根结点.此时执行单旋转,如图7.26所示.在保持二叉搜索树特性的情况下,结点s成为新的根,原来的根p成为它的子女结点.②情况2:同构的形状.结点s是其父结点p的左子女,结点p又是其父结点g的左子女(/).或者结点s是其父结点p的右子女,结点p又是其父结点g的右子女(\).此时执行一字形旋转,如图7.27所示.这是一个双旋转:首先围绕p旋转g,再围绕s旋转p.旋转发生后,当前刚访问的结点s调整到祖父结点的位置,同时仍保持了二叉搜索树的特性.③情况3:异构的形状.结点s是其父结点p的左子女,结点p又是其父结点g的右子女(>).或者结点s是其父结点p的右子女,结点p又是其父结点g的左子女(<=).此时执行之字形旋转,如图7.28所示.因为刚访问的结点s与其父结点p和祖父结点g形成折线,需要做与AVL树一样的双旋转,首先围绕s旋转p,再围绕s旋转g,把结点s上升到祖父结点的位置,并保持二叉搜索树的特性.
之字形旋转使得树结构趋向于平衡化,它将子树β和γ上升一层,并把子树δ下降一层,结果常常使树结构的高度减少1.而一字形旋转一般不会降低树结构的高度,它只是把刚访问的结点向根结点上移.
被访问结点s“展开”过程的算法描述如下面程序所示,它包括了一系列双旋转,提升结点s直到它到达根结点或根结点的一个子女结点.必要的话,再执行一次单旋转将s上升到根结点位置.“展开”的结果使得访问最频繁的结点靠近树结构的根部,从而减少访问代价.
splaying(g,p,s){ //g 是 p 的父结点，p 是 s 的父结点。算法将 s 移到根结点位置 while(s 不是树的根结点)if(s 的父结点是根结点) 进行单旋转，将 s 调整为根结点 elseif(s 与它的前驱 p,g 是同构形状) 进行一字形双旋转，将 s 上移 else //s 与它的前驱 p,g 是异构形状 进行之字形双旋转，将 s 上移 };伸展树并不要求每一个操作都是高效的,但是对于一个有n个结点的树结构,并执行m次操作的情形,可能一次插入或搜索操作需要花费O(n)时间,当m>=n时,所有m个操作总共需要 O ( m log 2 n ) O(m \log_2 n) O(mlog2n)时间,从而使每次访问操作所花费的平均时间达到 O ( log 2 n ) O(\log_2 n) O(log2n)从整体上保持较高的时间性能.证明伸展树实能够保证达到 O ( m log 2 n ) O(m \log_2 n) O(mlog2n)的时间复杂性已经超出小编所知道的范围,详细的讨论请参考 Adam Drozdek 的Data Structures and Algorithms in C++ (Second Edition).
图7.29 描述了伸展树是如何通过“展开”实现自调整的.首先在伸展树中搜索70,搜索过程与二叉搜索树完全一样,一旦搜索成功,就执行“展开”过程将该结点上移到根结点位置.
伸展树的插入操作与二叉搜索树相同,但结点一经插入之后立即展开到根结点.同样,从伸展树中删除一个结点的操作也与二叉搜索树相同,但需要把被删结点的父结点展开到根结点.伸展树与AVL树在操作上稍有不同.伸展树的调整与结点被访问(包括搜索、插入、删除)的频率有关,能够进行更合理的调整.而AVL树的结构调整只与插入、删除的顺序有关,与访问的频率无关.
2.红⿊树介绍
2.1红⿊树的概念
红⿊树是⼀棵⼆叉搜索树,它的每个结点增加⼀个存储位来表示结点的颜⾊,可以是红⾊或者⿊⾊.通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束,红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍,因⽽是接近平衡的.红黑树是这样的一棵二叉搜索树:树中的每一个结点的颜色不是黑色就是红色.可以把一棵红黑树视为一棵扩充二叉树,用外部结点表示空指针.
2.2红⿊树的性质
①根结点和所有外部结点的颜色是黑色.
②从根结点到外部结点的途中没有连续两个结点的颜色是红色.
③所有从根到外部结点的路径上都有相同数目的黑色结点.
从红黑树中任一结点x出发(不包括结点x),到达一个外部结点的任一路径上的黑结点个数叫做结点x的黑高度,亦称为结点的阶记作bh(x).红黑树的黑高度定义为其根结点的黑高度.
图7.30所示的二叉搜索树就是一棵红黑树.结点旁边的数字为该结点的黑高度.
另一种等价的定义是看结点指针的颜色.从父结点到黑色子女结点的指针为黑色的,从父结点到红色子女结点的指针为红色的.
⓵从内部结点指向外部结点的指针是黑色的.
⓶从根结点到外部结点的途中没有两个连续的红色指针.
⓷所有根到外部结点的路径上都有相同数目的黑色指针.
如果知道指针的颜色,就能推断结点的颜色,反之亦然.图7.31给出用指针颜色表示的红黑树,它与图7.30所示红黑树等价.树中的粗线是黑色指针,细线是红色指针.从指针的颜色和特性1可知,结点20、40、70是红色的,因为指向它们的指针是红色的,其余的结点都是黑色的.此外,从根到外部结点的每条路径上都有2个黑色指针和3个黑色结点(包括根与外部结点),不存在含有两个连续红色结点或指针的路径.
结论1:设从根到外部结点的路径长度(Path Length,PL)为该路径上指针的个数,如果P与Q是红黑树中的两条从根到外部结点的路径,则有:
P L ( P ) ⩽ 2 P L ( Q ) \mathrm{PL}(P) \leqslant 2\mathrm{PL}(Q) PL(P)⩽2PL(Q)
证明:考查任意一棵红黑树.假设根结点的黑高度 bh ( root ) = r \text{bh}(\text{root})=r bh(root)=r.由特性 1 ′ 1' 1′ 可知,每条从根结点到外部结点的路径中最后一个指针为黑色;从特性 2 ′ 2' 2′ 可知,不存在有连续两个红色指针的路径.因此,每个红色指针后面都会跟随一个黑色指针,从而每条从根到外部结点的路径上都有 r ∼ 2 r r \sim 2r r∼2r 个指针,综上所述,有 P L ( P ) ⩽ 2 P L ( Q ) \mathrm{PL}(P) \leqslant 2\mathrm{PL}(Q) PL(P)⩽2PL(Q).参看图7.31,从根到 40 左下的外部结点的路径长度 P L ( 40 ) = 4 \mathrm{PL}(40) = 4 PL(40)=4,从根到 70 右下的外部结点的路径长度 P L ( 70 ) = 3 \mathrm{PL}(70) = 3 PL(70)=3,因此 P L ( 40 ) ⩽ P L ( 70 ) \mathrm{PL}(40) \leqslant \mathrm{PL}(70) PL(40)⩽PL(70) 或者 P L ( 70 ) ⩽ P L ( 40 ) \mathrm{PL}(70) \leqslant \mathrm{PL}(40) PL(70)⩽PL(40).
结论2:设 h h h 是一棵红黑树的高度(不包括外部结点), n n n 是树中内部结点的个数, r r r 是根结点的黑高度,则以下关系式成立:
(1) h ⩽ 2 r h \leqslant 2r h⩽2r
(2) n ⩾ 2 r − 1 n \geqslant 2^r - 1 n⩾2r−1
(3) h ⩽ 2 log 2 ( n + 1 ) h \leqslant 2\log_2(n+1) h⩽2log2(n+1)
证明：
(1)从结论1的证明可知,从根到任一外部结点的路径长度不超过 2 r 2r 2r,同时从树的定义可知,树的高度即为根结点的高度,等于从根到离根最远的外部结点的路径的长度,因此有 h ⩽ 2 r h \leqslant 2r h⩽2r.例如,在图 7.31 中红黑树的高度(不计外部结点)为 2 r = 4 2r = 4 2r=4.
(2)因为红黑树的黑高度为 r r r,则从树的第1层到第 r r r 层没有外部结点,因而在这些层中有 2 r − 1 2^r - 1 2r−1个内部结点,就是说,内部结点的总数至少为 2 r − 1 2^r - 1 2r−1.例如,在图 7.31 所示的红黑树中,树的黑高度为 r = 2 r=2 r=2,第1层和第2层共有 2 2 − 1 = 3 2^2 - 1 = 3 22−1=3 个内部结点,而在第3层和第4层还有4个内部结点,则有 n ⩾ 2 r − 1 n \geqslant 2^r - 1 n⩾2r−1.
(3)由(2)可得 r ⩽ log 2 ( n + 1 ) r \leqslant \log_2(n+1) r⩽log2(n+1),结合(1),有 h ⩽ 2 log 2 ( n + 1 ) h \leqslant 2\log_2(n+1) h⩽2log2(n+1).
由于红黑树的高度最大为 2 log 2 ( n + 1 ) 2\log_2(n+1) 2log2(n+1),所以,搜索、插入、删除操作的时间复杂性为 O ( log 2 n ) O(\log_2 n) O(log2n).注意,最差情况下的红黑树的高度大于最差情况下具有相同结点个数的 AVL 树的高度)近似于 1.44 log 2 ( n + 2 ) 1.44\log_2(n+2) 1.44log2(n+2)).
红黑树继承了二叉搜索树的定义,一些数据成员和成员函数可以直接使用二叉搜索树的成员.
《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是⿊⾊的规则.它这⾥所指的叶⼦结点不是传统的意义上的叶⼦结点,⽽是我们说的空结点,有些书籍上也把NIL叫做外部结点.NIL是为了⽅便准确的标识出所有路径,《算法导论》在后续实现的细节中也忽略了NIL结点,所以我们知道⼀下这个概念即可.我们通过图片形象理解一下
2.3红⿊树如何确保最⻓路径不超过最短路径的2倍的?
1️⃣从根到NULL结点的每条路径都有相同数量的⿊⾊结点,所以极端场景下,最短路径就就是全是⿊⾊结点的路径,假设最短路径⻓度为bh(black height).
2️⃣由性质2和性质3可知,任意⼀条路径不会有连续的红⾊结点,所以极端场景下,最⻓的路径就是⼀⿊⼀红间隔组成,那么最⻓路径的⻓度为2bh.
3️⃣综合红⿊树的性质⽽⾔,理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的.假设任意⼀条从根到NULL结点路径的⻓度为x,那么bh <= h <= 2bh.
2.4红⿊树的效率
假设N是红⿊树树中结点数量,h最短路径的⻓度,那么,由此推出,也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径,那么2h − 1 <= N < 22∗h − 1.由此推出h ≈ logN 也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径,那么时间复杂度还是O(logN).
红⿊树的表达相对AVL树要抽象⼀些,AVL树通过⾼度差直观的控制了平衡.红⿊树通过性质的颜⾊约束,间接的实现了近似平衡,他们效率都是同⼀档次,但是相对⽽⾔,插⼊相同数量的结点,红⿊树的旋转次数是更少的,因为它对平衡的控制没那么严格.
3.红⿊树的实现
3.1红⿊树的结构
//RBTree.h#pragmaonce// 枚举值表示颜色enumColour{ RED, BLACK };// 这里我们默认按key/value结构实现template<classK,classV>structRBTreeNode{// 这里更新控制平衡也要加入parent指针 pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<classK,classV>classRBTree{typedef RBTreeNode<K, V> Node;public:boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv); _root->_col = BLACK;returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(kv); cur->_col = RED;if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(grandfather->_left == parent){ Node* uncle = grandfather->_right;// 叔叔存在且为红->变色if(uncle && uncle->_col == RED){ parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;// 继续往上处理 cur = grandfather; parent = cur->_parent;}else// 叔叔不存在，或者叔叔存在且为黑->旋转+变色{if(cur == parent->_left){// g// p u//c // 右单旋RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// p u// c // 左右单旋RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else// grandfather->_right == parent{// g// u p Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续往上处理 cur = grandfather; parent = cur->_parent;}else// 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色// g// u p// cif(cur == parent->_right){RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}} _root->_col = BLACK;returntrue;}voidInOrder(){_InOrder(_root); cout << endl;}boolIsBalance(){if(_root ==nullptr)returntrue;if(_root->_col == RED)returnfalse;// 黑色节点数量参考值 Node* leftMost = _root;int blackRef =0;while(leftMost){if(leftMost->_col == BLACK)++blackRef; leftMost = leftMost->_left;}returnCheck(_root,0, blackRef);}intHeight(){return_Height(_root);}intSize(){return_Size(_root);} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}private:int_Size(Node* root){return root ==nullptr?0:_Size(root->_left)+_Size(root->_right)+1;}int_Height(Node* root){if(root ==nullptr)return0;int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}boolCheck(Node* cur,int blackNum,constint blackNumRef){if(cur ==nullptr){if(blackNum != blackNumRef){ cout <<"黑色节点的数量不相等"<< endl;returnfalse;}returntrue;}if(cur->_col == RED && cur->_parent && cur->_parent->_col == RED){ cout << cur->_kv.first <<"->"<<"连续的红色节点"<< endl;returnfalse;}if(cur->_col == BLACK)++blackNum;returnCheck(cur->_left, blackNum, blackNumRef)&&Check(cur->_right, blackNum, blackNumRef);}void_InOrder(Node* root){if(root ==nullptr)return;_InOrder(root->_left); cout << root->_kv.first <<" ";//cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(parent == _root){ _root = subL; subL->_parent =nullptr;}else{if(parentParent->_left == parent){ parentParent->_left = subL;}else{ parentParent->_right = subL;} subL->_parent = parentParent;}}voidRotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;if(subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR;if(parent == _root){ _root = subR; subR->_parent =nullptr;}else{if(parentParent->_left == parent){ parentParent->_left = subR;}else{ parentParent->_right = subR;} subR->_parent = parentParent;}}private: Node* _root =nullptr;};#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<vector>usingnamespace std;#include"RBTree.h"voidTestRBTree1(){ RBTree<int,int> t;// 常规的测试用例//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例int a[]={4,2,6,1,3,5,15,7,16,14};for(auto e : a){if(e ==14){int x =0;} t.Insert({ e, e });//t.InOrder();//cout << "Insert:" << e << "->" << t.IsBalanceTree() << endl;} t.InOrder(); cout << t.IsBalance()<< endl;}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等voidTestRBTree2(){constint N =1000000; vector<int> v; v.reserve(N);srand(time(0));for(size_t i =0; i < N; i++){ v.push_back(rand()+ i);} size_t begin2 =clock(); RBTree<int,int> t;for(auto e : v){ t.Insert(make_pair(e, e));} size_t end2 =clock(); cout <<"Insert:"<< end2 - begin2 << endl; cout << t.IsBalance()<< endl; cout <<"Height:"<< t.Height()<< endl; cout <<"Size:"<< t.Size()<< endl; size_t begin1 =clock();// 确定在的值/*for (auto e : v) { t.Find(e); }*/// 随机值for(size_t i =0; i < N; i++){ t.Find((rand()+ i));} size_t end1 =clock(); cout <<"Find:"<< end1 - begin1 << endl;}intmain(){TestRBTree2();return0;}3.2红黑树的搜索
由于每一棵红黑树都是二叉搜索树,可以使用与搜索普通二叉搜索树时所使用的完全相同的算法进行搜索.在搜索过程中不需使用颜色信息.对普通二叉搜索树进行搜索的时间复杂性为O(h),对于红黑树则为 O ( log 2 n ) O(\log_2 n) O(log2n)因为在搜索普通二叉搜索树、AVL 树和红黑树时使用了相同的代码,并且在最差情况下 AVL 树的高度最小,因此,在那些以搜索操作为主的应用程序中,最差情况下 AVL 树能获得最优的时间复杂性.
3.3红⿊树的插⼊
1️⃣插⼊⼀个值按⼆叉搜索树规则进⾏插⼊,插⼊后我们只需要观察是否符合红⿊树的性质.
2️⃣如果是空树插⼊,新增结点是⿊⾊结点.如果是⾮空树插⼊,新增结点必须红⾊结点,因为⾮空树插⼊,新增⿊⾊结点就破坏了性质是很难维护的.
3️⃣⾮空树插⼊后,新增结点必须红⾊结点,如果⽗亲结点是⿊⾊的,则没有违反任何性质,插⼊结束.
4️⃣⾮空树插⼊后,新增结点必须红⾊结点,如果⽗亲结点是红⾊的,则违反性质.进⼀步分析,c是红⾊,p为红,g必为⿊,这三个颜⾊都固定了,关键的变化看u的情况,需要根据u分为以下⼏种情况分别处理.
说明:下图中假设我们把新增结点标识为c (cur),c的⽗亲标识为p(parent),p的⽗亲标识为g(grandfather),p的兄弟标识为u(uncle).
①情况1:变⾊
c为红,p为红,g为⿊,u存在且为红,则将p和u变⿊,g变红.在把g当做新的c,继续往上更新.
分析:因为p和u都是红⾊,g是⿊⾊,把p和u变⿊,左边⼦树路径各增加⼀个⿊⾊结点,g再变红,相当于保持g所在⼦树的⿊⾊结点的数量不变,同时解决了c和p连续红⾊结点的问题,需要继续往上更新是因为,g是红⾊,如果g的⽗亲还是红⾊,那么就还需要继续处理;如果g的⽗亲是⿊⾊,则处理结束了;如果g就是整棵树的根,再把g变回⿊⾊.情况1只变⾊,不旋转.所以⽆论c是p的左还是右,p是g的左还是右,都是上⾯的变⾊处理⽅式.图0:
❶跟AVL树类似,图0展示了⼀种具体情况,但是实际中需要这样处理的有很多种情况.
❷图1将以上类似的处理进⾏了抽象表达,d/e/f代表每条路径拥有hb个⿊⾊结点的⼦树,a/b代表每条路径拥有hb-1个⿊⾊结点的根为红的⼦树,hb>=0.
❸图2/图3/图4,分别展示了hb = 0/hb = 1/hb= 2的具体情况组合分析,当hb等于2时,这⾥组合情况上百亿种,这些样例是帮助我们理解,不论情况多少种,多么复杂,处理⽅式⼀样的,变⾊再继续往上处理即可,所以我们只需要看抽象图即可.图1:图2:图3:图4:
②情况2:单旋+变⾊
c为红,p为红,g为⿊,u不存在或者u存在且为⿊,u不存在,则c⼀定是新增结点,u存在且为⿊,则c⼀定不是新增,c之前是⿊⾊的,是在c的⼦树中插⼊,符合情况1,变⾊将c从⿊⾊变成红⾊,更新上来的.
分析:p必须变⿊,才能解决,连续红⾊结点的问题,u不存在或者是⿊⾊的,这⾥单纯的变⾊⽆法解决问题,需要旋转+变⾊.
如果p是g的左,c是p的左,那么以g为旋转点进⾏右单旋,再把p变⿊,g变红即可.p变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为p的⽗亲是⿊⾊还是红⾊或者空都不违反性质.
如果p是g的右,c是p的右,那么以g为旋转点进⾏左单旋,再把p变⿊,g变红即可.p变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为p的⽗亲是⿊⾊还是红⾊或者空都不违反性质.
③情况3:双旋+变⾊
c为红,p为红,g为⿊,u不存在或者u存在且为⿊,u不存在,则c⼀定是新增结点,u存在且为⿊,则c⼀定不是新增,c之前是⿊⾊的,是在c的⼦树中插⼊,符合情况1,变⾊将c从⿊⾊变成红⾊,更新上来的.
分析:p必须变⿊,才能解决,连续红⾊结点的问题,u不存在或者是⿊⾊的,这⾥单纯的变⾊⽆法解决问题,需要旋转+变⾊.
如果p是g的左,c是p的右,那么先以p为旋转点进⾏左单旋,再以g为旋转点进⾏右单旋,再把c变⿊,g变红即可.c变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为c的⽗亲是⿊⾊还是红⾊或者空都不违反性质.
如果p是g的右,c是p的左,那么先以p为旋转点进⾏右单旋,再以g为旋转点进⾏左单旋,再把c变⿊,g变红即可.c变成课这颗树新的根,这样⼦树⿊⾊结点的数量不变,没有连续的红⾊结点了,且不需要往上更新,因为c的⽗亲是⿊⾊还是红⾊或者空都不违反性质.
3.4红⿊树的插⼊代码实现
// 旋转代码的实现跟AVL树是⼀样的，只是不需要更新平衡因⼦boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv); _root->_col = BLACK;returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(kv);// 新增结点。颜⾊红⾊给红⾊ cur->_col = RED;if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;// g// p uif(parent == grandfather->_left){ Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){// u存在且为红 -》变⾊再继续往上处理 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{// u存在且为⿊或不存在 -》旋转+变⾊if(cur == parent->_left){// g// p u//c//单旋RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// p u// c//双旋RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else{// g// u p Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变⾊即可if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续往上处理 cur = grandfather; parent = cur->_parent;}else// 叔叔不存在，或者存在且为⿊{// 情况⼆：叔叔不存在或者存在且为⿊// 旋转+变⾊// g// u p// cif(cur == parent->_right){RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}} _root->_col = BLACK;returntrue;}3.5红⿊树的查找
//按⼆叉搜索树逻辑实现即可,搜索效率为O(logN) Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}3.6红⿊树的验证
这⾥获取最⻓路径和最短路径,检查最⻓路径不超过最短路径的2倍是不可⾏的,因为就算满⾜这个条
件,红⿊树也可能颜⾊不满⾜性质,当前暂时没出问题,后续继续插⼊还是会出问题的.所以我们还
是去检查性质,满⾜这些性质,⼀定能保证最⻓路径不超过最短路径的2倍.
1️⃣枚举颜⾊类型,天然实现保证了颜⾊不是⿊⾊就是红⾊.
2️⃣直接检查根即可.
3️⃣前序遍历检查,遇到红⾊结点查孩⼦不太⽅便,因为孩⼦有两个,且不⼀定存在,反过来检查⽗亲的颜⾊就⽅便多了.
4️⃣前序遍历,遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量),前序遍历遇到⿊⾊结点就++blackNum,⾛到空就计算出了⼀条路径的⿊⾊结点数量.再任意⼀条路径⿊⾊结点数量作为参考值,依次⽐较即可.
boolCheck(Node* root,int blackNum,constint refNum){if(root ==nullptr){// 前序遍历⾛到空时，意味着⼀条路径⾛完了//cout << blackNum << endl;if(refNum != blackNum){ cout <<"存在⿊⾊结点的数量不相等的路径"<< endl;returnfalse;}returntrue;}// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了if(root->_col == RED && root->_parent->_col == RED){ cout << root->_kv.first <<"存在连续的红⾊结点"<< endl;returnfalse;}if(root->_col == BLACK){ blackNum++;}returnCheck(root->_left, blackNum, refNum)&&Check(root->_right, blackNum, refNum);}boolIsBalance(){if(_root ==nullptr)returntrue;if(_root->_col == RED)returnfalse;// 参考值int refNum =0; Node* cur = _root;while(cur){if(cur->_col == BLACK){++refNum;} cur = cur->_left;}returnCheck(_root,0, refNum);}3.7红⿊树的删除
红黑树的删除算法与二叉搜索树的删除算法类似,不同之处在于,在红黑树中执行一次二叉搜索树的删除运算,可能会破坏红黑树的特性,需要重新平衡.
在红黑树中真正删除的结点应是叶结点或只有一个子女的结点.若设被删除为p,其唯一的子女为s.结点p被删除后,结点s取代了它的位置.
如果被删结点p是红色的,删去它不存在问题.因为树中各结点的黑高度都没有改变,也不会出现连续两个红色结点,红黑树的特性仍然保持,不需执行重新平衡过程.
如果被删结点p是黑色的,一旦删去它,红黑树将不满足性质3的要求,因为在这条路径上黑色结点少了一个,从根到外部结点的黑高度将会降低.为此,可以将结点u看成具有额外的一重黑色,这样,任意包含结点u的路径上的黑高度仍保持删除前的值,就能恢复红黑树的特性.问题是在红黑树的定义中没有包括双重黑色的结点,因此必须通过旋转变换和改变结点的颜色,消除双重黑色结点,恢复红黑树的特性.
设u是被删结点p的唯一的子女结点.如果u是红色结点,可以把结点u染成黑色,从而恢复红黑树的特性.如果被删结点p是黑色结点,它的唯一的子女结点u也是黑色结点,就必须先将结点p摘下,将结点u链到其祖父结点g的下面.假设结点u成为结点g的右子女,v是u的左兄弟.根据v的颜色,分以下两种情况讨论:
情况1:结点v是黑色结点,若设结点v的左子女结点为w.根据w的颜色又需分两种情况讨论:
(1)结点w是红色结点,此时作一次右单旋转,将w、g染成黑色,v染成红色,如图7.35 所示,就可消除结点u的双重黑色,恢复红黑树的性质.
(2)结点w是黑色结点,还要看结点w的右兄弟结点r.根据结点r的颜色,又要分两种情况:
①结点r是红色结点,可通过一次先左后右的双旋转,并将g染成黑色,就可消除结点u的双重黑色,恢复红黑树的特性,参看图7.36.
②结点r是黑色结点,这时还要看结点g的颜色.如果g是红色结点,只要交换结点g和其子女结点v的颜色就能恢复红黑树的特性,参看图7.37(a).如果g是黑色结点,可做一次右单旋转,将结点v上升并染成双重黑色,从而消除结点u的双重黑色,将双重黑色结点向根的方向转移,如图7.37(b)所示.
情况2:结点v是红色结点.考查v的右子女结点r.根据红黑树的性质2,r一定是黑色结点.再看结点r的左子女结点s.根据s的颜色,可以分为两种情况讨论.
(1)结点s是红色结点.通过一次先左后右双旋转,让r上升,使包含u的路径的黑高度增1,从而消除结点u 的双重黑色,恢复红黑树的特性.参看图7.38.
(2)结点s是黑色结点,再看结点s的右兄弟结点t.根据结点t的颜色又可分为两种情况进行讨论.
①若结点t为红色结点,先以t为旋转轴,做左单旋转,以t替补r的位置;然后再以t为旋转轴,做一次先左后右的双旋转,可消除结点u的双重黑色,恢复红黑树的特性,如图7.39 所示.
②若结点t为黑色结点,以v为旋转轴,做一次右单旋转,并改变v和r的颜色,即可消除结点u的双重黑色,恢复红黑树的特色.参看图7.40.
当结点u是结点g的左子女的情况与上面讨论的情况是镜像的,只要左、右指针互换就可以了.
3.8红黑树模拟实现
#include<iostream>#include<algorithm>usingnamespace std;// 颜色枚举enumColor{ RED, BLACK };// 红黑树节点结构template<typenameK,typenameV>structRBNode{ K key;// 键（用于排序） V value;// 值 Color color;// 节点颜色 RBNode* parent;// 父节点 RBNode* left;// 左孩子 RBNode* right;// 右孩子// 构造函数RBNode(const K& k,const V& v, Color c = RED):key(k),value(v),color(c),parent(nullptr),left(nullptr),right(nullptr){}};// 红黑树类template<typenameK,typenameV>classRBTree{private:using Node = RBNode<K, V>; Node* root;// 根节点 Node* nil;// 哨兵节点（代替NULL，简化边界处理）// 左旋voidleft_rotate(Node* x){ Node* y = x->right;// y是x的右孩子 x->right = y->left;// 将y的左子树挂到x的右子树if(y->left != nil){ y->left->parent = x;// y左子树的父节点改为x} y->parent = x->parent;// y的父节点继承x的父节点if(x->parent == nil){// x是根节点 root = y;}elseif(x == x->parent->left){// x是父节点的左孩子 x->parent->left = y;}else{// x是父节点的右孩子 x->parent->right = y;} y->left = x;// x成为y的左孩子 x->parent = y;// x的父节点改为y}// 右旋voidright_rotate(Node* y){ Node* x = y->left;// x是y的左孩子 y->left = x->right;// 将x的右子树挂到y的左子树if(x->right != nil){ x->right->parent = y;// x右子树的父节点改为y} x->parent = y->parent;// x的父节点继承y的父节点if(y->parent == nil){// y是根节点 root = x;}elseif(y == y->parent->left){// y是父节点的左孩子 y->parent->left = x;}else{// y是父节点的右孩子 y->parent->right = x;} x->right = y;// y成为x的右孩子 y->parent = x;// y的父节点改为x}// 插入后修复红黑树性质voidinsert_fixup(Node* z){// 当父节点是红色时，才需要修复（违反“无连续红节点”）while(z->parent->color == RED){if(z->parent == z->parent->parent->left){// 父节点是祖父的左孩子 Node* uncle = z->parent->parent->right;// 叔父节点（祖父的右孩子）// 情况1：叔父节点是红色 → 仅需变色if(uncle->color == RED){ z->parent->color = BLACK;// 父节点变黑 uncle->color = BLACK;// 叔父节点变黑 z->parent->parent->color = RED;// 祖父节点变红 z = z->parent->parent;// 向上继续检查}else{// 情况2：叔父是黑色，且当前节点是父节点的右孩子 → 先左旋转为情况3if(z == z->parent->right){ z = z->parent;left_rotate(z);}// 情况3：叔父是黑色，且当前节点是父节点的左孩子 → 右旋+变色 z->parent->color = BLACK; z->parent->parent->color = RED;right_rotate(z->parent->parent);}}else{// 父节点是祖父的右孩子（对称逻辑） Node* uncle = z->parent->parent->left;if(uncle->color == RED){ z->parent->color = BLACK; uncle->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent;}else{if(z == z->parent->left){ z = z->parent;right_rotate(z);} z->parent->color = BLACK; z->parent->parent->color = RED;left_rotate(z->parent->parent);}}} root->color = BLACK;// 确保根节点始终是黑色}// 二叉搜索树插入逻辑（纯BST插入） Node*bst_insert(const K& key,const V& value){ Node* parent = nil; Node* curr = root;// 找到插入位置while(curr != nil){ parent = curr;if(key < curr->key){ curr = curr->left;}elseif(key > curr->key){ curr = curr->right;}else{// 键已存在，更新值并返回原节点 curr->value = value;return curr;}}// 创建新节点（默认红色) Node* new_node =newNode(key, value, RED); new_node->parent = parent; new_node->left = nil; new_node->right = nil;// 挂到父节点的对应位置if(parent == nil){ root = new_node;// 空树，新节点为根}elseif(key < parent->key){ parent->left = new_node;}else{ parent->right = new_node;}return new_node;}// 中序遍历voidinorder_traversal(Node* node)const{if(node == nil)return;inorder_traversal(node->left); cout <<"["<< node->key <<":"<< node->value <<","<<(node->color == RED ?"红":"黑")<<"] ";inorder_traversal(node->right);}public:// 构造函数：初始化哨兵节点和根节点RBTree(){ nil =newNode(K(),V(), BLACK);// 哨兵节点固定为黑色 root = nil;}// 析构函数~RBTree(){// 此处可补充递归删除所有节点的逻辑，避免内存泄漏delete nil;}// 插入接口voidinsert(const K& key,const V& value){ Node* new_node =bst_insert(key, value);if(new_node->color == RED){// 仅新节点是红色时需要修复insert_fixup(new_node);}}// 中序遍历接口voidinorder()const{inorder_traversal(root); cout << endl;}// 查找节点 Node*find(const K& key)const{ Node* curr = root;while(curr != nil){if(key < curr->key){ curr = curr->left;}elseif(key > curr->key){ curr = curr->right;}else{return curr;}}returnnullptr;// 未找到}};intmain(){// 1. 创建红黑树 RBTree<int, string> rb_tree;// 2. 插入测试数据 rb_tree.insert(10,"A"); rb_tree.insert(20,"B"); rb_tree.insert(30,"C"); rb_tree.insert(15,"D"); rb_tree.insert(25,"E"); rb_tree.insert(5,"F");// 3. 中序遍历（验证有序+颜色） cout <<"红黑树中序遍历（键值:颜色）："<< endl; rb_tree.inorder();auto node = rb_tree.find(15);if(node){ cout <<"\n查找键15：值="<< node->value <<"，颜色="<<(node->color == RED ?"红":"黑")<< endl;}return0;}4.相关OJ题
4.1二叉搜索树中的插入操作
classSolution{public: TreeNode*insertIntoBST(TreeNode* root,int val){// 若根节点为空，直接返回新节点if(root ==nullptr){returnnewTreeNode(val);} TreeNode* cur = root;while(cur !=nullptr){if(val < cur->val){// 左子树为空，直接插入新节点if(cur->left ==nullptr){ cur->left =newTreeNode(val);break;}// 否则继续遍历左子树else{ cur = cur->left;}}else{// 右子树为空，直接插入新节点if(cur->right ==nullptr){ cur->right =newTreeNode(val);break;}// 否则继续遍历右子树else{ cur = cur->right;}}}return root;}};4.2将二叉搜索树变平衡
classSolution{private:// 中序遍历，将BST转换为升序数组voidinorder(TreeNode* root, vector<int>& nums){if(root ==nullptr)return;inorder(root->left, nums); nums.push_back(root->val);inorder(root->right, nums);}// 从有序数组的[start, end]区间构建平衡BST TreeNode*build(const vector<int>& nums,int start,int end){if(start > end)returnnullptr;// 选择中间元素作为根，避免栈溢出int mid = start +(end - start)/2; TreeNode* node =newTreeNode(nums[mid]);// 递归构建左右子树 node->left =build(nums, start, mid -1); node->right =build(nums, mid +1, end);return node;}public: TreeNode*balanceBST(TreeNode* root){ vector<int> nums;inorder(root, nums);// 步骤1：中序遍历得到有序数组returnbuild(nums,0, nums.size()-1);// 步骤2：重构平衡BST}};4.3判断是否为平衡二叉树
classSolution{private:// 辅助函数：返回以当前节点为根的子树高度，若子树不平衡则返回 -1intgetHeight(TreeNode* node){if(node ==nullptr){return0;// 空节点高度为 0}// 递归计算左子树高度，若左子树不平衡，直接返回 -1int leftHeight =getHeight(node->left);if(leftHeight ==-1){return-1;}// 递归计算右子树高度，若右子树不平衡，直接返回 -1int rightHeight =getHeight(node->right);if(rightHeight ==-1){return-1;}// 若当前节点左右子树高度差 > 1，说明不平衡，返回 -1if(abs(leftHeight - rightHeight)>1){return-1;}// 否则返回当前节点的高度（左右子树最大高度 +1）returnmax(leftHeight, rightHeight)+1;}public:boolisBalanced(TreeNode* root){// 若辅助函数返回值不为 -1，说明树是平衡的returngetHeight(root)!=-1;}};4.4二叉搜索树迭代器
classBSTIterator{private: vector<int> inorderList;int idx;// 中序遍历，将节点值存入数组voidinorder(TreeNode* node){if(node ==nullptr)return;inorder(node->left); inorderList.push_back(node->val);inorder(node->right);}public:BSTIterator(TreeNode* root){inorder(root); idx =0;// 指针初始化为数组起始位置}intnext(){return inorderList[idx++];}boolhasNext(){return idx < inorderList.size();}};4.5二叉树中的最大路径和
classSolution{private:// 辅助函数：返回当前节点能向父节点提供的最大贡献，同时更新全局最大路径和inthelper(TreeNode* node,int& maxSum){if(node ==nullptr){return0;// 空节点贡献为0}// 计算左右子树的最大贡献，若为负则取0（剪枝）int leftContribution =max(helper(node->left, maxSum),0);int rightContribution =max(helper(node->right, maxSum),0);// 以当前节点为最高点的路径和，更新全局最大值int currentPathSum = node->val + leftContribution + rightContribution; maxSum =max(maxSum, currentPathSum);// 返回当前节点向父节点的最大贡献（只能选左或右子树）return node->val +max(leftContribution, rightContribution);}public:intmaxPathSum(TreeNode* root){int maxSum = INT_MIN;// 初始化为极小值，应对全负数的情况helper(root, maxSum);return maxSum;}};敬请期待下一篇文章内容–>C++封装红⿊树实现mymap和myset!
每日心灵鸡汤:向阳而生!
只有足够的努力,才会足够幸运.想要得到这世上最好的东西,得先让世界看到最好的你.你不一定要逆风翻盘,但一定要向阳而生.努力上很难,但永远要记住,如果不努力,就会一直很难.希望我们不要沉溺在安逸里得过且过,能给你遮风挡雨的屋檐,同样也会让你不见天日.只有你自己强大了才能不惧风雨,自己撑起一片天空.没有谁的幸运是凭空而来的,所谓的好运不过是机会遇到努力的你!
