经典搜索算法之2-3-4树与红黑树

缺乏、安全感 2022-05-15 00:52 49阅读 0赞

## 1.2-3-4树 ##

在笔者[上篇文章][Link 1]中，介绍了B树和B+树，这里我所说的2-3-4树就是阶为4的B树。根据离散数学的图论相关知识，可以证明2-3-4树和红黑树是等价的。对于m阶(m指的结点的最大分支数)B树，其结点的值的个数n：1<=n<m。因此，对于2-3-4树，其结点的值的个数1<=n<4，如下图所示：

![70][]

## 2.红黑树 ##

红黑树也是一种平衡查找树，只不过其结点是带有色彩的二叉查找树，红黑树可以保证在![Olog(n)][Olog_n]时间内完成查找，插入和删除。此外，红黑树具有其下特性：

1.  结点是红色或黑色。
2.  根结点是黑色。
3.  每个叶子结点都带有两个空的黑色结点（称之为NIL节点，它又被称为黑哨兵）。
4.  每个红色结点必须有两个黑色的子结点。（从每个叶子到根的所有路径上不能有两个连续的红色结点。）
5.  从任一结点到其每个叶子结点的所有简单路径都包含相同数目的黑色节点。

下面进行举例说明：

![70 1][]                           ![70 2][]

上图中左右两棵树是一样的，只不过一个画出了null结点，一个没有画出。**我们在理解和真正操作的时候，以没有null结点的图进行理解操作即可。**添加null结点表示数据结束，保证了所有结点都有两个子结点，这样做的好处是使得红黑树在算法的实现上更简单些。

下面我们从图来看2-3-4树和红黑树为何的等价的：

首先，我们将上图中的红结点放平：

![70 3][]                              ![70 4][]

然后，我们将红结点合并到与其在同一层、并直接相连的黑结点：

![70 5][]

通过上面过程可看出任何红黑树可以转化为2-3-4树。都可以可以想想如何将最上面的2-3-4树转化为红黑树。

**红黑树的旋转变色：**

**   **由于插入操作可能会破坏红黑树的平衡性，因此我们在插入值后需要对红黑树进行调整，这个调整过程就是红黑树结点的颜色变换和旋转操作，这些操作都可以从2-3-4树的角度来理解。

假设我们在上图的2-3-4树中插入17，则：

![70 6][]

将其转化为红黑树：

![70 7][]

插入完毕，相比直接在原红黑树进行旋转变色，以2-3-4树的方式更容易简单理解。插入17后的红黑树其实是在原红黑树基础上旋转、变色得到的。

红黑树一般应用在关联数组，关联数组是一种具有特殊索引方式的数组。不仅可以通过整数来索引它，还可以使用字符串或者其他类型的值来索引它。通俗的讲，关联数组就是大家熟知的key-value系统。最典型的是，在java8以前，hashmap是数组和链表实现的，在java8以后，为了防止某一索引处链表过长，造成hashmap的查询、增删操作效率降低，在某一索引处的链表长度达到8时，该处的链表会被红黑树所替换，以保证hashmap的效率。

[Link 1]: https://blog.csdn.net/m0_38075425/article/details/81777364
[70]: /images/20220515/c1d3f88300974ac4a18c976a5645d6d2.png
[Olog_n]: https://private.codecogs.com/gif.latex?Olog%28n%29
[70 1]: https://img-blog.csdn.net/20180828105802304?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDc1NDI1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: /images/20220515/ec07a458df3645129e0f63fa84ece75b.png
[70 3]: https://img-blog.csdn.net/20180828111323543?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDc1NDI1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 4]: /images/20220515/f8ed26053ec0477596d18ec0098b0bb4.png
[70 5]: /images/20220515/0a9da8b2a4f1426e80625af27b4ff2f0.png
[70 6]: /images/20220515/798cf60813824285b3bbed8b7a0b17f4.png
[70 7]: /images/20220515/6fcf25010bb847019ad208460a1115bc.png