1.红黑树的概念红黑树是一棵二叉搜索树它的每个结点增加一个存储位来表示结点的颜色可以是红色或黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出 2 倍因而是接近平衡的1.1 红黑树的规则每个结点不是红色就是黑色根节点是黑色的如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点对于任意一个结点从该结点到其所有 NULL 结点的简单路径上均包含相同数量的黑色结点说明《算法导论》等书籍上补充了一条每个叶子结点NIL都是黑色的规则。这里的叶子节点指的不是传统意义上的叶子结点而是空节点有些书籍上也把NIL结点叫做外部结点。NIL结点是为了方便准确的标识出所有路径。1.2 红黑树如何保证最长路径不超过最短路径2倍右规则4可知从根到 NULL 结点的每条路径都有相同数量的黑色结点所以极端场景下最短路径就是全为黑色结点的路径假设最短路径的长度为 bh(black height)由规则2和规则3可知任意一条路径不会有连续的红色结点所以极端场景下最长路径就是一黑一红间隔组成那么最长路径的长度为 2 * bh综合红黑树的四条规则理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到 NULL 结点路径的长度为 h那么 bh h 2 * bh1.3 红黑树的效率假设 N 是红黑树中结点的数量h 为最短路径的长度那么 2^h - 1 N 2^(2h) - 1由此推出 h ≈ logN也就是意味着红黑树增删查改最坏情况下也就是走最长路径 2logN那么时间复杂度还是 O(logN)红黑树的表达相对 AVL 树要抽象一些AVL树通过高度差直观的控制了平衡红黑树通过四条规则的颜色约束间接实现了近似平衡他们的效率是同一档次但是相对而言插入相同数量的结点红黑树的旋转次数更少因为它对平衡的控制没有AVL树严格2.红黑树的实现2.1 红黑树的结构// 枚举值表示颜色enumColor{RED,BLACK};// key/value结构templateclassK,classVstructRBTreeNode{pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Color _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};templateclassK,classVclassRBTree{typedefRBTreeNodeK,VNode;public:// ...private:Node*_rootnullptr;};2.2 红黑树的插入2.2.1 红黑树插入一个值的大概过程插入一个值按二叉搜索树规则进行插入插入后需要观察是否符合红黑树的4条规则如果是空树插入新增结点是黑色结点。如果是非空树插入新增结点必须是红色结点因为非空树插入如果新增黑色结点就破坏了规则4规则4是很难维护的非空树插入后新增结点必须为红色结点如果父亲结点是黑色的则没有违反任何规则插入结束非空树插入后新增结点必须为红色结点如果父亲结点是红色的则违法规则3。如果违反红黑树的规则那么c为红色p一定是红色g一定是黑色这三个颜色是固定的关键看 u 的情况根据 u 的情况可以分为以下几种情况说明新增结点为 c(cur)c 的父亲结点为 p(parent)p 的父亲结点为 g(grandfather)p 的兄弟结点为 u(uncle)2.2.2 情况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 的左孩子还是右孩子都是一样的变色处理方式。2.2.3 情况2单旋变色c 为红p 为红g 为黑u 不存在或u存在且为黑。若u不存在则c一定是新增结点u存在且为黑则c一定不是新增c 之前是黑色的是在 c 的子树中插入符合情况1变色将 c 从黑色变成红色更新上来的。分析p 必须变黑才能解决连续红色结点的问题。u 不存在或 u 存在且为黑色时单纯变色无法解决问题需要旋转 变色。g p u c如果 p 是 g 的左c 是 p 的左那么以 p 为旋转点进行右单旋再把 p 变黑g 变红即可。p 变成这棵树新的根这样子树的黑色结点数量保持不变没有连续的红色结点了且不需要再往上更新因为 p 的父亲是黑色还是红色都不违反规则g u p c如果 p 是 g 的右c 是 p 的右。那么以 g 为旋转点进行左单旋再把 p 变黑g 变红即可。p 变成这棵树新的根这样子树的黑色结点数量保持不变没有连续的红色结点了且不需要再往上更新因为 p 的父亲是黑色还是红色都不违反规则例如当 bh 1 时2.2.4 情况3双旋变色c 为红p 为红g 为黑u 不存在或u存在且为黑。若u不存在则c一定是新增结点u存在且为黑则c一定不是新增c 之前是黑色的是在 c 的子树中插入符合情况1变色将 c 从黑色变成红色更新上来的。分析p 必须变黑才能解决连续红色结点的问题。u 不存在或 u 存在且为黑色时单纯变色无法解决问题需要旋转 变色。g p u c如果 p 是 g 的左c 是 p 的右那么先以 p 为旋转点进行左单旋再以 g 为旋转点进行右单旋再把 c 变黑g 变红即可。c 变成这棵树新的根这样子树的黑色结点数量保持不变没有连续的红色结点了且不需要再往上更新因为 p 的父亲是黑色还是红色都不违反规则g u p c如果 p 是 g 的右c 是 p 的右。那么先以 p 为旋转点进行右单旋再以 g 为旋转点进行左单旋再把 c 变黑g 变红即可。p 变成这棵树新的根这样子树的黑色结点数量保持不变没有连续的红色结点了且不需要再往上更新因为 p 的父亲是黑色还是红色都不违反规则例如当 bh 1 时2.3 红黑树的插入代码实现红黑树插入时的旋转逻辑和AVL树是一样的只是不需要更新平衡因子右旋和左旋voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;// subLR 连接 parent// subLR 非空时才能更改其 _parentparent-_leftsubLR;if(subLR)subLR-_parentparent;// 记录 parent 的原 parentNode*parentParentparent-_parent;// subL 连接 parentsubL-_rightparent;parent-_parentsubL;// parent 可能是整棵树的根也可能是局部的子树// 如果是整棵树的根要修改 _root// 如果是局部的指针要与上一层连接if(parentParentnullptr){_rootsubL;subL-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubL;}else{parentParent-_rightsubL;}subL-_parentparentParent;}}voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}}插入时双旋可以通过调用两次单旋完成boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);// 新增结点颜色为红色cur-_colRED;if(parent-_kv.firstcur-_kv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;// 父亲节点存在并且为红色出现了连续的红色结点需要处理while(parentparent-_colRED){Node*grandfatherparent-_parent;// g// p u// uncle存在且为右孩子if(parentgrandfather-_left){Node*unclegrandfather-_right;// uncle存在且为红色// 直接修改 parent 和 uncle为黑色grandfather为红色if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;// 继续向上处理curgrandfather;parentcur-_parent;}else{// u存在且为黑或不存在// g// p u// c// LL 右旋变色if(curparent-_left){RotateR(grandfather);parent-_colBLACK;grandfather-_colRED;}else{// g// p u// c// LR 左右双旋RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}else{// g// u p// uncle存在且为左孩子Node*unclegrandfather-_left;// uncle存在且为红色// 直接修改 parent 和 uncle为黑色grandfather为红色if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;// 继续向上处理curgrandfather;parentcur-_parent;}else{// u存在且为黑或不存在// g// u p// c// RR 左旋变色if(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{// g// u p// c// RL 左右双旋RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}// 将根变为黑色赋值代价很小所以无需判断直接赋值即可_root-_colBLACK;returntrue;}2.4 红黑树查找红黑树查找逻辑与二叉搜索树逻辑相同搜索效率为O(logN)Node* Find(const K key) { Node* cur _root; while (cur) { if (key cur-_kv.first) { cur cur-_right; } else if (key cur-_kv.first) { cur cur-_left; } else { return cur; } } return nullptr; }2.5 红黑树的验证规则1枚举颜色类型保证红黑树中只有RED和BLACK两种颜色无需检查规则2直接检查根即可规则3遍历二叉树检查每个红色结点的父亲节点是否为红色规则4前序遍历遍历过程中用形参记录根到当前结点的blackNum黑色结点数量前序遍历遇到黑色结点就blackNum走到空就计算出当前路径的黑色结点数量将黑色结点数量与基准值任意一条路径的黑色结点数量比较即可boolIsBalanceTree(){if(_rootnullptr){returntrue;}if(_root-_colRED){returnfalse;}intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}return_IsBalanceTree(_root,0,refNum);}bool_IsBalanceTree(Node*root,intblackNum,constintrefNum){if(rootnullptr){if(refNum!blackNum){cout存在黑色结点数量不相等的路径endl;returnfalse;}returntrue;}if(root-_colREDroot-_parent-_colRED){cout存在连续红色结点endl;returnfalse;}if(root-_colBLACK){blackNum;}return_IsBalanceTree(root-_left,blackNum,refNum)_IsBalanceTree(root-_right,blackNum,refNum);}