2-3 树 与 红-黑 树

红黑树的本质就是2-3树，二者可以完全等价。想要弄清楚红黑树可以直接从2-3树下手。

什么是2-3树？

一句话，2-3树一个绝对平衡的多叉树，每一个节点的左右子树高度差不超过1。

2-3树中有两种节点。一种是2节点，与二分搜索树中的节点相同，每个2节点有两个子树。另一种是3节点，每个节点包含两个元素，每个节点有三个子树。

假设依次向2-3树中添加 21，17，15，13，11节点，整个过程如下：

2-3树 与 红-黑 树 对比

当只有一个节点“21”时，这就是一个普通的二分搜索树，只有一个2节点。随后加入新节点“17”，“17”选择与“21”融合，形成一个3节点。继续加入新节点“15”，“15”先选择与现有的3节点融合形成4节点，随后分裂，形成3个2节点。继续加入新节点“13”，新节点直接与“15”融合形成一个3节点。接续加入新节点“11”， 新节点“11”先于“13”“15”融合形成一个4节点，随后分裂成三个 2节点，“13”节点继续向上融合，与上一层的“17”节点融合成3节点。

可以看出，即使我们以最极端的方式，从大到小（或是 从小到大）插入节点，2-3树依旧能保持平衡。

总结一下2-3树的操作规则：

1. 新节点加入的时候永远选择与现有的节点进行融合

2. 若融合成一个3节点，则到此为止

3. 若融合成一个4节点（一个节点有三个元素），则进行分裂，分裂出来的上面一个节点向上继续融合，进入步骤1。

红-黑 树 与 2-3 树

红-黑树 本质上 就是将 2-3树 转换为 二叉树。其中的红色节点就是 2-3 树中的3节点的 左边一个节点，且红色节点是 2-3 树中的3节点的右边节点的左孩子。

根据形象化地对比 红-黑 树 与 2-3 树可以很轻松地得出红黑树具有以下特征：

• 红黑树的根节点一定是黑色。

• 红黑树是一个相对平衡的二叉树，或者说是一个绝对 黑平衡 的二叉树，任意节点的左右子树的 黑高度 相等，任意两个叶子节点到他们的祖先节点经过的黑节点个数一定相等。