数据结构与算法之红黑树

数据结构与算法系列

数据结构与算法之哈希表

数据结构与算法之跳跃表

数据结构与算法之字典树

数据结构与算法之2-3树

数据结构与算法之平衡二叉树

数据结构与算法之红黑树

数据结构与算法之十大经典排序

数据结构与算法之二分查找三模板

数据结构与算法之动态规划

数据结构与算法之回溯算法

数据结构与算法之Morris算法

数据结构与算法之贪心算法

数据结构与算法之摩尔投票

数据结构与算法之红黑树

前言

红黑树是基于AVL树（平衡二叉树）的基础上提出一种新的树结构，并且它与2-3树可以说是等价的。
因此在介绍红黑树之前，先把AVL树和2-3树与大家梳理一下。
同时，本文主要是想介绍红黑树的基本原理与构建规则，其底层实现是十分庞大且复杂的，因此我们更多的关注点在于理解它的构建并知晓红黑树的用途。

平衡二叉树（AVL树）

介绍

对于二叉搜索树，大家应该都不是很陌生，二叉搜索树具有每个节点的左子树节点大小都要比该节点小，右子树节点大小都要比该节点大的性质。因此，平均情况下，二叉搜索树这一数据结构的各种操作可以达到O(logn)的时间复杂度。
但是，最坏情况下，二叉搜索树可能会退化成链表，即二叉树失衡，如下图。

因此，就诞生了平衡二叉树。
接下来就介绍下，平衡二叉树的性质以及其调整失衡的策略。

性质

1. 平衡二叉树可以为空
2. 平衡二叉树的任一节点的左右子树均为平衡二叉树，且左右子树的高度差值不可以超过1

调整失衡策略

在介绍失衡策略之前，先引入一个概念，称为平衡因子(Balance Factor)，它是左子树与右子树的高度差值，当这一差值大于1说明此时二叉搜索树失衡，反之则未失衡。
那么失衡策略主要分为四类：

1. LL：在某一节点左子树根节点的左子树插入节点导致失衡（通过右旋进行调整）
2. RR： 在某一节点右子树根节点的右子树插入节点导致失衡（通过左旋进行调整）
3. LR：在某一节点左子树根节点的右子树插入节点导致失衡（左旋+右旋）
4. RL：右子树中某一节点的左子树插入节点导致失衡（右旋+左旋）
   调整失衡遵循修正最小失衡子树的规则。

最小失衡子树
在新插入的节点向上查找，以第一个平衡因子的绝对值超过１的节点为根的子树称为最小不平衡子树，也称最小失衡子树。

具体调整策略请移步 数据结构与算法之平衡二叉树

2-3树

介绍

平衡二叉树的优点是使得二叉搜索树的结构相对平衡，高度差不超过1，可以加速查询操作。但是AVL树在插入、删除操作方面会引起结构的变化，从而导致结构的多次调整（左旋右旋）。
在AVL树高度差不大于1的前提下，科学家又开始思考是否有一种树的结构是绝对平衡的呢，也就意味着没有高度差，所有的叶子节点处于同一高度，于是2-3树被提出了。
2- 代表着节点包含一个元素，其有两个分支，大小遵循左根、右。

3-代表着节点包含两个元素，其有三个分支，大小遵循左、根左、中、根右、右。

性质

1. 节点只能为2-节点或者3-节点
2. 对于2-节点其有一个数据，两个指针节点
3. 对于３-节点其有两个数据，三个指针节点
4. 所有叶子节点的高度保持一只高度

2-3树的构造

主要以插入操作进行讲解2-3树的构造。
因为创建过程其实就是一个插入过程。
而插入过程又可以根据节点的不同分成四种，根据刚才2-节点，3-节点的定义，其实这一插入过程相对容易理解一些。

1. 向2-节点插入新节点（将2-节点转变成3-节点，并将元素插入其中即可。）
   
