目录1、红黑树的概念2、红黑树的性质3、红黑树节点的定义4、红黑树类 的基本框架5、红黑树的插入操作6、红黑树的验证7、红黑树的删除8、红黑树与AVL树的比较9、红黑树的应用1、红黑树的概念红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍最长路径不超过最短路径的2倍因而是接近平衡的。同是二叉搜索平衡树但是AVL树控制的比红黑树严格的多AVL树要是每个节点的平衡因子绝对值不超过1就会导致不断的去旋转调整付出相对较高的代价而这里红黑树更像是一种近似平衡条件没有这么苛刻。如下一棵树站在红黑树的角度看是平衡的站在AVL树的角度看就是不平衡的需要旋转调整但是从搜索效率的角度看AVL树还是好一点因为它的平衡标准高就导致其更加平衡相同数量的节点情况下AVL树的高度会更低加上存100w个数据AVL树大概有20层log100w而红黑树最坏就能达到40层显然AVL树的搜索效率高。但是在内存里找20次和找40次没有什么区别因为CPU足够的快这里简单提一下。2、红黑树的性质1、每个结点不是红色就是黑色2、根节点必须是黑色的3、如果一个节点是红色的则它的两个孩子结点是黑色的没有连续的红色节点4、对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每条路径都包含相同数量的黑色节点5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点 -》NIL节点)根据这些规则红黑树是如何保证最长路径不超过最短路径的2倍的呢首先我们根据规则分析得知我们假设一条路径的黑色节点的个数为N个则最长路径和最短路径的情况如下最短路径全黑最长路径一黑一红间隔而这里一黑一红间隔的原因在于红黑树不允许出现连续的红节点为了能最大程度的保证最长节点数唯有一黑一红间隔的方式才能达到最长综上当黑节点个数固定为N时最短路径节点个数为N最长路径节点个数为2N3、红黑树节点的定义这里节点的实现相较于AVL树我们依旧是创建成KV模型、三叉链结构唯一有所改变的是这里要通过枚举的方式把红色和黑色定义好并在节点类内部定义变量_col表示节点颜色最后记得写上构造函数。enum Colour { Red, Black, }; //节点类 template class K, class V struct RBTreeNode { //三叉链结构 RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; //存储的键值对 pairK, V _kv; //节点的颜色 Colour _col; //构造函数 RBTreeNode(const pairK, V kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(Red) {} };为什么插入的节点在构造函数这里要处理成红色如果处理成黑色则一定导致新插入节点的那条路径多出一个黑色节点不再满足各个路径黑色节点个数相同的性质一定破坏性质4此时很难维护。如果处理成红色则可能父亲节点也是红色此时就出现了连续的红色节点破坏性质3不过此时我们向上调整即可但如果父亲节点是黑色那就无需操作了不违反任何性质。综合利弊插入黑色节点一定会破坏性质4而插入红色节点可能破坏性质3因此处理成红色为宜。4、红黑树类 的基本框架此模板类主要是用于红黑树的插入、旋转、调整、验证等等操作基本框架如下//红黑树的类 template class K, class V class RBTree { typedef RBTreeNodeK, V Node; public: //…… private: Node* _root nullptr; };5、红黑树的插入操作红黑树的插入操作主要分为这几大步骤1、一开始为空树直接new新节点2、一开始非空树寻找插入的合适位置3、找到插入的合适位置后进行父亲与孩子的双向链接4、检测新节点插入后红黑树的性质是否造到破坏接下来对其进行逐个分析1、一开始为空树直接new新节点因为树为空的所以直接new一个新插入的节点将其作为根_root即可接着更新颜色_col为黑色。2、一开始非空树寻找插入的合适位置这里和二叉搜索树的寻找合适的插入位置的思想一样都要遵循以下几步插入的值 节点的值更新到右子树查找插入的值 节点的值更新到左子树查找插入的值 节点的值数据冗余插入失败返回false当循环结束的时候就说明已经找到插入的合适位置即可进行下一步链接。3、找到插入的合适位置后进行父亲与孩子的双向链接注意这里节点的构成为三叉链因此最后链接后端孩子和父亲是双向链接具体操作如下插入的值 父亲的值把插入的值链接在父亲的右边插入的值 父亲的值把插入的值链接在父亲的左边因为是三叉连插入后记得双向链接孩子链接父亲走到这说明节点已经插入完毕接下来就要对红黑树的颜色进行调整了4、检测新节点插入后红黑树的性质是否造到破坏不是所有的情况都是需要进行调整的当插入节点的父亲为黑色新节点的默认颜色是红色那么就不需要进行调整因为没有破坏红黑树的任何一条性质。只有当插入节点的父亲为红色时新节点的默认颜色也是是红色才需要进行调整因为此时插入的节点和父亲都是红色节点但是红黑树不允许出现连续的红色节点此时就要进行调整。注意这里既然插入节点cur的父亲p是红色那么根据红黑树的性质根结点是黑色的其父亲的父亲g也就是祖父必然存在且一定是黑色那么其父亲的兄弟节点u可能不存在也就是新插入节点cur的叔叔。因此我们约定cur为当前节点p为父节点g为祖父节点u为叔叔节点。这里调整的办法主要是看叔叔节点的颜色如何叔叔节点的不同会导致三种不同的情况需要调整情况一cur为红p为红g为黑u存在且为红情况二cur为红p为红g为黑u不存在情况三cur为红p为红g为黑u存在且为黑接下来分别进行讨论情况一cur为红p为红g为黑u存在且为红为了避免出现连续的红色节点我们可以把父节点p变黑但是为了保证每条路径的黑色节点个数相同我们需要把祖父节g点变红不影响其它路径黑节点的个数再把叔叔节点u变黑。调整并未结束此时祖父节点g为红色但是如果这棵树本就是一颗完整的树呢也就是g为根节点那么只需要把节点g变成黑色即可。如果这棵树是一棵树的子树那么刚好把祖父节点g作为新插入的节点cur向上继续调整继续判断父亲、叔叔如何……直至调整结束。补充情况一不关心左右关系只变色不旋转所以 p、u是g的左或右是无所谓的cur是p的左或右也是无所谓的。情况二cur为红p为红g为黑u不存在如果节点u不存在则cur一定是新插入节点因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色就不满足性质4每条路径黑色节点个数相同。此时就是一个很经典的右单旋结构新节点插入较高左子树的左侧我们可以先对其进行一个右单旋再来更新颜色。具体步骤如下让祖父g变成父亲p的右子树父亲p作为根节点更新父亲节点p为黑色更新祖父g为红色补充如若p为g的右孩子cur为p的右孩子则针对p做左单旋转示例如若祖孙三代的关系是折线cur、parent、grandfather这三个结点为一条折现则我们需要先进行双旋操作再进行颜色调整颜色调整后这棵被旋转子树的根是黑色的因此无需继续往上进行处理。示例综上p为g的左cur为p的左则进行右单旋 p变黑g变红p为g的右cur为p的右则进行左单旋 p变黑g变红p是g的左cur是p的右则进行左右双旋 cur变黑 g变红p是g的右cur是p的左则进行右左双旋 cur变黑 g变红下面进入情况三情况三cur为红p为红g为黑u存在且为黑此情况绝非单独存在绝不可能是真的新节点cur插入然后还会出现p为红g为黑u存在且为黑的情况如果存在那么只能说明先前插入节点或者构造函数就有问题因为插入前就不符合红黑树的性质啊每个路径的黑节点个数均相同既然情况三出现了那么一定是合理的它就是建立在情况一的基础上继续往上调整从而出现的一种特殊情况具体咱就是画图演示此时就是很明显的一个情况3了cur为红pp为红gg为黑u存在且为黑由此证明情况三是通过情况一向上继续调整演化出来的。并且此新节点一定是从p和x任意一颗左右子树插入或演化上来的才引发后续的cur从黑变红。此时就是一个很经典的右单旋结构cur在较高左子树的左侧我们可以先对其进行一个右单旋再来更新颜色。具体步骤如下让p的右子树变成g的左子树让p变成根节点位置p的右子树指向g更新p的颜色为黑色更新g的颜色为红色补充如若p为g的右孩子cur为p的右孩子则进行左单旋 调色示例综上p为g的左cur为p的左则进行右单旋 p变黑g变红p为g的右cur为p的右则进行左单旋 p变黑g变红p是g的左cur是p的右则进行左右双旋 cur变黑 g变红p是g的右cur是p的左则进行右左双旋 cur变黑 g变红情况二和情况三旋转 变色后这颗子树不违反红黑树规则相比插入前且黑色节点的数量不变不会影响上层处理结束了。代码如下bool Insert(const pairK, V kv) { //1、一开始为空树直接new新节点 if (_root nullptr) { _root new Node(kv); _root-_col Black;//新插入的节点处理成黑色 return true; } //2、寻找插入的合适位置 Node* cur _root; Node* parent nullptr; 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;//插入的值 节点的值数据冗余插入失败返回false } } //3、找到了插入的位置进行父亲与插入节点的链接 cur new Node(kv); cur-_col Red;//插入的节点处理成红色 if (parent-_kv.first kv.first) { parent-_right cur;//插入的值 父亲的值链接在父亲的右边 } else { parent-_left cur;//插入的值 父亲的值链接在父亲的左边 } cur-_parent parent;//三叉链要双向链接 //4、检测新节点插入后红黑树的性质是否造到破坏 while (parent parent-_col Red)//存在连续的红色节点 { Node* grandfather parent-_parent; assert(grandfather); //先确保叔叔的位置 if (grandfather-_left parent) { Node* uncle grandfather-_right; //情况一cur为红p为红g为黑u存在且为红 if (uncle uncle-_col Red) { //变色 parent-_col uncle-_col Black; grandfather-_col Red; //继续往上处理 cur grandfather; parent cur-_parent; } //情况二情况三叔叔不存在或者叔叔存在且为黑 else { if (cur parent-_left)//p为g的左cur为p的左则进行右单旋 p变黑g变红 { // g // p // cur RotateR(grandfather); parent-_col Black; grandfather-_col Red; } else//p是g的左cur是p的右则进行左右双旋 cur变黑 g变红 { // g // p // cur RotateLR(grandfather); cur-_col Black; grandfather-_col Red; } break; } } else//grandfather-_right parent { Node* uncle grandfather-_left; //情况一cur为红p为红g为黑u存在且为红 if (uncle uncle-_col Red) { //变色 parent-_col uncle-_col Black; grandfather-_col Red; //继续往上处理 cur grandfather; parent cur-_parent; } //情况二情况三叔叔不存在或者叔叔存在且为黑 else { if (cur parent-_right)//p为g的右cur为p的右则进行左单旋 p变黑g变红 { // g // p // cur RotateL(grandfather); parent-_col Black; grandfather-_col Red; } else//p是g的右cur是p的左则进行右左双旋 cur变黑 g变红 { // g // p // cur RotateRL(grandfather); cur-_col Black; grandfather-_col Red; } break; } } } _root-_col Black;//暴力处理把根变成黑色 return true; } //1、左单旋 void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; Node* ppNode parent-_parent;//提前保持parent的父亲 //1、建立parent和subRL之间的关系 parent-_right subRL; if (subRL)//防止subRL为空 { subRL-_parent parent; } //2、建立subR和parent之间的关系 subR-_left parent; parent-_parent subR; //3、建立ppNode和subR之间的关系 if (parent _root) { _root subR; _root-_parent nullptr; } else { if (parent ppNode-_left) { ppNode-_left subR; } else { ppNode-_right subR; } subR-_parent ppNode;//三叉链双向链接关系 } } //2、右单旋 void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; Node* ppNode parent-_parent; //1、建立parent和subLR之间的关系 parent-_left subLR; if (subLR) { subLR-_parent parent; } //2、建立subL和parent之间的关系 subL-_right parent; parent-_parent subL; //3、建立ppNode和subL的关系 if (parent _root) { _root subL; _root-_parent nullptr; } else { if (parent ppNode-_left) { ppNode-_left subL; } else { ppNode-_right subL; } subL-_parent ppNode;//三叉链双向关系 } } //3、左右双旋 void RotateLR(Node* parent) { RotateL(parent-_left); RotateR(parent); } //4、右左双旋 void RotateRL(Node* parent) { RotateR(parent-_right); RotateL(parent); }6、红黑树的验证红黑树的验证主要分为两大步骤1、检测其是否满足二叉搜索树(中序遍历是否为有序序列)2、检测其是否满足红黑树的性质接下来分别演示1、检测其是否满足二叉搜索树(中序遍历是否为有序序列)这里只需要递归写一个中序遍历并判断测试用例的结果是否为一个有序序列即可判断二叉搜索树//验证是否为一颗搜索二叉树 void InOrder() { _InOrder(_root);//调用中序遍历子树 cout endl; } //中序遍历的子树 void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_kv.first ; _InOrder(root-_right); }2、检测其是否满足红黑树的性质这里只要判断是否满足红黑树的5大规则即可具体操作如下1、根节点是否为黑色2、任意一条路径黑色节点数是否相同递归每一条和确定的一条比较是否相同3、递归检测是否违反性质三从而出现连续的红节点bool IsBalanceTree() { Node* pRoot _root; // 空树也是红黑树 if (pRoot nullptr) return true; // 检测根节点是否满足情况 if (pRoot-_col ! Black) { cout 违反红黑树性质二根节点必须为黑色 endl; return false; } // 获取任意一条路径中黑色节点的个数--拿最左路径作为比较基准值 size_t blackCount 0; Node* pCur pRoot; while (pCur) { if (pCur-_col Black) blackCount; pCur pCur-_left; } // 检测是否满足红黑树的性质k用来记录路径中黑色节点的个数 size_t k 0; return _IsValidRBTree(pRoot, k, blackCount); } bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount) { //走到null之后判断k和black是否相等 if (pRoot nullptr) { if (k ! blackCount) { cout 违反性质四每条路径中黑色节点的个数必须相同 endl; return false; } return true; } // 统计黑色节点的个数 if (pRoot-_col Black) k; // 检测当前节点与其双亲是否都为红色 Node* pParent pRoot-_parent; if (pParent pParent-_col Red pRoot-_col Red) { cout 违反性质三没有连在一起的红色节点而这里出现了 endl; return false; } return _IsValidRBTree(pRoot-_left, k, blackCount) _IsValidRBTree(pRoot-_right, k, blackCount); }7、红黑树的删除红黑树的删除这里和AVL树一样就不做过多演示了具体可参考《算法导论》或者《STL源码剖析》8、红黑树与AVL树的比较红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(logN)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。9、红黑树的应用1、C STL库 -- map/set、mutil_map/mutil_set2、Java 库3、linux内核4、其他一些库