C++进阶6：红黑树原理

目录一、红黑树的概念1.1 红黑树的规则1.2 红黑树如何确保最长路径不超过最短路径的 2 倍1.3 红黑树的效率二、红黑树的实现2.1 红黑树的结构2.2 红黑树的插入2.2.1 红黑树插入一个值的大概过程2.2.2 情况 1变色2.2.3 情况 2单旋 变色2.2.4 情况 2双旋 变色2.4 红黑树的查找2.5 红黑树的验证一、红黑树的概念红黑树Red-Black Tree是一种自平衡的二叉搜索树它通过在插入和删除操作中维护一系列颜色规则确保树的高度始终保持在对数级别从而保证了高效的查找、插入和删除性能。1.1 红黑树的规则一棵红黑树必须满足以下 4 条核心性质每个节点要么是红色要么是黑色。根节点必须是黑色。如果一个节点是红色则它的两个子节点都是黑色即不能有两个连续的红色节点。从任一节点到其所有后代叶子节点的简单路径上均包含相同数量的黑色节点。注意这里的一条路径是从根节点一直走到NULL。1.2 红黑树如何确保最长路径不超过最短路径的 2 倍最短路径全为黑色节点的路径。最长路径红黑交替的路径。根据性质 4红色节点不能连续出现因此最长路径的长度不会超过最短路径的 2 倍。这保证了红黑树的平衡性其时间复杂度稳定在 O (log n)。1.3 红黑树的效率时间复杂度查找、插入、删除操作的平均和最坏时间复杂度均为 O (log n)。空间复杂度O (n)用于存储 n 个节点。与 AVL 树相比红黑树牺牲了部分平衡性换取了更少的旋转操作在频繁插入删除的场景下性能更优。二、红黑树的实现2.1 红黑树的结构在 C 中我们可以用结构体来定义红黑树的节点enum Colour { RED, BLACK }; templateclass K,class V struct RBTreeNode { 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 红黑树插入一个值的大概过程按照二叉搜索树的规则将新节点插入到合适的位置并将其颜色设为红色。(因为所有路径的黑色节点都必须保持一致如果插入的节点是黑色会非常麻烦)检查插入后是否违反了红黑树的性质。如果违反了性质则通过变色和旋转操作进行修复直到所有性质都得到满足。2.2.2 情况 1变色当新节点的父节点和叔叔节点都是红色时将父节点和叔叔节点变为黑色。将祖父节点变为红色。将祖父节点作为新的节点继续向上检查。cur作为新插入的节点这里只是一种概述情况但这种逻辑是只要节点出现这种情况就如此处理但我们需要注意如果我们变化的祖父节点是根节点就违反了红黑树的逻辑所以无论如何变化我们都要加上一句让根节点始终保持黑色。可以有两个连续的根节点2.2.3 情况 2单旋 变色当新节点的父节点是红色叔叔节点是黑色或者不存在。叔叔不存在则c一定是新增结点叔叔存在且为黑则 c一定不是新增c之前是黑色的是在c的⼦树中插入符合情况1变色将c从黑色变成红色更新上来的2.2.4 情况 2双旋 变色当新节点的父节点是红色叔叔节点是黑色或者不存在。叔叔不存在则c一定是新增结点叔叔存在且为黑则 c一定不是新增c之前是黑色的是在c的⼦树中插入符合情况1变色将c从黑色变成红色更新上来的2.3 红黑树的插入代码实现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; if (parent grandfather-_left) { // g // p u Node* uncle grandfather-_right; //情况1 if (uncle uncle-_col RED) { // 变色 parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else { //情况2 if (cur parent-_left) { // g // p u // c RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } else { //情况3 // g // p u // c RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } else { // g // u p Node* uncle grandfather-_left; // 叔叔存在且为红-》变色即可 //情况1 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else // 叔叔不存在或者存在且为黑 { // 情况二叔叔不存在或者存在且为黑 // 旋转变色 // g // u p // c //情况2 if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } //情况3 else { RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_col BLACK; return true; } void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* pParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (pParent-_left parent) { pParent-_left subL; } else { pParent-_right subL; } subL-_parent pParent; } } void RotateL(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 (parentParent nullptr) { _root subR; subR-_parent nullptr; } else { if (parent parentParent-_left) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } }2.4 红黑树的查找红黑树的查找操作与普通二叉搜索树完全一致从根节点开始若查找值小于当前节点则向左子树查找若大于则向右子树查找。直到找到目标值或到达叶子节点NIL 节点。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. 规则1枚举颜色类型天然实现保证了颜色不是黑色就是红色2. 规则2直接检查根即可3. 规则3前序遍历检查遇到红色结点查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲的颜色就方便多了4. 规则4前序遍历遍历过程中用形参记录跟到当前结点的blackNum(黑色节点数量)前序遍历遇到黑色结点就blackNum走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值依次比较即可。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); } private: 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); }