★ FEATURED ARTICLE 文章目录红黑树概念储存规则效率插入逻辑一共三种情况情况一只变色二单旋变色三双旋变色尝试实现红黑树概念也是以二叉搜索树为基础的每个节点单位以pair储存他的每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是接近平衡的。储存规则每个结点不是红色就是黑色根结点是黑色的如果一个结点是红色的则它的两个子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点说明《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统意义上的叶子结点而是我们说的空结点有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径《算法导论》在后续讲解实现的细节中也忽略了NIL结点所以我们知道一下这个概念即可。NIL。意味NULL。是空的意思注空树也是红黑树满足每个结点不是红就是黑空树没有结点没有反例成立。根结点是黑色的空树没有根结点自然不违反“根必须是黑”的规则。或者可以理解为空指针本身就是一个黑色的外部结点NIL。红色结点的子结点必为黑没有红色结点成立。所有路径包含相同数量的黑色结点空树的所有路径只有一条长度为零的路径包含的黑色结点数都是相同的通常黑高 Black Height 记为 0。没有反例成立。路径根节点到空节点最短路径h最长路径2*h最短路径特点全黑最长路径特点红黑交替红黑树是怎么保证最长路径不超过最短路径的2倍依据三条规则从根到任意 NIL空叶子的路径黑节点数量相同。红节点的孩子必须是黑节点。根节点是黑色。设路径上有b个黑色节点不计末尾NIL那么最短路径至少有b个节点他们都是黑色那么最长路径的最长结果就是这b个黑色节点与红色节点交替出现最多有b个红色节点出现那么最长路径就是2b个节点效率假设N是红黑树树中结点数量h最短路径的长度那么2 h − 1 ≤ N 2 2 ∗ h − 1 2^h - 1 \le N 2^{2*h} - 12h−1≤N22∗h−1由此推出h ≈ l o g N h \approx logNh≈logN也就是意味着红黑树增删查改最坏也就是走最长路径2 ∗ l o g N 2*logN2∗logN那么时间复杂度还是O(logN)红黑树的表达相对AVL树要抽象一些AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束间接的实现了近似平衡他们效率都是同一档次但是相对而言插入相同数量的结点红黑树的旋转次数是更少的因为他对平衡的控制没那么严格。红黑树的查找按照搜索二叉树的规则来查找效率也是logN插入逻辑也是按照二叉搜索树的规则来进行如果是空树那么直接插入黑色节点要满足根节点是黑色的规则如果不是空树就必须插入红色保证黑色节点总数始终保持不变因为该规则最难维护那么出现两个红色节点连续出现怎么办后面通过旋转解决如果非空节点插入红色父节点是黑色那么没有违反任何规则插入结束如果非空节点插入红色父节点也是红色那么违反了红色节点不能连续出现的规则设当前节点为cur简称c父节点为parent简称p父节点的兄弟节点为uncle简称u父节点的父节点为grandparent简称g进一步分析c红p红g必为黑那么就只要看u的颜色来分析根据u分为下面几种情况来处理一共三种情况情况一只变色c红p红g黑u为红那么要将p和u变黑g变红因为g的左右子树为p、u/u、p要保证每条路的黑色数量不变就必须把g变红p、u变黑这同时也解决了红色连续的问题。再把g当做新的c向上更新如果g的父亲是红色那么还要继续处理如果是黑色就结束了如果g就是整棵树的根节点那么再把g变回黑色情况1只变色不旋转。所以无论c是p的左还是右p是g的左还是右都是上面的变色处理方式。下面参考图由具体到抽象二单旋变色c为红p为红g为黑u为黑或u为空当u为空时c一定是新插入节点直接进行旋转当u为黑时c一定不是新插入节点而是由下面的节点通过情况一变色变上来的三双旋变色c为红p为红g为黑u为空或u为黑u为空时c一定是新增节点u不为空与情况二同理是变色变上来的这里因为c节点出现在p节点的另一侧参考AVL树双旋的情况需要进行双旋尝试实现#pragma once // 枚举值表示颜色 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: //右旋 void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR parent-_right; parent-_left subLR; if (subLR) subLR-_parent parent-_left; Node* Parentparent parent-_parent; subL-_right parent; parent-_parent subL; // parent有可能是整棵树的根也可能是局部的⼦树 // 如果是整棵树的根要修改_root // 如果是局部的指针要跟上⼀层链接 if (Parentparent nullptr) { _root subL; subL-_parent nullptr; } else { if (Parentparent-_left parent) { Parentparent-_left subL; } else if (Parentparent-_right parent) { Parentparent-_right subl; } subL-_parent Parentparent; } parent-_bf subL-_bf 0; } //右旋 void RotateL(const Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_left subRL; if (subRL) subRL-_parent parent-_left; Node* Parentparet parent-_parent; subR-_right parent; parent-_parent subR; if (Parentparet nullptr) { _root subR; subR-_parent nullptr; } else { if (Parentparet-_left parent) { Parentparet-_left subR; } else if (Parentparet-_right parent) { Parentparet-_right subR; } subR-_parent Parentparet; } parent-_bf subR-_bf 0; } 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) { cur parent-left; } else { cur parent-_right } cur-_parent parent; while (parent parent-_col RED)//parent存在且为红 { Node* grandfa parent-_parent; if (parent grandfa-_left)//parent在grandfa左 { Node* uncle grandfa-_right; if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfa-_col RED; //继续往上处理 cur grandfa; parent cur-_parent; } else//uncle为黑或不存在 { //parent与cur都在左侧 if (cur parent-_left) { RotateR(grandfa);//单旋右旋 parent-_col BLACK; grandfa-_col RED } else//parent在grandfa左侧,cur在parent右侧 { RotateL(parent); RotateR(grandfa); cur-_col BLACK; parent-_col BLACK; grandfa-_col RED; } break; } } else//parent在grandfa的右 { Node* uncle grandfa-_left; //uncle存在且为红直接变色 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfa-_col RED; //继续往上处理 cur grandfa; parent cur-_parent; } else//uncle不存在或为黑 { if (cur parent-_right)//parent在grandfa右侧cur在parent右侧 { RotateL(grandfa);//单旋左旋 parent-_col BLACK; grandfa-_col RED; } else//parent在grandfa右侧cur在parent左侧 { RotateR(parent); RotateL(grandfa); parent-_col BLACK; grandfa-_col RED; cur-_col BLACK; } break; } } } _root-_col BLACK; return true; } void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_kv.first ; _InOrder(root-_right); } // 前序递归遍历检查 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 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 IsBalanceTree() { 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: Node* _root nullptr; };完
阅读完成 · 觉得有帮助？
)
