原标题：大厂必备技能：数据结构树之红黑树
树这种数据结构是比较复杂的，相比数组和链表而言，树这种全新的数据结构充分将数据的增删改查效率发挥到极致，不再像数组和链表这两种数据结构那么两极分化，那么极端化。对于数据结构来说，树结构让数据的读写效率相对高效且趋于平衡，是一种相对比较完美的数据结构。
前面呢，咱们主要介绍了一种比较简单的树，叫做二叉查找树，就是一个结点只能存在最多两棵子树，也就是左、右子树。在插入数据的时候，会从根结点依次比较，如果待插入结点值比当前结点小，就递归左子树，如果待插入结点值比当前结点大，就递归右子树。这样而言，通过前、中、后序遍历，我们就能以比较高效的方式查找到咱们想要的结点。对于二叉树的细节，在此就不再一一赘述了，有需要的同学可以看看我之前写得文章。
今天咱们学习一种新的树，也是咱们很熟悉，尤其是咱们学Java的同学经常听到过得一种树，它就是红黑树。
我相信大家知道这个概念64之后且单条链表结点超过8，链表结构就会转化成红黑树）。
还是对红黑树有比较详细的了解，如果让你设计HashMap，你能真正明白其中的奥妙与智慧吗？在回答面试官的问题时，你能够口若悬河，用自己的技术征服一切，用自己过硬的实力拿到一个一个属于自己的offer。
还是靠背去碰运气，自己背得辛苦，面试官问题稍微一改变或者一深入就显得有心无力呢？在本篇文章中，咱们会详细讲解一下红黑树，让咱们不知其然，更能知其所以然，让咱们的技术更上一个档次，达到一种脱胎换骨的蜕变。
一、原始二叉查找树的弊端
二叉查找树能够提高咱们的数据读写效率是毋庸置疑的，比如对下面的这棵树：
这棵树是一棵非常理想的满二叉树，此时咱们的搜索效率极高，比如查询20这个结点咱们只需要查询3次即可，先跟根节点10比，发现待查询结点的值比10大，就查找10的右子树，再次发现子树根节点16同样比待查询结点小，则继续查找16的右子树，这个时候20跟待查询结点值相等，此时直接返回即可。在这个时候我们明显可以看出树这种结构的优势，比如咱们这棵树一共有7个结点，如果是链表，最坏的情况明显要查询7次，但是咱们的树只需要查询3次。查询效率只跟咱们树的高度有关，高度越低，查询次数越少。
我们从上一步得出结论，树的查询效率只跟当前树的高度有关，咱们最坏的情况，也只会查询当前高度所对应的次数，那么此时，我们的树既不是满二叉树也不是完全二叉树呢，比如咱们有这样一棵树：
可以看出这棵树特别极端，也是咱们二叉树最极端的一种情况，这个时候咱们二叉树的高度为8，那么查询效率最坏的情况也是8，那么细心的同学有没有发现，其实这就是链表。咱们二叉树的极端也就是链表，对于链表的查询效率咱们就不多说了，而且这种情况，咱们此时的二叉树比链表还要低，因为链表只需要从头遍历到尾，咱们的二叉树每一次层级都要比较左右子结点，效率更加惨不忍睹。
那么针对这种情况，咱们怎么解决呢，也就是树这种数据结构比较重要的一个内容也就是树的平衡。
二、平衡树
通过以上的知识，我们可以知道满二叉树以及完全二叉树是查询效率最高的一种情况。那么何为平衡化？就是指咱们的二叉树在不满足完全二叉树的情况下将其转化为一棵近似完全二叉树甚至满二叉树的过程，进而降低了咱们二叉树的高度，在前面我们知道二叉树的查询效率只受高度影响，所以通过平衡化的操作让咱们的二叉树高度更低，进而提升咱们二叉树的查询效率。
那么什么是平衡树呢？平衡树的概念就是指对于一棵二叉树而言，其任意结点的左右子树的高度应该小于等于1，让树的左右子树都得到充分利用。所谓树的平衡化，就是将一颗不稳定的树尽可能的转化为一棵趋近完全二叉树的过程，进而大幅度发挥树结构的真正作用与效率。例如像下面这棵树就是一棵平衡树：
对咱们这棵树而言，其实就是一棵完全二叉树，满足所有结点的左右子树高度差都小于等于1。比如对根节点25号结点，左右子树高度差为0，对15结点来说，左右子树高度差同样为0，对48号结点来说，左右子树高度差为1，叶子结点就不用说了，4、20、35左右子树都为空，高度差均为0。所以符合平衡树的定义，所以整棵树是一棵平衡树。
而对这棵树而言，如下图所示：
对根结点25号结点来说，左右子树高度差为2，这显然是一棵非平衡树，查询效率肯定会有所影响，比如我们这么转换，它就会变成一棵平衡树。
对于平衡树的概念咱们先说这么多，平衡树的作用是为了提高二叉树查询效率而出现的一种结构，下面我们用2-3查找树的思想来解决树的平衡问题。
三、2-3查找树
2-3查找树是一种平衡思想，主要用于解决树的平衡问题，那什么是2-3查找树呢？我们需要重点理解2-3查找树、二和三所表示的含义。
二表示2-结点，2-结点就表示一个结点只存一个有效key，从这个结点最多引出两个子连接，如下图所示：
如上图所示，对15号结点，当前结点只存储15这个有效key，从15号结点最多可以延伸出两个子连接，这种结点咱们称为2-结点。比2-结点小的咱们放在左连接，比2-结点大的结点咱们放在右子结点，和二叉树的插入规则一样。如下图所示：
那么什么是三呢？顾名思义，就是3-结点，3-结点表示一个结点中存在2有效key，通过这个有效key能够延伸出3条连接。如下图所示：
上图表示一个3-结点，可以看出一个3-结点存在2个有效key，2个有效key的位置左小右大，对它的子连接来说，比当前3-结点左边的key也就是15小的放在连接1的位置，基于15-30范围内的放在连接2的位置，比当前3-结点右边的key，也就是30还大的则放在连接3的位置。下图就是一个常见的3-结点：
有了以上的知识，我们对2-结点、3-结点有了基础的了解，那么就可以来认识咱们的2-3查找树了，结合我们之前讲得二叉树，我们可以这么说，二叉树是由2-结点组合起来的一棵树，那么2-3查找树则是由2-结点以及3-结点一起组合起来得一棵树。
我们既然说2-3查找树主要是解决树的平衡的，那么它是怎么解决的了，咱们来看看它的添加过程。
就拿我们刚开始那个极端10->9->8>…>3这棵树做例子，咱们进行2-3查找树的添加：
第一步：添加第一个结点，我们添加第一个结点到2-3查找树，第一次添加树中没有一个结点，将其直接作为根结点添加即可。如下图所示：
第二步：咱们添加第二个结点9，这个时候添加的规则和二叉树的添加规则一样，我们需要判断待添加结点和已有结点的大小，此时9比10小，照理说应该将其添加到10号结点的左子树，但是因为咱们2-3查找树可以存储3-结点，此时需要将2-结点10转化为3-结点，又因为9比10小，此时直接添加到10的左边即可。如下图所示：
第三步：咱们添加第三个结点8，这个时候需要跟9和10比较，发现8比9小，所以咱们应该将其添加到9和10这个3-结点的左连接。如下图所示：
这种添加规则看似没问题，但是却并不是咱们2-3查找树的添加规则，如果咱们要添加的结点是个3-结点，此时并不是将其添加到其子连接，而是将其转化为1个临时的4-结点，即一个结点3个key，4个子连接。所以正确的添加结果应该是这样。如下图所示：
又因为咱们的2-3查找树只能有2-结点和3-结点，所以此时咱们需要将4-结点进行分解，将中间的key作为父结点将其转化为3个2-结点。如下图所示：
第四步：添加第四个结点7，这个时候和二叉查找树的添加规则一样，先拿待添加结点7和根节点9做比较，7比9小，这时候继续查找9的的左子树，用8和7继续比较，发现7仍然比8小，这个时候就继续递归8的左子树，此时发现8已经是整棵树的叶子节点了，按照二叉树的添加规则，此时我们应该将7作为左子结点添加到8号结点下面。但是2-3查找树能用3-结点表示，所以此时我们不应该添加为子结点，应该将两个key合并为一个3-结点，又因为7比8小，所以在最新的3-结点中，7左8右。如下图所示：
第五步：添加第五个结点6，这个时候再根据二叉树的添加规则，发现它比7小，应该是作用在7，8号对应的3-结点，此时6比7小，这个时候咱们再把6，7，8合并为一个临时的4-结点。如下图所示：
下面同样的套路，对这个临时的4-结点进行分解，将7提取为6和8号结点的父结点，但是这时候已经存在根节点了，所以此时根节点就会由2-结点转化为3-结点。此时就会变成如下图的结构：
第六步：添加第六个结点5，5这个结点此时应该添加到6号结点左边，同理将2-结点转化为3-结点。如下图所示：
第七步：添加第七个结点4，这个时候将5，6对应的3-结点转化为临时的4-结点，如下图所示：
接下来进行4-结点的分解，结果如下图所示：
我们可以看出一旦4，5，6所对应的4-结点一经过分解过后，5号结点向上提升过后，根节点已经由事先的3-结点转化为了4-结点，这个时候我们需要将根结点进行分解，如下图所示：
最后一步：添加3号结点，此时应该添加到4这个位置，因为4号结点是2-结点，此时将3，4号结点一起合并为一个3-结点，最终整棵树的结构如下所示：
通过以上的添加步骤，咱们可以看出咱们形成的一棵树是一棵满二叉树，那么它的查询效率不用说应该是效率最高的，咱们将一条极不平衡的链表转化为了一棵满二叉树。之前的查询效率最坏为8次，现在最多为3次。那么查询效率不用说，咱们的2-3查找树肯定是大大提升，并且将一棵很不平衡的树转化为了一棵特别平衡的满二叉树结构。
通过上面的例子，我们可以得出一下结论：
1.任意叶子结点到根节点的路径长度都是相等的；
2.分叉结点为4-结点进行分解时，咱们树的高度并不会发生变化，但是会增加咱们父结点的有效key，当且仅当咱们的根节点为4-结点时，分解结点的时候咱们树的高度才会加1；
3.二叉树的生长是从上到下，而咱们的2-3查找树却是自下到上的。
2-3查找树是实现树平衡的一种思想，具体的实现就是咱们听说过的红黑树，红黑树其实就是2-3查找树的一种落地实现方式，接下来咱们就揭开红黑树神秘的面纱。
四、红黑树
红黑树大家想必都听过，那么说了这么多，什么是红黑树呢？红黑树实质就是一棵自带平衡的二叉树，也是一棵变相的2-3查找树。那么我相信有同学就有疑问了，红黑树是二叉树，只能存在2-结点，那么它怎么表示3-结点的呢？咱们继续往下看。
4.1概念
红黑树实质是一棵2-3查找树，因为作为二叉树本身不能表示3-结点，所以在表示3-结点时使用了特殊的手段也就是结点的颜色表示。
红黑树一共有两种颜色，顾名思义，一个结点要不是红色的，要不就是黑色的。黑色结点表示二叉树中的普通结点，红色结点和它的父结点（不计父结点颜色）一同形成一个N-结点。
简单的来说就是红黑树的红色结点，和它的父结点一同构成N-结点，这句话可能有点抽象，咱们通过下面的图加深理解。
比如对这样两个结点来说，50是黑色结点，它不用管，35号结点为红色结点，那么此时需要将它和它的父节点看作一个3-结点。对应咱们2-3查找树这样的一个3-结点，如下图所示：
再比如这种结构，如下图所示：
又比如这种结构：
那么我们将其还原成2-3查找树，对应的结点也就是一个4-结点。如下图所示：
除了红色结点，还有黑色结点相互连接的情况，黑色结点和它的父结点咱们不需要转化，直接就是最原始的2-结点。如下图所示：
那么像这种黑色结点，依然表示2-3查找树的2-结点，就不用再做结点的合并操作了，咱们还原成2-3查找树的模型为：
4.2红黑树的规则
1.根节点始终是黑色结点。
这句话也好理解，我们都说一个红色结点跟它的父结点可以合并为一个N-结点，此时咱们的根节点都没有父结点了，那么肯定就不可能再是红色结点。
2.所有黑色结点构成完全二叉树，所有空链接到根节点的黑色结点数量是相等的。
比如将我们最开始的那棵10->9->8>…>3对应的2-3查找树，如下图所示：
咱们用红黑树来表示，如下图所示：
可以看出我们忽略红节点不看，所有路径上的黑色结点数量都是相等的，什么叫做空链接呢？其实就是叶子结点的下一结点，因为它本身并不存在，就用空表示。
3.一条路径上不能出现两个连续的红色结点：
这句话怎么理解了，我们通过下面的图进行理解：
比如对这样一颗树而言，对于80号结点，左子树出现了连续的两个红色结点。我们在上面的知识讲到过红色结点的意义是需要将其和其父结点合并为一个N-结点，那么这是50、65、80就是一个4-结点。我们将其还原为2-3查找树的模型，如下图所示：
如果此时存在两个连续的红色结点，可以看出最终的结点为一个4-结点。在2-3查找树中不能存在4-结点，所以说一条路径不能出现连续的两个红色结点。
4.红色结点只能出现在左子结点，而不能成为右子结点。
4.3红黑树的添加思路
下面了，我们结合2-3查找树的思想来讲解一下红黑树的添加思路，我们还是使用10->9->8->7->…->3这棵链表树来进行创建红黑树：
第一步：添加第一个结点10，此时红黑树中没有一个结点，将其作为红黑树的根结点即可，因为根结点的颜色始终为黑色，将其标记为黑色即可。如下图所示：
此时还原出来的2-3查找树如下图所示：
第二步：继续添加第二个结点9，此时2-3查找树是合并为3-结点。如下图所示：
那么对应的红黑树，9这个结点就是红色结点，如下图所示：
第三步：继续添加8号结点，此时2-3查找树会临时转化为4-结点。如下图所示：
此时在红黑树中，8号结点仍然是红色结点。如下图所示：
第四步：在2-3查找树中，遇到临时4-结点，需要进行分解结点，将一个4-结点分解为3个2-结点。如下图所示：
那么在红黑树应该怎么操作呢，此时在红黑树中，对于这种情况，也就是一条路径上出现了两个连续的红色结点。此时对应的操作叫做右旋。下图是右旋之前的红黑树：
第五步：右旋和变色平衡思路
右旋是红黑树中解决平衡的一个很重要的操作，比如有这么一棵子树，如下图所示：
比如在这个子树之中，对88号这个结点来说，出现了连续的两个连续的红色结点，此时对应的2-3查找树中出现了临时的4-结点。这个时候在红黑树通过右旋操作来处理这种情况。
此时对88号结点这棵子树进行右旋操作，右旋的操作也并不复杂，我们设88号结点为x，那么右旋的步骤为x.left=x.left.right;x.left.right=x;x.left.color=x.color,x.color=red。右旋的结果如下图所示：
这时候将这棵树还原成2-3树模型为：
这个时候66、77、88又构成了一个4-结点，这个时候造成4-结点的原因是在上一步左旋的时候将66和88标记成为了红色结点。此时针对这种情况的4-结点，我们就不用通过旋转的方式进行处理了，需要将这个4-结点的每一个key对应红黑树的结点进行变色操作（根结点除外，如果参与的结点存在根结点，根结点永远都是黑色）。变色后的红黑树如下：
此时77号结点为红色，那么将77号结点以及它的父结点99看作一个3-结点。那么此时还原成2-3查找树模型就为：
第六步：对10号根结点进行右旋，此时咱们加入8号结点后，形成的树结构为：
那么此时10号结点出现了两个连续的左子结点，此时在2-3查找树中对应一个4-结点。此时需要进行右旋，那么此时对应的红黑树为：
此时出现9号结点的两个子结点的颜色都为红色，此时需要进行变色，变完色后的红黑树模型如下：
因为此时9号结点作为咱们整棵树的根结点，上面也讲过：咱们红黑树根结点的颜色无论何时一定为黑色，所以最终咱们需要将9号结点还原为黑色，最终对应的红黑树结构如下图所示：
那么还原成2-3树实质上就是对临时4-结点的分解，如下图所示：
第七步：添加第四个结点7，这时候我们应该添加的位置应该是8号结点，此时将其合并为一个临时的3-结点，即7号结点的颜色为红色。如下图所示：
第八步：添加第五个结点6，这时候我们应该添加的位置应该是4号结点，此时将6、7、8合并为一个临时的4-结点，即6号结点的颜色也为红色。如下图所示：
此时6、7、8号结点一共构成一个4-结点，此时对应的2-3查找树模型为：
此时咱们6、7、8所对应的4-结点需要进行分解，我们需要将红黑树进行右旋，此时右旋后的红黑树模型为：
此时又出现7号结点两个子结点都为红色结点的情况，此时还是4-结点，此时需要进行变色处理。那么经过右旋和变色两个操作后，最终咱们形成的红黑树模型如下图所示：
此时7号结点为红色，相当于7号结点和9号结点一起构成了一个3-结点，那么此时对应的2-3查找树模型为：
第九步：添加第六个结点5，此时5这个结点应该添加的位置为6号结点，此时两个结点合并为一个3-结点，此时5号结点的颜色为红色。如下图所示：
第十步：添加第七个结点4，此时4这个结点应该添加的位置为5号结点，此时三个结点合并为一个4-结点，此时4号结点的颜色为红色。如下图所示：
第十一步：此时4、5、6三个结点构成一个临时的4-结点，我们需要进行右旋操作，具体思路和上面的一样，右旋后的结果为：
下一步进行变色操作，最终形成的红黑树模型为：
此时，5、7和9号结点同时又合并为一个4-结点，又需要对9号结点进行右旋。此时的红黑树模型为：
这个时候5、7、9三个结点又合并为一个临时的4-结点，这个时候进行变色处理。变色后的红黑树如下图所示：
又因为此时咱们的7号结点为根结点，故需要再把7号结点修改为黑色。最终的红黑树模型图如下：
第十二步：添加最后一个结点3，此时算出3号结点的位置应该在4号结点附近，此时将4号结点和3号合并成一个3-结点，所以3号结点的颜色为红色，如下图所示:
第十三步：以上步骤完成了咱们所有结点的添加，最终形成的红黑树结构为：
转化为一棵最原始的二叉树则为：
可以看出：通过红黑树转化的二叉树最大左右子树的高度差为1，正好构成一棵平衡树。
4.4红黑树的实现
4.4.1 创建结点颜色枚举类
在上面的知识中，我们知道在红黑树中每个结点都具有颜色，要不是红色，要不就是黑色。所以针对每个结点的颜色，咱们创建一个枚举类来表示：
package com.ignorance.tree.node;
public enum Color {
RED(true,”red”),
BLACK(false,”black”);
private Boolean flag;
private String desc;
Color(Boolean flag, String desc) {
this.flag = flag;
this.desc = desc;
}
public Boolean getFlag() {
return flag;
}
public void setFlag(Boolean flag) {
this.flag = flag;
}
public String getDesc() {
return desc;
}
public void setDesc(String desc) {
this.desc = desc;
}
public static Color getColorByFlag(Boolean flag){
Color targetColor = null;
Color[] values = Color.values();
for (Color color : values){
if (flag == color.flag){
targetColor = color;
break;
}
}
if (targetColor == null){
throw new RuntimeException(“【当前结点暂不支持这种颜色…】”);
}
return targetColor;
}
}
4.4.2 定义红黑树结点类
package com.ignorance.tree.node;
public class Node<K extends Comparable<K>,V> {
private K key;//当前结点的key
private V value;//当前结点的value
private Color color;//当前结点的颜色
public Node<K,V> left;//当前结点的左子结点
public Node<K,V> right;//当前结点的右子结点
public Node(K key, V value, Color color) {
this.key = key;
this.value = value;
this.color = color;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public Color getColor() {
return color;
}
public void setColor(Color color) {
this.color = color;
}
@Override
public String toString() {
return “Node{” +
“key=” + key +
“, value=” + value +
“, color=” + color +
};
}
}
4.4.3 创建红黑树核心类
红黑树添加方法
有了以上的添加思路，咱们按照添加的思路实现具体的代码即可，核心代码如下：
package com.ignorance.tree;
import com.ignorance.tree.node.Color;
import com.ignorance.tree.node.Node;
public class RedBlackTree<K extends Comparable<K>,V> {
//根结点
private Node<K,V> root;
//红黑树中有效结点个数
private int size;
/**
* @return
*/
public Node<K, V> getRoot() {
return root;
}
/**
* @return
*/
public int getSize() {
return size;
}
/**
* 向整个树中添加结点
* @param key
* @param value
*/
public void put(K key,V value){
this.root = put(this.root,key,value);
//根结点的颜色始终为黑色
this.root.setColor(Color.BLACK);
}
/**
* 向x子树添加结点
* @param x
* @param key
* @param value
* @return
*/
private Node<K,V> put(Node<K,V> x,K key,V value){
//有效结点自增
if (x == null){
size++;
//每次添加新结点时，都将该结点的颜色暂时设置为红色
return new Node<>(key,value,Color.RED);
}
int cmp = key.compareTo(x.getKey());
/**
* 二叉树添加规则
* 待添加结点和当前结点作比较
* 如果待添加结点的key值比当前结点key小，则递归当前结点的左子树
* 如果待添加结点的key值比当前结点key大,则递归当前结点的右子树
* 如果待添加结点的key值跟当前结点相等，则直接修改当前结点的value
*/
if (cmp < 0){
x.left = put(x.left,key,value);
}else if(cmp > 0) {
x.right = put(x.right,key,value);
}else {
x.setValue(value);
}
/**
* 当前结点如果出现两个红色左子结点的时候
* 需要通过右旋来进行平衡
*/
if(x.left != null && x.left.left != null){
if (x.left.getColor() == Color.RED && x.left.left.getColor() == Color.RED){
x = rightRotate(x);
}
}
/**
* 如果当前结点左右子结点都不为空的时候
*/
if (x.left != null && x.right != null){
/**
* 针对当前结点的两个子结点
* 如果左子结点为黑色结点且右子结点为红色结点
* 则需要通过左旋来维持红黑树的平衡
*/
if (x.left.getColor() == Color.BLACK && x.right.getColor() == Color.RED){
x = leftRotate(x);
}
/**
* 针对当前结点的两个子结点
* 如果左右子结点都为红色结点
* 则需要通过变色来维持红黑树的平衡
*/
if (x.left.getColor() == Color.RED && x.right.getColor() == Color.RED){
reverseColor(x);
}
}
return x;
}
/**
* 当一个结点连续出现两个左子结点都为红色结点的时候
* 需要进行右旋来保持红黑树的平衡化
* @param x
*/
private Node<K,V> rightRotate(Node<K,V> x){
Node<K,V> h = x.left;
x.left = h.right;
h.right = x;
h.setColor(x.getColor());
x.setColor(Color.RED);
return h;
}
/**
* 当一个结点出现左子结点为黑色，右子结点为红色的时候
* 需要进行左旋来保证红黑树的平衡化
* @param x
*/
private Node<K,V> leftRotate(Node<K,V> x){
Node<K,V> h = x.right;
x.left = h.right;
h.right = x;
h.setColor(x.getColor());
x.setColor(Color.RED);
return h;
}
/**
* 当一个结点出现左右子结点都是红色结点时
* 此时需要通过反转这三个结点的颜色
* 相当于对临时4-结点的分解
* @param x
*/
private void reverseColor(Node<K,V> x){
x.setColor(Color.getColorByFlag(!x.getColor().getFlag()));
x.left.setColor(Color.getColorByFlag(!x.left.getColor().getFlag()));
x.right.setColor(Color.getColorByFlag(!x.right.getColor().getFlag()));
}
/**
* 统计整棵红黑树的高度
* @return
*/
public int getDeep(){
if (root == null){
return 0;
}
return getDeep(root);
}
/**
* 统计x子树的高度
* @param x
* @return
*/
private int getDeep(Node<K,V> x){
return x == null ? 0 : Integer.max(getDeep(x.left),getDeep(x.right) + 1);
}
}
添加方法测试：
测试代码如下：
package com.ignorance.tree.test;
import com.ignorance.tree.RedBlackTree;
import com.ignorance.tree.node.Node;
import org.junit.Test;
public class RedBlackTest {
@Test
public void testRedBlackPut(){
RedBlackTree<Integer,String> redBlackTree = new RedBlackTree<>();
redBlackTree.put(10,”李白”);
redBlackTree.put(9,”韩信”);
redBlackTree.put(8,”瑶瑶公主”);
redBlackTree.put(7,”镜”);
redBlackTree.put(6,”赵云”);
redBlackTree.put(5,”吕布”);
redBlackTree.put(4,”貂蝉”);
redBlackTree.put(3,”伽罗”);
Node<Integer, String> root = redBlackTree.getRoot();
System.out.println(“【当前红黑树的根结点为:】” + root);
int size = redBlackTree.getSize();
System.out.println(“【当前红黑树的有效结点个数为:】” + size);
int deep = redBlackTree.getDeep();
System.out.println(“【当前红黑树的高度为：】” + deep);
}
}
测试结果如下：
我们分别再写前后中序遍历来看一下当前红黑树每个结点的情况：
/**
* 前序遍历整棵红黑树
*/
public void preShow(){
if (root == null){
throw new RuntimeException(“【当前红黑树为空，不支持前序遍历】”);
}
preShow(root);
}
/**
* 前序遍历x子树
* @param x
*/
private void preShow(Node<K,V> x){
if (x == null){
return;
}
System.out.println(x);
if (x.left != null){
preShow(x.left);
}
if (x.right != null){
preShow(x.right);
}
}
/**
* 中序遍历整棵红黑树
*/
public void middleShow(){
if (root == null){
throw new RuntimeException(“【当前红黑树为空，不支持中序遍历】”);
}
middleShow(root);
}
/**
* 中序遍历x子树
* @param x
*/
private void middleShow(Node<K,V> x){
if (x == null){
return;
}
if (x.left != null){
middleShow(x.left);
}
System.out.println(x);
if (x.right != null){
middleShow(x.right);
}
}
/**
* 后序遍历整棵红黑树
*/
public void afterShow(){
if (root == null){
throw new RuntimeException(“【当前红黑树为空，不支持后序遍历】”);
}
afterShow(root);
}
/**
* 后序遍历x子树
* @param x
*/
private void afterShow(Node<K,V> x){
if (x == null){
return;
}
if (x.left != null){
afterShow(x.left);
}
if (x.right != null){
afterShow(x.right);
}
System.out.println(x);
}
测试代码：
@Test
public void testShow(){
RedBlackTree<Integer,String> redBlackTree = new RedBlackTree<>();
redBlackTree.put(10,”李白”);
redBlackTree.put(9,”韩信”);
redBlackTree.put(8,”瑶瑶公主”);
redBlackTree.put(7,”镜”);
redBlackTree.put(6,”赵云”);
redBlackTree.put(5,”吕布”);
redBlackTree.put(4,”貂蝉”);
redBlackTree.put(3,”伽罗”);
Node<Integer, String> root = redBlackTree.getRoot();
System.out.println(“【当前红黑树的根结点为:】” + root);
int size = redBlackTree.getSize();
System.out.println(“【当前红黑树的有效结点个数为:】” + size);
int deep = redBlackTree.getDeep();
System.out.println(“【当前红黑树的高度为：】” + deep);
System.out.println(“【前序遍历结果为】：”);
redBlackTree.preShow();
System.out.println(“【中序遍历结果为】：”);
redBlackTree.middleShow();
System.out.println(“【后序遍历结果为】：”);
redBlackTree.afterShow();
}
测试结果如下：
下面呢，我们可以通过debug看一下最终的红黑树长什么样子：
最终呢，我们画出对应的红黑树模型为：
下一步：我们测试一下红黑树的查找效率，先完成查找方法。核心代码如下：
/**
* 查询整棵树
* @param key
* @return
*/
public V get(K key){
return get(root,key);
}
/**
* 查询x子树
* @param x
* @param key
* @return
*/
private V get(Node<K,V> x,K key){
System.out.println(“【开始查询】”);
if (x == null){
return null;
}
int cmp = key.compareTo(x.getKey());
/**
* 二叉树查找规则
* 待查询结点和当前结点作比较
* 如果待查询结点的key值比当前结点key小，则递归当前结点的左子树
* 如果待查询结点的key值比当前结点key大,则递归当前结点的右子树
* 如果待查询结点的key值跟当前结点相等，则直接返回当前结点的value
*/
if (cmp < 0){
return get(x.left,key);
}else if(cmp > 0){
return get(x.right,key);
}else {
return x.getValue();
}
}
测试代码如下：
@Test
public void testGet(){
RedBlackTree<Integer,String> redBlackTree = new RedBlackTree<>();
redBlackTree.put(10,”李白”);
redBlackTree.put(9,”韩信”);
redBlackTree.put(8,”瑶瑶公主”);
redBlackTree.put(7,”镜”);
redBlackTree.put(6,”赵云”);
redBlackTree.put(5,”吕布”);
redBlackTree.put(4,”貂蝉”);
redBlackTree.put(3,”伽罗”);
String val1 = redBlackTree.get(3);
System.out.println(val1);
String val2 = redBlackTree.get(7);
System.out.println(val2);
}
测试结果如下：
从上面的例子中，我们将一棵完全不平衡的二叉树改造成一棵红黑树，将原来高度为8的二叉树转化为一棵高度为4的二叉树，查询效率显然得到了明显的提升。以下是红黑树核心类的全部代码，希望给同学们做个参考：
package com.ignorance.tree;
import com.ignorance.tree.node.Color;
import com.ignorance.tree.node.Node;
public class RedBlackTree<K extends Comparable<K>,V> {
//根结点
private Node<K,V> root;
//红黑树中有效结点个数
private int size;
/**
* @return
*/
public Node<K, V> getRoot() {
return root;
}
/**
当前红黑树有效结点个数
* @return
*/
public int getSize() {
return size;
}
/**
* 向整个树中添加结点
* @param key
* @param value
*/
public void put(K key,V value){
this.root = put(this.root,key,value);
//根结点的颜色始终为黑色
this.root.setColor(Color.BLACK);
}
/**
* 向x子树添加结点
* @param x
* @param key
* @param value
* @return
*/
private Node<K,V> put(Node<K,V> x,K key,V value){
//有效结点自增
if (x == null){
size++;
//每次添加新结点时，都将该结点的颜色暂时设置为红色
return new Node<>(key,value,Color.RED);
}
int cmp = key.compareTo(x.getKey());
/**
* 二叉树添加规则
* 待添加结点和当前结点作比较
* 如果待添加结点的key值比当前结点key小，则递归当前结点的左子树
* 如果待添加结点的key值比当前结点key大,则递归当前结点的右子树
* 如果待添加结点的key值跟当前结点相等，则直接修改当前结点的value
*/
if (cmp < 0){
x.left = put(x.left,key,value);
}else if(cmp > 0) {
x.right = put(x.right,key,value);
}else {
x.setValue(value);
}
/**
* 当前结点如果出现两个红色左子结点的时候
* 需要通过右旋来进行平衡
*/
if(x.left != null && x.left.left != null){
if (x.left.getColor() == Color.RED && x.left.left.getColor() == Color.RED){
x = rightRotate(x);
}
}
/**
* 如果当前结点左右子结点都不为空的时候
*/
if (x.left != null && x.right != null){
/**
* 针对当前结点的两个子结点
* 如果左子结点为黑色结点且右子结点为红色结点
* 则需要通过左旋来维持红黑树的平衡
*/
if (x.left.getColor() == Color.BLACK && x.right.getColor() == Color.RED){
x = leftRotate(x);
}
/**
* 针对当前结点的两个子结点
* 如果左右子结点都为红色结点
* 则需要通过变色来维持红黑树的平衡
*/
if (x.left.getColor() == Color.RED && x.right.getColor() == Color.RED){
reverseColor(x);
}
}
return x;
}
/**
* 当一个结点连续出现两个左子结点都为红色结点的时候
* 需要进行右旋来保持红黑树的平衡化
* @param x
*/
private Node<K,V> rightRotate(Node<K,V> x){
Node<K,V> h = x.left;
x.left = h.right;
h.right = x;
h.setColor(x.getColor());
x.setColor(Color.RED);
return h;
}
/**
* 当一个结点出现左子结点为黑色，右子结点为红色的时候
* 需要进行左旋来保证红黑树的平衡化
* @param x
*/
private Node<K,V> leftRotate(Node<K,V> x){
Node<K,V> h = x.right;
x.left = h.right;
h.right = x;
h.setColor(x.getColor());
x.setColor(Color.RED);
return h;
}
/**
* 当一个结点出现左右子结点都是红色结点时
* 此时需要通过反转这三个结点的颜色
* 相当于对临时4-结点的分解
* @param x
*/
private void reverseColor(Node<K,V> x){
x.setColor(Color.getColorByFlag(!x.getColor().getFlag()));
x.left.setColor(Color.getColorByFlag(!x.left.getColor().getFlag()));
x.right.setColor(Color.getColorByFlag(!x.right.getColor().getFlag()));
}
/**
* 统计整棵红黑树的高度
* @return
*/
public int getDeep(){
if (root == null){
return 0;
}
return getDeep(root);
}
/**
* 统计x子树的高度
* @param x
* @return
*/
private int getDeep(Node<K,V> x){
return x == null ? 0 : Integer.max(getDeep(x.left),getDeep(x.right) + 1);
}
/**
* 前序遍历整棵红黑树
*/
public void preShow(){
if (root == null){
throw new RuntimeException(“【当前红黑树为空，不支持前序遍历】”);
}
preShow(root);
}
/**
* 前序遍历x子树
* @param x
*/
private void preShow(Node<K,V> x){
if (x == null){
return;
}
System.out.println(x);
if (x.left != null){
preShow(x.left);
}
if (x.right != null){
preShow(x.right);
}
}
/**
* 中序遍历整棵红黑树
*/
public void middleShow(){
if (root == null){
throw new RuntimeException(“【当前红黑树为空，不支持中序遍历】”);
}
middleShow(root);
}
/**
* 中序遍历x子树
* @param x
*/
private void middleShow(Node<K,V> x){
if (x == null){
return;
}
if (x.left != null){
middleShow(x.left);
}
System.out.println(x);
if (x.right != null){
middleShow(x.right);
}
}
/**
* 后序遍历整棵红黑树
*/
public void afterShow(){
if (root == null){
throw new RuntimeException(“【当前红黑树为空，不支持后序遍历】”);
}
afterShow(root);
}
/**
* 后序遍历x子树
* @param x
*/
private void afterShow(Node<K,V> x){
if (x == null){
return;
}
if (x.left != null){
afterShow(x.left);
}
if (x.right != null){
afterShow(x.right);
}
System.out.println(x);
}
/**
* 查询整棵树
* @param key
* @return
*/
public V get(K key){
return get(root,key);
}
/**
* 查询x子树
* @param x
* @param key
* @return
*/
private V get(Node<K,V> x,K key){
System.out.println(“【开始查询】”);
if (x == null){
return null;
}
int cmp = key.compareTo(x.getKey());
/**
* 二叉树查找规则
* 待查询结点和当前结点作比较
* 如果待查询结点的key值比当前结点key小，则递归当前结点的左子树
* 如果待查询结点的key值比当前结点key大,则递归当前结点的右子树
* 如果待查询结点的key值跟当前结点相等，则直接返回当前结点的value
*/
if (cmp < 0){
return get(x.left,key);
}else if(cmp > 0){
return get(x.right,key);
}else {
return x.getValue();
}
}
}
总结
以上是本篇文章讲解得所有内容，在本篇文章中，咱们主要介绍了一种新的树，在讲解红黑树这种数据结构之前，咱们花了大量的篇幅讲解了红黑树出现的原因以及原始二叉树会出现的弊端。在本篇文章中，咱们主要讲解了一种比较巧妙的思想让咱们的二叉树达到平衡，也就是咱们的2-3查找树，红黑树其实就是2-3查找树的一种实现方式。这种思想特别重要，希望大家都能够有所理解和所获。
学习的过程从来都是层层递进，越来越难的。但是当我们一步一步克服了一切困难后，豁然开朗的一瞬间又会是充满着无语言表的成就感的。所以呢，加油吧！未来一定属于那些迎难而上、百折而不挠的奋斗者的！
