前言 　　11.1新的一月加油！这个购物狂欢的季节，一看，已囊中羞涩！赶紧来恶补一下红黑树和2-3树吧!红黑树真的算是大名鼎鼎了吧？即使你不了解它，但一定听过吧？下面跟随我来揭开神秘的面纱吧！ 　　一、2-3树 　　1、抢了红黑树的光环？ 　　今天的主角是红黑树，是无疑的，主角光环在呢！那2-3树又是什么鬼呢？学习2-3树不仅对理解红黑树有帮助，对理解B类树，也是有巨大帮助的，所以学习2-3树很必要！ 　　2、基本性质 　　2-3树满足二分搜索树的基本性质，但节点可以存放一个元素或两个元素！如下图，就是2-3树： 　　 　　说明：2-3树一颗绝对平衡的树（绝对平衡：对于任意一个节点，左右子树高度相同） 　　3、维护绝对平衡 　　2-3树在插入过程中如何维护绝对平衡呢？进行画图演示，实在有点不好画，如下图： 　　 　　说明： 　　1、不能将新节点插入到空节点 　　　　因为那样如上图，就不满足绝对平衡了，所以可以将37和42合并，2-3支持3节点。 　　2、不支持4节点，进行拆分 　　　　再插入12时，也不能插入空节点，也要合并，但2-3树不支持4节点，所以进行进行拆分。 　　3、子节点达到3节点，合并到父节点 　　　　再依次插入18、6，达到4节点，进行拆分，但不符合绝对平衡了怎么办？将12和37合并，就形成了最后3节点的图了 　　总结：讲到这里，应该对2-3树如何维护绝对平衡，应该了解了吧？理解2-3树，对于再理解红黑树，是非常有帮助的，其实，它们有等价性的，接下来会说明的。 　　二、红黑树 　　1、红黑树和2-3树的等价性 　　也想达到像2-3树那样的绝对平衡，但2-3树的实现比较麻烦，所以产生了红黑树；那么,红黑树和2-3树有怎么样的等价性呢？如下图： 　　 　　说明：红黑树最开始想用红线区别b、c，但实现起来比较困难，然后用红黑来表示节点，就比较好实现了！ 　　红黑树和2-3树总体对比图，可以参考一下： 　　 　　2、红黑树5个重要性质 　　1、引自《算法导论》 　　红黑树有五个重要性质，引自算法界一本圣洁《算法导论》中的内容，如下： 　　 　　是不是看着有点晕，下面我进行解释。 　　2、5个重要性质 　　1、每一个节点或者红色的，或是黑色的 　　2、根节点是黑色的 　　3、每一个叶子节点（最后的空节点）是黑色的 　　4、如果一个节点是红色的，那么它的孩子节点都是黑色的 　　5、从任意节点到叶子节点，经过的黑色节点是一样的 　　 　　解释：最重要的性质是第五条，前4条在理解2-3树之后，就很好理解了，第5条性质说明了：红黑树是保持“黑平衡”的二叉树； 严格意义上来说，红黑树不是平衡二叉树，最大高度：2logn，但是时间复杂度仍然是O（logn），因为2是常数，但比AVL树查询要稍微慢一些。 　　三、红黑树添加元素 　　红黑树添加元素，比较繁琐，因为要保持上面的五个性质，要不然就不是红黑树了； 　　1、保持根节点为节点 　　红黑树的节点类也可以从二分搜索树上进行修改，但要新增“color”成员变量，来标注节点颜色，节点类如下： 复制代码 template class RBTree { private: static const bool RED = true; static const bool BLACK = false; struct Node { Key key; Value value; Node *left; Node *right; bool color; Node(Key key, Value value) { this->key = key; this->value = value; this->left = this->right = nullptr; color = RED;　　//默认初始化为红色 } Node(Node *node) { this->key = node->key; this->value = node->value; this->left = node->left; this->right = node->right; this->color = node->color; } }; Node *root; int size; } 复制代码 　　因为红黑树性质1要求根节点为黑色，所以要保持根节点为黑色； 　　2、左旋转 　　像AVL树一样，红黑树也需要左旋和右旋，如下图就需要左旋转，因为“红色节点是左倾斜的”： 　　 　　说明：图中黑色字体标识黑色节点，红色表示红色节点，并演示了旋转过程，最后还要改变节点颜色。 　　3、左旋转代码实现 　　代码如下： 　　 复制代码 Node *leftRotate(Node *node) { Node *x = node->right; node->right = x->left; x->left = node; x->color = node->color; node->color = RED; return x; } 复制代码 　　4、颜色反转 　　下面这种情况就需要颜色反转，如下图： 　　 　　 　　5、颜色反转代码实现 　　代码如下： 复制代码 void flipColors(Node *node) { node->color = RED; node->left->color = BLACK; node->right->color = BLACK; } 复制代码 　　6、右旋转 　　下面情况需要右旋转，如下图： 　　 　　　　旋转之后，如下图： 　　 　　　7、右旋转代码如下 　　代码如下： 　　 复制代码 Node *rightRotate(Node *node) { Node *x = node->left; node->left = x->right; x->right = node; x->color = node->color; node->color = RED; return x; } 复制代码 　　8、总体流程图 　　 　　9、总体代码 　　总体代码如下，供参考和学习： View Code 　　总结　　 　　面试时99.9%不会让手写一下红黑树的添加过程，除非你面试算法工程师，那就打扰了！主要理解红黑树的性质、左旋和右旋等。 　　欢迎点赞和评论，感谢支持！ 作者：柳德维 出处：https://www.cnblogs.com/liudw-0215/ ------------------------------------------- 个性签名：独学而无友，则孤陋而寡闻。做一个灵魂有趣的人！ 如果觉得这篇文章对你有小小的帮助的话，记得在右下角点个“推荐”哦，博主在此感谢！ 万水千山总是情，打赏一分行不行，所以如果你心情还比较高兴，也是可以扫码打赏博主，哈哈哈(っ•̀ω•́)っ✎⁾⁾！https://www.cnblogs.com/liudw-0215/p/9887951.html