2. 向仅有一个3-节点的树中插入新节点（3-节点临时变成4-节点，再转化成３个2-节点即将4-节点的中间元素变为左右元素的父节点，并与原3-节点的父节点合并为3-节点）
   
3. 向一个父节点为2-节点的3-节点中插入新节点（与2有些类似）
4. 向一个父节点为3-节点的3-节点插入新节点（相当于做了两次向父节点为2-节点的3-节点插入新节点）
   

其实主要就是两点：

1. 2-节点转变成3-节点
2. 3-节点转变成4-节点，4-节点转变成3个2-节点（根左、根中、根右 => 左、根、右）

具体内容可以移步数据结构与算法之2-3树
下面就开始介绍我们的红黑树了。

红黑树

定义

红黑树，面试重灾区，我们最经常听见但是似乎从未用过的一种数据结构，实际上它就在我们身边，举个例子，我们用到哈希表，当存入键值对达到一定量级时，就转变成了红黑树结构。
下面依然看一下红黑树在维基百科上的简介。

维基百科
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在O(log n)时间内完成查找、插入和删除，这里的n是树中元素的数目。

红黑树的好处不言而喻，下面我们就从它的性质入手，类比与2-3树进行介绍。

性质

1. 节点只有红色或者黑色
2. 根节点一定是黑色
3. 叶子节点一定是黑色空节点（NULL节点）
4. 红色节点的左右子节点均为黑色节点
5. 任一节点到其叶子节点上的黑色节点数目一致

2-3树与红黑树等价转换

为什么说2-3树与红黑树可以算是等价的呢？
下面来对照看一下：

1. 2-节点对应着普通的黑色节点。
2. 而3-节点则对应发生变化，根左变为根右元素的左节点，根左节点对应红色节点，根右对应黑色节点。

也就是说，红节点只会出现在3-节点转变成2-节点的时候发生，即根左转变的节点变成红色，然后3-节点的三个子节点有两个转变为了红节点的左右黑色子节点，剩余一个变成了根右元素的子节点，同样是黑色，那么在这棵树的局部满足了红黑树的第五点性质，而这一点也是最重要的一点。
红黑树的第五条性质保证了红黑树具有2-3树的平衡性，也就是平衡二叉树的特性，即红黑树需要通过变色和旋转达到了AVL树的平衡特点。

红黑树的创建

那么就以上图中的数组[59,55,50,45,30,29,28,25,15,10,5]进行红黑树的创建描述吧。
这里需要指出，除了根节点，之后插入到红黑树的节点，我们都以红色节点进行插入，因为：

1. 在2-3树中，对于一个无叶子节点的2-节点，其插入新节点，会转变成3-节点，也就对应了上述2-3树与红黑树等价的第二点。
2. 这样也保证了红黑树性质的第五点。
   
   这里只以前三个元素作为例子说明一下流程，具体过程变色以及旋转处理其实十分复杂，但是我们只需要知道按照红黑树的五点要求，以及参考平衡二叉树和2-3树的调整策略、构建过程，总能构建出一个完美的红黑树，只是过程过于复杂，博主也没有十分通透，只好介绍至此。

红黑树优点

虽然说由于2-3树3-节点转化为红黑树时会将路径增长，红黑树的效率可能相对AVL树来说会低一些，但是它的优势主要在于插入与删除操作，这一点可以参考2-3树的一些操作，详见上面博客地址。相较于AVL树，红黑树的调整平衡的策略更多，也就相应的使得红黑树的自平衡更容易调整。

总结

AVL树、2-3树是红黑树的基础，掌握了2-3树对于理解红黑树有着很大的帮助。
同时我们注意到，2-3树与红黑树有着很大的优势，树的平衡度高，对于查询有着很大的优势，然而对于2-、3-节点（红节点、黑节点）的维护以及树结构的稳定性会使得该数据结构变得十分复杂，其底层实现仍需慢慢揣摩，但更重要的是懂得他的运用场景。

如有兴趣可以关注我的微信公众号，每周带你学一点算法与数据结构。