C++ 红黑树

红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。请在阅读前文的AVL树相关文章之后学习红黑树C AVLTree-CSDN博客1.红黑树及其基本规则1.1 基础规则1.每个结点不是红色就是黑色2.根节点是黑色的3.如果一个节点是红色的则它的两个孩子结点是黑色的4.对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点)对于规则3可以理解为一条路径中没有连续的红色节点。对于规则4可以理解为每条路径黑色节点数量相等。从规则中我们也可以看出AVL树严格平衡能保证所有的分支之间高度差小于1红黑树近似平衡最长路径不会超过最长路径的两倍。因为红色不能连续所以最短情况全黑最长情况一黑一红并且黑色数量都是一样的所以最长的就是比最短的多一倍节点。最长和最多只是理想状态每一棵树不一定有最长的也不一定有最短的。第五点也叫NIL(nullptr)节点其实不考虑NIL节点也可以。NIL节点主要便于计数路径数比如上图有11个NIL节点就有11个路径。1.2 红黑树和AVL树的查找效率前文说到AVL高度差不会超过1红黑是高度不差过一倍。所以只讨论find函数AVL树肯定更快但是对于红黑树最短路径LogN 最长路径2*LogN所以其时间复杂度其实都是O(LogN)并且因为LogN足够小所以对cpu的运算速度来说LogN和2*LogN没区别。因此可以认为红黑树与AVL树的效率是差距不大的。反而在插入和删除元素时红黑树更有优势调整起来没有那么麻烦。1.3 红黑树的节点定义enum Color { RED, BLACK }; templatetypename k,typename v struct RBTreeNode { typedef RBTreeNodek, v Node; RBTreeNode(const pairk,v kv make_pair(k(),v())) :_parent(nullptr) ,_left(nullptr) ,_right(nullptr) ,_kv(kv) ,_color(RED) {} Node* _parent; Node* _left; Node* _right; pairk, v _kv; Color _color; }; templatetypename k,typename v class RBTree { public: typedef RBTreeNodek, v Node; private: Node* _root nullptr; };2. 红黑树的插入以此树为例这个情况下要添加节点加红节点还是黑节点呢无论怎样加都会破坏规则。插入一个黑色的会让插入新节点的路径和其他所有路径都一定矛盾黑节点数量变了。插入一个红色的如果是在黑色节点下面插入就无需调整如果在红色节点下面插入红色依然存在问题。插入黑节点一定有问题插入红节点可能有问题所以要插入新节点时我们无脑插入红色节点然后再逐一遍历向上调整。具体调整分析如下红黑树的调整中多通过观察三代子cur 父parent 叔叔uncle 爷爷grandfather不需要调整的一类插入直接在parent下面插入一个红色节点。这是最理想的情况不需要调整。那么我们是否可以把所有需要调整的情况都往这种不需要调整的方向靠拢呢需要调整注意此处看到的所有树都有可能是完整的树或者一棵子树。第一种 parent和uncle都是红色改色最简单的时候 abcde都是空树 也就是说cur是我们插入的第一个节点。解决方法需要将p和u都变黑然后g变红调整完之后如果g是根需要将g改为黑色如果不是根需要检查g和他的_parent节点的颜色关系如果是两个红需要进入新一轮的调整。子树有一个黑色节点时cde可能是x y z中的一种此时要在a或b的下面插入一个节点新增的记做cur 其父节点记作p 父节点因为是红色所以一定还有父节点记作g思路不变父亲和叔叔变黑爷爷变红然后爷爷变cur再往上调整。至于往上调整时是哪种情况需要重新判断。其实不管子树有多少层都可以只看成一种情况。因为我们插入时都是直接插红色而以上都是调整的部分。cur可以作为新增的元素也可以在上一轮中被调整的元素不用纠结子树到底长什么样。第二种 uncle是黑或者不存在旋转改色叔叔不存在的时候不能贸然的把父节点变黑。单纯变黑不能解决问题会改变路径上黑节点的数量旋转解决旋转后注意parent要变黑grandparent要变红,也就是交换了parent和grandparent的颜色。先看单旋的情况curp,g成一条直线并且此处u是空再看双旋的情况双旋旋转一次就能得到单旋的情况。例如需要双旋并且u存在的时候此时abc必定是有黑色节点的这个情况一定是先经过其他调整才得到的因为abc中必然有黑色节点记忆旋转时要让g和c变成p的左右节点所以要让g的颜色变成红色p变成黑色旋转一定会存在单旋或者双旋 由于前文avl树中有详细解释此处不再多介绍。总结遇到连续的红节点关键看叔叔。进一步分析在以上逻辑中每一个插入的节点原本都是红色。如果他是黑色说明这是一个已经经历过调整的节点。3. 代码实现插入后的遍历调整经过上述分析首先parent对应的节点需要是红色才需要我们进一步调整。并且如果parent是红色说明parent一定不是根grandfather一定存在。为了控制高度差我们又没有_bf来作为标志只能先分parent在g的左和右两个大类来讨论然后再 将grandparent的值赋值给cur 然后parent的值变成cur-_parentwhile里面又判断了一下parent是不是为空1、parent为空parent已经不存在了说明cur就是根了出循环之后处理根的颜色即可2、parent存在且为黑。这是最理想的状态不需要再调节直接出循环。3、parent存在且为红进入新一轮的调整循环。此时读者容易有的问题1、为什么先只写uncle为红的情况答因为uncle为红一定是第一个需要调整的情况换句话说这样一个节点中cur不可能是新增节点。否则原来的黑色数量就不对。比如一种会uncle是黑的情况第二轮循环才会遇到uncle是黑。2、出循环之后如何处理根的颜色答直接_root-_colour BLACK;即可因为根节点的颜色变化是唯一一个不会影响“所有路径黑色节点数相等”这一条件的接着实现uncle是黑的情况由AVL树处可知旋转分为单旋和双旋。单纯的一边高如上图是单旋非单纯的需要采用双旋因此我们还要继续判断//uncle 为黑或者不存在(旋转变色) if (cur parent-_left) { // g // p u //c //都是同一边高采用单旋即可 RotateR(grandfather); parent-_color BLACK; grandfather-_color RED; } else { // g // p u // c 采用双旋 RotateL(parent); RotateR(grandfather); cur-_color BLACK; grandfather-_color RED; }并且旋转之后都可以直接Break不用像情况1一样再往上调整。因为旋转之后的颜色改变让我们目前操作的这课子树的“根”变成了黑色没有改变任意路径的黑色节点数量使该子树与调整之前一样并且还解决了新加入的节点。无需往上调节。整体代码while (parent parent-_color RED) { Node* grandfather parent-_parent; if (parent grandfather-_left) { // g // p u Node* uncle grandfather-_right; //叔叔为红改色处理即可 if (uncle uncle-_color RED) { parent-_color uncle-_color BLACK; grandfather-_color RED; cur grandfather; parent cur-_parent;//进入新的一轮循环之后 //如果parent不存在则cur已经到根了 } else { //uncle 为黑或者不存在(旋转变色) if (cur parent-_left) { // g // p u //c //都是同一边高采用单旋即可 RotateR(grandfather); parent-_color BLACK; grandfather-_color RED; } else { // g // p u // c 采用双旋 RotateL(parent); RotateR(grandfather); cur-_color BLACK; grandfather-_color RED; } break; } } else if (parent grandfather-_right) { //与上述同理 } } _root-_color BLACK; return true;旋转逻辑与AVL树同理void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) { subRL-_parent parent; } subR-_left parent; Node* parentParent parent-_parent; parent-_parent subR; if (parentParent nullptr) { this-_root subR; } else { if (parentParent-_left parent) parentParent-_left subR; if (parentParent-_right parent) parentParent-_right subR; } subR-_parent parentParent; } void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) { subLR-_parent parent; } Node* parentParent parent-_parent; parent-_parent subL; subL-_right parent; if (parentParentnullptr) { this-_root subL; } else { if (parentParent-_left parent) parentParent-_left subL; if (parentParent-_right parent) parentParent-_right subL; } subL-_parent parentParent; }实现几个简单接口能坚持到这里并理解红黑树大逻辑的各位应该都能轻松搞定下列接口了吧因为 外部不能掉_root所以包一层。4. 检测红黑树1.中序判断是否是有序的。2.遇到红节点就检查其父亲是否是红判断是否有红色连续。这个不难解决遍历的时候检查就行。3. 黑色节点的数量。遍历每个节点时记下每个节点的到根节点的路径上有多少黑色节点。思路遍历一条路径获得一个基准值。之后每一条路径遇到空的时候都与基准值做比较递归中我们加入一个blackNum 作为形参每一层栈帧中都带上blackNum不需要使用引用或者指针或者容器还可以顺带检查下有无连续红色节点。bool IsBalance() { if (_root nullptr) { return true; } if (_root-_color RED) { return false; } int refnum 0;//作为比较的标准值 Node* pnode _root; while (pnode) { if (pnode-_color BLACK)refnum; pnode pnode-_left; } return check(_root, 0, refnum); } bool check(Node* cur, int BlackNum, const int refnum) { if (cur nullptr) { //如果走到头了 if (BlackNum refnum) { return true; } else { cout 黑色节点数量不一致 endl; return false; } } else { //如果没走到头 if (cur-_color RED) { if (cur-_parent-_color RED) { cout 有连续红色节点 endl; return false; } } else { BlackNum; } } return check(cur-_left, BlackNum, refnum) check(cur-_right, BlackNum, refnum); }效率比较同时拿很多数据插入AVL和RB树RB确实会高一点但是旋转次数也少一点。红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(logN)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。