本文共 1565 字，大约阅读时间需要 5 分钟。

红黑树的起源，自然是二叉查找树了，这种树结构从根节点开始，左子节点小于它，右子节点大于它。每个节点都符合这种特性，所以易于查找，是一种很好的数据结构。但是它有一个问题，就是容易偏向某一侧，这样就像一个链表结构了，失去了树结构的优点，查找时间就会变坏。

所以我们都希望树结构都是矮矮胖胖的，像这样：

红黑树就是一种平衡树，它可以保证二叉树基本符号矮矮胖胖的结构，但是理解红黑树之前，必须先了解另一种树，叫做2-3树，红黑树背后的逻辑就是它

• 2-3数是二叉查找树的变种，树中的2和3代表两种节点，即2-节点和3-节点。
• 2-节点是普通节点：包含一个元素，两个子连接
• 3-节点是扩容版，包含两个元素，三个子连接。
  • 两个元素A、B
  • 左边的连接指向小于A的节点，中间的连接指向介于A、B之间的节点，右边的连接指向大于B的节点

所谓构造，就是从零开始一个节点一个节点的插入。在二叉查找树中，插入过程是从根节点开始比较，当前值小于节点值则继续与左子节点比，大于则继续与右子节点比，知道某节点左或者右子节点为空，则把值插入进去。这样无法避免偏向问题。在2-3树中，插入的过程是这样的

（1）如果将值插入一个2-节点，则将2-节点扩充为一个3-节点

• 第一种情况：3-节点没有父节点，即整颗树就只有它一个三节点。此时，将3-节点扩充为一个4-节点，即包含三个元素的节点，然后将其分解，变成一颗二叉树。此时二叉树仍然保持平衡
  
• 第二种情况：3-节点有一个2-节点的父节点，此时的操作是，3-节点扩充为4-节点，然后分解4-节点，然后将分解后的新树的父节点融入到2-节点的父节点中去
  
• 第三种情况：3-节点有一个3-节点的父节点，此时操作是：3-节点扩充为4-节点，然后分解4-节点，新树父节点向上融合，上面的3-节点继续扩充，融合，分解，新树继续向上融合，直到父节点为2-节点为止，如果向上到根节点都是3-节点，将根节点扩充为4-节点，然后分解为新树，至此，整个树增加一层，仍然保持平衡

从上面可以看出，2-3树的设计完全可以保证二叉树保持矮矮胖胖的状态，保持其性能良好。但是，将这种直白的表述写成代码实现起来并不方便，因为要处理的情况太多。这样需要维护两种不同类型的节点，将链接和其他信息从一个节点复制到另一个节点，将节点从一种类型转换为另一种类型等等。

因此，红黑树出现了，红黑树的背后逻辑就是2-3树的逻辑，但是由于用红黑作为标记这个小技巧，最后实现的代码量并不大。

我们先来看看红黑树和2-3树的关联。首先，最台面上的问题，红和黑的含义。红黑树中，所有的节点都是标准的2-节点，为了体现出3-节点，这里将3-节点的两个元素用作斜红色的链接链接起来，即连接了两个2-节点来表示一个3-节点。这里红色节点标记就代表指向其的链接是宏链接，黑色标记的节点就是普通的节点。所以才会有这样一条定义：“从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点”，因为红色节点是可以与其父节点合并为一个3-节点的，红黑树实现的其实是一个完美的黑色平衡，如果你将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的，所以它并不是一个严格的平衡二叉树，但是它的综合性能已经很优秀了

• 红黑树均为左链接
• 没有任何一个节点同时与两颗红链接相连（这样会出现4-节点）
• 该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同

转载地址：https://blog.csdn.net/zhizhengguan/article/details/122421684 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！