红黑树是数据结构中比较复杂的一种，最近与它交集颇多，于是花了一周的空闲时间跟它死磕，终于弄明白并实现了红黑树。写文总结一下，希望能给试图理解红黑树的同学一些灵感，也让我能记得更深刻。
在研究红黑树时吃了不少苦头，原因有二：
红黑树的插入和删除非常复杂，很多人并没有理解或完全实现，或实现了的没有任何注释，让人很难参考；
网络上红黑树的理解方式较为单一，一般是 双黑、caseN 法，而插入和删除的情况很多，每种都有对应的处理方式，如果死记硬背的话，再过一段时间再回忆各种情况可能就一头雾水了。
网络上讲红黑树的实现多来源于《算法导论》一书，直接讲红黑树的实现，需要处理颜色和高度两种属性约束，比较晦涩。本文通过红黑树的等同—— 2-3-4树，避开颜色属性约束，也弱化了高度的影响，以另一种方式去理解红黑树，虽然并不能完全降低它的复杂度，但自认为较之普遍实现，更易记一些。
文章最前面先放上红黑树的实现源码，代码在 Github 上，一开始实现时使用我最熟练的 PHP，后续添加了 Java 版，代码都可以直接运行。源码链接：GitHub-枕边书-RBTree，欢迎star。
文章欢迎转载，请注明出处：。
红黑树 定义红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下要求：
节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
下图就是一个典型的红黑树：
但实现上我省略了其中的 Nil 结点，一般如下图，大家理解时也可以忽略它们。
我们知道二叉查找树在不停地添加或删除结点后，可能会导致结点情况如下：
这种情况下，二叉查找树的查找效率最坏会降低为 O(n)。
而红黑树由于在插入和删除结点时都会进行变色旋转等操作，在符合红黑树条件的情况下，即使一边子树全是黑色结点，另一边子树全是红黑相间，两子树的高度差也不会超过一半。一棵有 n 个结点的红黑树高度至多为 2log(n+1)，查找效率最坏为 O(log(n))。
所以红黑树常被用于需求查找效率稳定的场景，如 Linux 中内核使用它管理内存区域对象、Java8 中 HashMap 的实现等，所以了解红黑树也很有意义。
下面介绍一下红黑树的等同 2-3-4树。
2-3-4树 定义2-3-4树是四阶的 B树(Balance Tree)，它的结构有以下限制：
所有叶子节点都拥有相同的深度。
节点只能是 2-节点、3-节点、4-节点之一。
2-节点：包含 1 个元素的节点，有 2 个子节点；
3-节点：包含 2 个元素的节点，有 3 个子节点；
4-节点：包含 3 个元素的节点，有 4 个子节点；
元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点；而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。
下图是一个典型的 2-3-4树（来自维基百科）：
2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。
对应红黑树至于为什么说红黑树是 2-3-4树的一种等同呢，这是因为 2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵 2-3-4树也都对应一棵红黑树，下图是 2-3-4树不同结点与红黑树子树的对应。
而上文中的 2-3-4树也可以转换成一棵红黑树：