红黑树（基于2-3树等价）
红黑树是一种常见的自平衡二叉查找树，经常使用于关联数组、字典，在各类语言的底层实现中被普遍应用，Java的TreeMap和TreeSet就是基于红黑树实现的。本篇分享将为读者讲解红黑树的定义、建立和用途。
一、红黑树的定义
（1）每一个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每一个叶子节点是黑色。
（4）若是一个节点是红色的，则它的子节点必须是黑色的
（5）从任意一个节点到叶子节点，通过的黑色节点是同样的。
我直接抄了一段算法导论里对于红黑树的描述，不少有关红黑树的讲解和我同样，上来就抄一段生硬的描述，让人摸不着头脑，本篇笔记但愿可以由浅入深地、渐进式地引导读者了解红黑树，所以咱们会先从红黑树的意义提及，为何咱们须要一棵红黑树。
二、平衡二叉查找树
咱们以这样一个数组为例[42，37，18，12，11，6，5]构建一棵二叉搜索树，因为数组中任意一点均可以做为二叉搜索树的根节点，所以这棵二叉搜索树并不惟一，咱们来看一个极端的例子（以42做为根节点，顺序插入元素）
平衡二叉查找树：简称平衡二叉树。是由前苏联的数学家 Adelse-Velskil和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具备以下几个性质：
性质1. 能够是空树。
性质2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，而且高度之差的绝对值不超过 1.
三、2-3树
通过上面的例子，咱们能够知道，构建一棵平衡的二叉搜索树的关键在于选取“正确”的根节点，那么咱们如何在每次构建平衡二叉搜索树时都能选取合适的根节点呢，这里就要用到另外一种重要的树：2-3树，2-3树和红黑树是等价的，理解2-3树对理解红黑树以及B类树都有很大的帮助。
2-3树的基本概念
所谓2-3树，即知足二叉搜索树的性质，且节点能够存放一个元素或者两个元素，每一个节点有两个或三个孩子的树。
性质1. 满足二叉搜索树的性质
性质2. 节点能够存放一个或两个元素
性质3. 每一个节点有两个或三个子节点
2-3树本质上也是一棵搜索树，和二叉搜索树的区别在于，2-3的节点可能存放2个元素，并且每一个节点可能拥有3个子节点。2-3树存在如下两种节点：2-节点（存在两个子节点）和3-节点（存在3个子节点）的数据结构
2-3树的建立
下面咱们来看如何建立一棵2-3树，建立2-3树的规则如下：
规则1. 加入新节点时，不会往空的位置添加节点，而是添加到最后一个叶子节点上
规则2. 四节点能够被分解三个2-节点组成的树，而且分解后新树的根节点须要向上和父节点融合
咱们依然使用上面的示例数组[42，37，18，12，11，6，5]，依然使用顺序插入的方式来构建2-3树，看看是否会出现退化成链表的状况。
咱们能够注意到，在建立2-3树的每一步中，整棵树始终保持平衡。既然2-3树已经可以保持自平衡，为何咱们还须要一棵红黑树呢，这是由于2-3树这种每一个节点储存1~2个元素以及拆分节点向上融合的性质不便于代码操做，所以咱们但愿经过一些规则，将2-3树转换成二叉树，且转换后的二叉树依然能保持平衡性。
2-3树和红黑树的等价性
本小节咱们以一棵2-3树为例，将其从2-3树转换成为一棵红黑树，从而学习了解2-3树和红黑树的转换规则，并体会2-3树和红黑树之间的等价性。
对于2-3树中的2-节点来讲，自己就和二叉搜索树的节点无异，能够直接转换为红黑树的一个黑节点，可是对于3-节点来讲，咱们须要进行一点小转换：
-
将3-节点拆开，成为一棵树，而且3-节点的左元素做为右元素的子树
-
将原来的左元素标记为红色（表示红色节点与其父节点在2-3树中曾是平级的关系）
咱们来转换一棵复杂点的2-3树，根据上边的两条转换规则，咱们将2-节点直接转换为黑色节点，将3-节点拆成一棵子树，并给左元素标上红色，这个过程应该不难理解，另外咱们能够注意到，因为红色节点是由3-节点拆分而来，所以全部的红色节点都只会出如今左子树上。
四、红黑树的性质和复杂度分析
红黑树基本性质分析
在完成了2-3树到红黑树的转换以后，咱们从新审视红黑树的五条性质：
(1) 每一个节点或者是黑色，或者是红色
这是红黑树的定义，没什么好说的。
(2) 根节点是黑色
根节点要么对应2-3树的2-节点或者3-节点，而这二者的根节点都是黑色的，于是根节点必然是黑色。从上图2-3树节点和红黑树节点对应关系就能很容易看出来
(3) 每一个叶子节点是黑色
注意，这里的叶子是指的为空的叶子节点，上图的红黑树的完整形式应该是这样的：
(4) 若是一个节点是红色的，则它的子节点必须是黑色的
因为红黑树的每一个节点都由2-3树转换而来，红色节点链接的节点必然是一个2-节点或者3-节点，而不管是2-节点仍是3-节点，其根节点都是黑色的，所以红色节点的子节点必然是黑色的
(5) 从任意一个节点到叶子节点，通过的黑色节点是同样多的
这是红黑树最重要的一条性质，也是红黑树的价值所在。因为红黑树是由2-3树转换而来，所以每个黑色节点必然对应2-3树的某个2-节点或者3-节点，所以红黑树的黑节点也能拥有2-3树的平衡性。若是对这条性质还不够理解，能够对着上文2-3树和红黑树的转换图再理解理解。
红黑树时间复杂度分析
网上有不少使用数学概括法来计算红黑树时间复杂度的证实了，这里就再也不赘述。咱们能够简单思考一下，对于一棵普通的平衡二叉搜索树来讲，它的搜索时间复杂度为O(logn)，而做为红黑树，存在着最坏的状况，也就是查找的过程当中，通过的节点全都是原来2-3树里的3-节点，致使路径延长两倍，时间复杂度为O(2logn)，因为时间复杂度的计算能够忽略系数，所以红黑树的搜索时间复杂度依然是O(logn)，固然，因为这个系数的存在，在实际使用中，红黑树会比普通的平衡二叉树（AVL树）搜索效率要低一些。
五、红黑树的建立
上文中咱们讲解了如何由2-3树转换一棵红黑树，下面咱们就来看看如何不通过2-3树直接建立一棵红黑树，毕竟咱们写代码的时候不能先建立一棵2-3树再转化成红黑树吧。咱们回想一下2-3树的建立规则：
规则1. 加入新节点时，不会往空的位置添加节点，而是添加到最后一个叶子节点上
规则2. 四节点能够被分解三个2-节点组成的树，而且分解后新树的根节点须要向上和父节点融合
简单来讲，2-3树的建立分为**「融合」和「拆分」两步**，为了实现这两步，咱们须要在建立二叉树的基础操做上增长另外几个操做，分别是：
-
保持根节点黑色
-
左旋转
-
右旋转
-
颜色翻转
保持根节点黑色和左旋转
因为咱们往2-3树插入节点时作的都是融合，所以新加入的节点和原位置的节点是平级关系，因此咱们往红黑树里增长节点的时候，增长的都是红色节点。
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
// 左旋转
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
颜色翻转
上一小节咱们介绍了左旋转的情形，其实左旋转的情形就对应着2-3树中生成3-节点的情形，也就是从2-节点到3-节点这一步，那么从3-节点到4-节点，再到拆分4-节点的这一步又对应红黑树的什么操做呢，咱们来看一个简单的例子。
咱们以一棵已经拥有两个节点的红黑树为例，如今这一红一黑两个节点就对应了2-3树的3-节点[37 42]，咱们加入新的红色节点66，节点66按照二叉搜索树的原则，暂时加在节点42的右子树上。以前咱们说过，红色节点表示该节点与其父节点在2-3树中是平级关系，也就是说这种左右子节点都是红色节点的状况其实对应了2-3树中临时的4-节点。固然，咱们知道红色的节点是只能出如今左子树上，因此咱们须要进行一些变形。
// 颜色翻转
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
右旋转
咱们刚才插入了节点66，66比42大，所以被加入到了节点42的右子树上，而后咱们使用颜色翻转就完成了转换。然而节点并不老是被添加到右子树上，好比说插入节点12，12小于37，所以节点12被加入到37的左子树上：
// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
// 右旋转
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
其余状况
咱们经过颜色翻转和右旋转，解决了往3-节点添加节点的两种状况，分别是大于b节点状况，小于a节点的状况，那么若是插入的节点大于a而小于b呢。
[37 40 42]做为例子：
流程总结
咱们总结一下以上三种情形，会发现其实红黑树插入节点不过五种形式
-
插入到一个2-节点，且节点小于该2-节点
-
插入到一个2-节点，且节点大于该2-节点
-
插入到一个3-节点，且插入节点小于3-节点的两个节点
-
插入到一个3-节点，且插入节点大于3-节点的两个节点
-
插入到一个3-节点，且插入节点在3-节点的两个节点之间
其实这五种形式均可以用一个逻辑链条来表示，咱们回顾一下6.4里，插入的节点小于a大于b的转换过程，出于通用性，我把具体数字隐去了。
咱们发现，这个流程已经包含了以上五种状况，若是咱们插入的节点大于a也大于b，那么咱们能够直接跳到第四步，而后进行颜色翻转；若是咱们插入的节点小于a也小于b，那么跳到第三步；若是插入节点在ab之间，那么就对应第二步。
有了这个逻辑流程，咱们的代码一会儿清晰起来，咱们只须要经过几个条件判断，就能描述红黑树全部旋转方式，下面咱们来写一段伪代码：
// 向以node为根的红黑树中插入元素(key, value)，递归算法
// 返回插入新节点后红黑树的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value); // 默认插入红色节点
}
if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
// 若是右节点为红色,左节点为黑色, 那么进行左旋转, 对应状况2
if (isRed(node.right) && !isRed(node.left))
node = leftRotate(node);
// 若是左节点为红色,左节点的左节点也为红色, 那么进行右旋转, 对应状况3
if (isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);
// 若是左右节点都为红色, 那么进行颜色翻转, 对应状况4
if (isRed(node.left) && isRed(node.right))
flipColors(node);
return node;
}
到这里，咱们就实现了红黑树的全部平衡操做，从这个过程当中，咱们还能得出一个重要结论，即红黑树任何不平衡，都能在3次旋转内获得解决，这也就是红黑树相较AVL树的优点所在。
六、红黑树和AVL树的比较
-
AVL树比红黑树更为平衡，其搜索效率也好于红黑树, 通过咱们以前的分析能够知道, 红黑树在最坏的状况下搜索时间复杂度为2logn，大于AVL树的logn。AVL树是严格平衡，红黑树只能达到“黑平衡”，即从任意节点出发到叶子节点通过的黑节点数量相同，但通过的红色节点数量不肯定，最差的状况下，通过的红色节点和黑色节点同样多。
-
红黑树增删节点的性能优于AVL树，当咱们往红黑树增长节点或删除节点引发红黑树不平衡，咱们只须要最多三次旋转就能解决，而相同条件下，AVL树的旋转次数要多于红黑树，所以红黑树在增删节点上相较于AVL树更优
七、总结
最后作个归纳，红黑树是以牺牲部分搜索性能换取增删性能的折中方案，用非严格的平衡，换取旋转次数的减小。在实际使用中，若是所维护的树须要频繁增删节点，红黑树会更加合适，反之，则适合AVL树。
关注公众号 ，专注于java大数据领域离线、实时技术干货定期分享！如有问题随时沟通交流！ www.lllpan.top
