红黑树实现：概念、插入与验证详解

1. 红黑树的概念红黑树是一棵二叉搜索树它的每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。通过对任何一条从根到叶子路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而接近平衡。1.1 红黑树的规则每个结点不是红色就是黑色。根结点是黑色的。如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点。说明《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。这里的叶子结点不是传统意义上的叶子结点而是我们说的空结点有些书籍上也把NIL叫做外部结点。NIL是为了方便准确地标识出所有路径《算法导论》在后续讲解实现的细节中也忽略了NIL结点所以我们知道一下这个概念即可。1.2 思考一下红黑树如何确保最长路径不超过最短路径的2倍的由规则4可知从根到NULL结点的每条路径都有相同数量的黑色结点所以极端场景下最短路径就是全是黑色结点的路径假设最短路径长度为bh(black height)。由规则2和规则3可知任意一条路径不会有连续的红色结点所以极端场景下最长的路径就是一黑一红间隔组成那么最长路径的长度为2*bh。综合红黑树的4点规则而言理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x那么bh h 2*bh。1.3 红黑树的效率假设N是红黑树树中结点数量h最短路径的长度那么2^h - 1 N 2^(2*h) - 1由此推出h约等于logN也就是意味着红黑树增删查改最坏也就是走最长路径2*logN那么时间复杂度还是O(logN)。红黑树的表达相对AVL树要抽象一些AVL树通过高度差直观地控制了平衡。红黑树通过4条规则的颜色约束间接地实现了近似平衡它们效率都是同一档次但是相对而言插入相同数量的结点红黑树的旋转次数是更少的因为他对平衡的控制没那么严格。2. 红黑树的实现2.1 红黑树的结构// 枚举值表示颜色 enum Colour { RED, BLACK }; // 这里我们默认按key/value结构实现 templateclass K, class V struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 pairK, V _kv; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; Colour _col; RBTreeNode(const pairK, V kv) : _kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} }; templateclass K, class V class RBTree { typedef RBTreeNodeK, V Node; public: private: Node* _root nullptr; };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的左还是右p是g的左还是右都是上面的变色处理方式。2.2.3 情况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的父亲是黑色还是红色或者空都不违反规则。2.2.4 情况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的父亲是黑色还是红色或者空都不违反规则。2.3 红黑树的插入代码实现// 旋转代码的实现跟AVL树是一样的只是不需要更新平衡因子 bool Insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); _root-_col BLACK; return true; } Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; } } cur new Node(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 u if (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 // c if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_col BLACK; return true; }2.4 红黑树的查找按二叉搜索树逻辑实现即可搜索效率为O(logN)。Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_right; } else if (cur-_kv.first key) { cur cur-_left; } else { return cur; } } return nullptr; }2.5 红黑树的验证这里获取最长路径和最短路径检查最长路径不超过最短路径的2倍是不可行的因为就算满足这个条件红黑树也可能颜色不满足规则当前暂时没出问题后续继续插入还是会出问题的。所以我们还是去检查4点规则满足这4点规则一定能保证最长路径不超过最短路径的2倍。规则1枚举颜色类型天然实现保证了颜色不是黑色就是红色。规则2直接检查根即可。规则3前序遍历检查遇到红色结点查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲的颜色就方便多了。规则4前序遍历遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)前序遍历遇到黑色结点就blackNum走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值依次比较即可。bool Check(Node* root, int blackNum, const int refNum) { if (root nullptr) { // 前序遍历走到空时意味着一条路径走完了 // cout blackNum endl; if (refNum ! blackNum) { cout 存在黑色结点的数量不相等的路径 endl; return false; } return true; } // 检查孩子不方便因为孩子有两个且不一定存在反过来检查父亲就方便多了 if (root-_col RED root-_parent-_col RED) { cout root-_kv.first 存在连续的红色结点 endl; return false; } if (root-_col BLACK) { blackNum; } return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum); } bool IsBalance() { if (_root nullptr) return true; if (_root-_col RED) return false; // 参考值 int refNum 0; Node* cur _root; while (cur) { if (cur-_col BLACK) { refNum; } cur cur-_left; } return Check(_root, 0, refNum); }