桂林网站建设招聘互联网技术培训机构

桂林网站建设招聘,互联网技术培训机构,天津建设网工程信息网站,网站搭建软件工具目录 红黑树的概念 红黑树的规则 红黑树的效率 红黑树的实现 红黑树的插入 情况1#xff1a;变色 情况2#xff1a;单旋变色 情况2#xff1a;双旋变色 为什么这三种情况能覆盖所有插入场景#xff1f; 步骤 1#xff1a;确定基础前提#xff08;插入前树是合法…目录红黑树的概念红黑树的规则红黑树的效率红黑树的实现红黑树的插入情况1变色情况2单旋变色情况2双旋变色为什么这三种情况能覆盖所有插入场景步骤 1确定基础前提插入前树是合法的步骤 2按u的颜色划分第一层级场景步骤 3证明无遗漏场景补充向上迭代的终止条件保证调整最终完成红黑树的插⼊代码实现红黑树的查找红黑树的验证红黑树的概念红黑树是⼀棵二叉搜索树他的每个结点增加⼀个存储位来表示结点的颜色可以是红色或者黑色。 通过对任何⼀条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有⼀条路径会比其他路径长出2倍因而是接近平衡的。红黑树的规则树中每一个节点的颜色要么是红色要么是黑色。树的根节点必须是黑色。如果一个节点是红色那么它的两个子节点必须都是黑色即树中不存在连续的红色节点。从任意一个节点出发到它所有的空NULL子节点的简单路径上包含的黑色节点数量都相同。红黑树如何确保最长路径不超过最短路径的2倍的根据红黑树的规则 4 可以推出从根节点到任意空NULL节点的路径包含的黑色节点数量都是相同的。因此在极端情况下最短路径就是全部由黑色节点构成的路径我们将这个最短路径的长度记为bh即黑高。结合规则 2根节点为黑色和规则 3不存在连续的红色节点可以推出极端情况下最长路径会由黑色节点和红色节点交替组成这条最长路径的长度就是2*bh。需要注意的是这种全黑的最短路径、以及一黑一红交替的最长路径并不是每一棵红黑树都会同时存在的。如果设从根节点到任意空节点的某条路径长度为x那么路径长度x会满足这样的范围bh ≤ x ≤ 2*bh红黑树的效率假设红黑树的节点总数为 N最短路径的长度为 h即黑高 bh那么 h 约等于 logN。红黑树中任意一条路径的长度都满足 h≤x≤2h这意味着红黑树的增删查改操作最坏情况下也只需要遍历最长路径对应的时间复杂度为 O(logN)。从节点数量的范围来看满足 2h−1≤N22h−1由此也能推导出红黑树的时间复杂度为 O(logN)。红黑树的平衡逻辑相比 AVL 树要更抽象一些AVL 树是通过严格控制左右子树的高度差来直接维持平衡而红黑树则是通过四条颜色规则的约束间接实现近似平衡。两者的时间复杂度处于同一档次但在插入相同数量的节点时红黑树的旋转次数更少 —— 因为它对平衡的要求没有 AVL 树那么严格。红黑树的实现// 枚举值表示颜色 enum Colour { RED, BLACK }; 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; };红黑树的插入红黑树树插入⼀个值的大概过程红黑树的插入流程可以分为两步先按二叉搜索树的规则插入新节点再检查插入后是否满足红黑树的四条核心规则根据情况调整。具体规则如下若插入前树为空那么新增节点直接作为根节点且颜色为黑色。若插入前树非空新增节点的颜色必须设为红色。这是因为如果设为黑色会直接破坏红黑树的规则 4任意节点到其 NULL 子节点的路径上黑节点数量相同而规则 4 的维护成本极高。非空树插入红色新节点后分两种情况判断若新节点的父节点颜色为黑色此时没有违反任何红黑树规则插入操作直接结束。若新节点的父节点颜色为红色则违反了规则 3不存在连续的红色节点。此时可以确定三个节点的颜色新节点ccur为红、父节点pparent为红、祖父节点ggrandfather必为黑。后续的调整策略关键取决于父节点的兄弟节点uuncle的颜色需要分情况处理。情况1变色触发条件核心是 “叔叔节点 u 为红”当新增节点c为红色、父节点p为红色、祖父节点g为黑色且叔叔节点u存在且为红色时调整规则如下变色操作将父节点p和叔叔节点u的颜色改为黑色将祖父节点g的颜色改为红色。向上迭代检查把祖父节点g当作新的当前节点c继续向上层g的父节点、祖父节点层级检查是否违反红黑树规则。调整逻辑分析原本p和u是红色、g是黑色将p和u变黑后g左右子树的路径上各增加了一个黑色节点再将g变红整体上保证了g所在子树的所有路径的黑色节点数量不变。这一步同时解决了c和p连续红色的问题但因为g被改为红色需要继续向上检查如果g的父节点是黑色调整结束如果g的父节点是红色则重复上述或其他对应情况的调整流程如果g已经是整棵树的根节点直接将g改回黑色即可。注意这种情况只需要变色不需要旋转无论c是p的左孩子还是右孩子也无论p是g的左孩子还是右孩子处理方式完全相同。图0图1图2跟AVL树类似图0我们展示了⼀种具体情况但是实际中需要这样处理的有很多种情况。图1将以上类似的处理进行了抽象表达d/e/f代表每条路径拥有hb个黑色结点的子树a/b代表每 条路径拥有hb-1个黑色结点的根为红的子树hb0。图2展示了hb3的具体情况组合分析当hb等于2时这里组合情况上百亿种这些样例是帮助我们理解不论情况多少种多么复杂处理方式⼀样的变色再继续往上处理即可所以我们只需要看抽象图即可。情况2单旋变色触发条件核心是 “叔叔节点 u 为黑 / 不存在且 c 与 p 同方向”当新增节点c为红色、父节点p为红色、祖父节点g为黑色且叔叔节点u不存在或存在但为黑色时需先明确节点背景若u不存在c是刚插入的新节点若u存在且为黑色c不是新节点它原本是黑色是因为其下方子树插入节点后经过 “情况 1变色” 调整才被改为红色并向上更新到当前层级的。如下图这种场景下仅靠变色无法解决问题会破坏黑节点数量平衡必须结合旋转 变色处理分两种子情况gp uc子情况 1p是g的左孩子c是p的左孩子旋转操作以祖父节点g为旋转点执行右单旋变色操作将父节点p改为黑色将祖父节点g改为红色调整后p成为这棵子树的新根。此时子树的黑节点数量保持不变也不存在连续红色节点且无需向上更新因为新根p的父节点无论颜色都不会违反红黑树规则。gu pc子情况 2p是g的右孩子c是p的右孩子旋转操作以祖父节点g为旋转点执行左单旋变色操作将父节点p改为黑色将祖父节点g改为红色调整后p成为这棵子树的新根。同样子树的黑节点数量、红节点连续性都符合规则无需向上更新。情况2双旋变色触发条件核心是 “叔叔节点 u 为黑 / 不存在且 c 与 p 反方向”c 为红p 为红g 为黑u 不存在或者 u 存在且为黑u 不存在则 c 一定是新增结点u 存在且为黑则c 一定不是新增c 之前是黑色的是在 c 的子树中插入符合情况 1变色将 c 从黑色变成红色更新上来的。分析p 必须变黑才能解决连续红色结点的问题u 不存在或者是黑色的这里单纯的变色无法解决问题需要旋转 变色。gp uc如果 p 是 g 的左c 是 p 的右那么先以 p 为旋转点进行左单旋再以 g 为旋转点进行右单旋再把 c 变黑g 变红即可。c 变成了这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为 c 的父亲是黑色还是红色或者空都不违反规则。图3gu pc如果 p 是 g 的右c 是 p 的左那么先以 p 为旋转点进行右单旋再以 g 为旋转点进行左单旋再把 c 变黑g 变红即可。c 变成了这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为 c 的父亲是黑色还是红色或者空都不违反规则。图3为什么这三种情况能覆盖所有插入场景插入新节点后仅可能出现连续红节点的违规因为新节点为红色其他规则均未被破坏而连续红节点的根源是c红→ p红我们可以通过穷举所有可能的场景证明这三种情况已覆盖全部可能性步骤 1确定基础前提插入前树是合法的插入前红黑树是合法的因此若p为红色则p的父节点g必为黑色否则p与g已连续红违反规则g必存在若p是根节点则p必为黑色与p为红矛盾因此p不可能是根g一定存在叔叔节点u是g的子节点只有两种可能红色或黑色包括不存在即 NIL。步骤 2按u的颜色划分第一层级场景场景 1u为红色 → 触发 “只变色”这是第一个明确的分支无其他子情况无论c是p的左 / 右孩子p是g的左 / 右孩子处理方式完全相同因为u为红时g的左右子树对称变色后黑节点数量仍平衡。场景 2u为黑色含不存在 → 需进一步按位置划分此时仅靠变色无法解决问题若将p改为黑色g的左子树黑节点数量会增加 1而右子树u为黑数量不变破坏黑节点平衡若将g改为红色又会引发上层连续红节点且仍无法解决当前连续红节点问题因此必须结合旋转而旋转的方式由c与p、p与g的位置关系决定子场景 2.1c与p同方向左左 / 右右→ 触发 “单旋 变色”子场景 2.2c与p反方向左右 / 右左→ 触发 “双旋 变色”。步骤 3证明无遗漏场景上述划分是互斥且穷尽的互斥性u的颜色只能是红或黑位置关系只能是同方向或反方向三种情况不会重叠穷尽性所有可能的违规场景都被包含在 “u为红”“u为黑且同方向”“u为黑且反方向” 中无其他可能性。补充向上迭代的终止条件保证调整最终完成在 “只变色” 的场景中需要将g作为新的c向上检查但这个过程不会无限循环因为若新的cg的父节点为黑色 → 无连续红节点调整终止若新的c是根节点 → 直接将其改为黑色满足根为黑的规则调整终止若新的c的父节点为红色 → 重复上述三种情况的判断此时新的c成为下一层的p新的祖父节点为原g的父节点叔叔节点为原g的兄弟节点最终会收敛到根节点或黑色父节点。红黑树的插⼊代码实现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 (grandfather-_left parent) { // g // p u // Node* uncle grandfather-_right; // uncle存在且为红 if (uncle uncle-_col RED) { // 变色 parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else // uncle不存在或者存在且为黑 { 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; }红黑树的查找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 倍是不可行的因为就算满足这个条件红黑树也可能颜色不满足规则当前暂时没出问题后续继续插入还是会出问题的。所以我们还是去检查 4 点规则满足这 4 点规则一定能保证最长路径不超过最短路径的 2 倍。规则 1 枚举颜色类型天然实现保证了颜色不是黑色就是红色。规则 2 直接检查根即可规则 3 前序遍历检查遇到红色结点查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲的颜色就方便多了。规则 4 前序遍历遍历过程中用形参记录根到当前结点的 blackNum (黑色结点数量)前序遍历遇到黑色结点就 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); }