(四)树结构---红黑树的实现
导语
- 红黑树的难点主要是何时为红色，何时为黑色，每次增删都可能对应着树的颜色发生变化
- 为什么存在红黑树，红黑树具体有哪些优势，和平衡二叉树的区别
- 笔者也会介绍2-3树，是为了更好地理解红黑树，若对红黑树性质有一些了解可直接跳过2-3树部分
- 本文的目的是为了更好的了解红黑树的机制和特性，结合所学资料，仅介绍添加方法时，红黑树发生的变化
1. 2-3树
1. 2-3树定义
2-3树是一种简单的由二节点和三结点组成的绝对平衡的B型树。
二结点：即该结点有一个元素，有两个空子结点
三结点：即该结点有两个元素，有三个空子结点
绝对平衡：类似满二叉树，但是有些结点可以存在两个元素
2-3树基础
2. 2-3树的添加操作
- 基础操作
- 对于一个空树来说，会构建成一个二节点(后续二节点都是拆分得到)
- 对于一个二节点，在添加一个元素后会变成(融合成)三结点
- 对于一个三结点，在添加一个元素后会暂时变成(融合成)四结点，之后对其进行拆分，拆分成一个父二节点拥有两个子二节点，若父二节点非根结点，再和其父节点进行向上融合
-
举例构建一个2-3树，依次添加元素{50，36，78，25，45，16，8}
1.向一个空2-3树添加元素50，此时会构建一个二结点
1.png
2.再添加元素36，此时会和已有值为50的二节点融合成三结点
2.png
3.再添加元素78，此时会先融合成四节点，再拆分，而拆分后的父结点为根结点，无需向上融合。
3.png
4.再依次添加元素25，45
添加元素25会和值为36的二节点融合成三结点；
再添加元素45后,此三结点会先融合成四结点，再拆分，拆分后的值为36的父二结点向上融合，与值为50的结点构成三结点
4.png
5.再依次添加元素16，8
添加元素16会和值为25的二节点融合成三结点；
再添加元素8后,此三结点会先融合成四结点，再拆分，拆分后的值为16的父二结点向上融合，与值为(36，50)的三结点构成四结点，再次拆分，直到拆分的父节点向上融合到根结点(即变成二结点)或与其父结点融合成为三结点
5.png
Ⅱ. (左倾)红黑树
左倾的意思？
- 红黑树分成左倾红黑树和右倾红黑树，只是人为约定的，即一个黑结点不可能同时拥有两个红色子结点，因为此时红黑树需要进行颜色反转处理，后续会介绍，为什么不能同时存在，且什么是颜色反转。左倾的意思是，一个黑结点若其子结点为红色，必然出现在左孩子上，右孩子必然是黑色结点(若红结点在右孩子上，则进行左旋)
1. 红黑树性质
- 1.每个结点或为黑色，或为红色
- 2.根结点为黑色
- 3.每个叶子节点为黑色的(红黑树中叶子结点指空结点)
- 4.如果一个结点是红色的，那他的左右孩子结点为黑色
- 5.从任意一个结点到叶子结点，经过的黑色结点是一样的
2. 红黑树与2-3树的关系
-
2-3树可以等价的转换成红黑树，由于红黑树是黑绝对平衡二叉树，所以相当于红色的左子结点与黑父亲结点是一个2-3树中的三结点。
-
2-3树中二结点 == 红黑树中某黑结点，左右孩子皆为黑结点的情况
-
2-3树中三结点 == 红黑树种某黑节点的左孩子为红节点的情况(右孩子必为黑色)
-
2-3树中新增结点需要融合已有叶子节点 == 红黑树中添加一个红色结点，所以红黑树中添加的新结点默认为红色
-
2-3树中结点拆分，向上融合 == 红黑树中颜色转换，拆分为孩子的结点为黑结点，拆分为双亲的结点需要上向融合，所以为红节点
2-3树与红黑树关系.png
3. 以2-3树解读红黑树定义性质
- 第一条：每个结点或为黑色，或为红色
如2-3树与红黑树关系图：
1.黑色结点代表(双子为黑色)二结点或三结点中的右结点
2.红色结点可以看作三结点中的左结点
- 第二条：根结点为黑色
根据第一条解释，不管根结点相当于2-3树中的二结点或是三结点中的右结点，都是黑色的
- 第三条：每个叶子节点为黑色的(红黑树中叶子结点指空结点)
1.若叶子结点不为黑色，而不为空的叶子结点为红色(关系图)，则会出现相当于2-3树中四节点的情况，因为红色结点永远与父亲结点融合
2.如上面关系图中红色叶子结点16，其父亲右结点为空，若空结点为红色，则不满足左倾的性质，因为双结点为红色结点需要进行颜色反转
- 第四条：如果一个结点是红色的，那他的左右孩子结点为黑色
若一个结点为红色，相当于为2-3树中的三结点的左结点；
而三结点有两种类型的孩子，二结点和三结点，二结点准换成红黑树为黑色结点，而三结点转换为红黑树，相当于连接的为三结点的右结点，右结点也必为黑色，因此红色结点的双子必为黑色，如关系图中值为(36-50)三结点和其二结点，三结点孩子，转换成的样子。
- 第五条：从任意一个结点到叶子结点，经过的黑色结点是一样的
因为红黑树只看黑节点即为黑平衡满二叉树，而满二叉树必然经过的结点数目是一样的。
4. 红黑树的添加的所有情况
-
向一个空的红黑树中添加一个元素
情况A
-
向以值为12的根结点的红黑树中添加元素(值<12)
情况B-1
-
向以值为12的根结点的红黑树中添加元素(值>12)
情况B-2
-
向拥有值为6的左儿子结点的值为12的结点中添加元素(值>12)
情况C-1
-
向拥有值为6的左儿子结点的值为12的结点中添加元素(值<6)
情况C-2
-
向拥有值为6的左儿子结点的值为12的结点中添加元素(6<值<12)
情况C-3
5. 红黑树的添加操作及其实现
- 举例结合代码实现添加操作,构建一个红黑树，依次添加依次添加元素{50，36，78，90，95，48，40}
5.1. 红黑树也是基于二分搜索树，因此可以复用二分搜索树的实现，而红黑树比二分搜索树多出了颜色标识，因此增加一个boolean元素，默认规定red = true,black = false
public class RedBlackTree<K extends Comparable<K>,V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node{
public K key;
public V value;
public Node left;
public Node right;
public boolean color;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
//默认添加的新结点为红色
color = RED;
}
}
private Node root;
private int size;
public RedBlackTree() {
root = null;
size = 0;
}
}
5.2. 空结点我们默认为黑色，在程序中增加一个私有方法，来判断当前结点是否为红色结点
/**
* 判断结点node的颜色
* @return
*/
private boolean isRed(Node node){
if(node == null){
return BLACK;
}
return node.color ;
}
5.3. 添加元素的操作和二分搜索树的过程过程是一致的，在回溯到过程中维护红黑树的性质，而在每次维护某结点后，会回溯维护其父结点，此时如同2-3树中的向上融合，因此其父结点变为红色，以此回溯维护，最差会维护到根结点，此时根则为红色，而红黑树性质根结点为黑色，因此再回溯维护完整颗红黑树后，维护一次根结点为黑色
/**
* 向红黑树中添加一个元素
* @param key :
* @param value :
*/
public void add(K key,V value){
root = add(root,key,value);
//回溯整颗红黑树后，根结点维护为黑结点
root.color = BLACK;
}
5.4. 上述准备工作已完成，接下来根据例子来实现代码的添加操作
-
先往空红黑树中添加第一个元素50，即情况A
1.png
此时结点并不需要在代码进行任何操作，因为相当于一个2-3树中二结点
-
再添加元素36，即情况B-1
2.png
此时结点并不需要在代码进行任何操作，因为相当于一个2-3树中的三结点
-
再添加元素78，即情况C-1
3.png
此时结点需要代码进行颜色反转操作，即情况C-1
此操作相当于2-3树中对一个三结点再融合一个元素
此时需要拆分成一个父二结点和两个子二结点，其中子二结点为黑色，父二结点需要向上融合，因此为红色
代码如下：
/**
* 颜色反转
*/
private void flipColors(Node node){
node.color = RED;
node.left.color = node.right.color = BLACK;
}
-
再添加元素90，此操作即情况B-2(只是父节点非根结点，并不影响)
4.png
此操作相当于2-3树中对一个结点进行融合，但是我们规定红黑树为左倾的，只支持添加新元素从左边融合结点，所以进行左旋操作
后继结点维持此结点的颜色不变：后继结点继承此结点颜色
而旋转后并没有改变子结点融合父节点的步骤，因此此时的新叶子结点需要融合新父亲结点(后继结点)，所以新叶子结点变成红色，相当于本次添加实际上新添加78这个元素
代码实现：
/**
* node x
* / \ / \
* T4 x 向左旋转(y) node Z
* / \ ---------------> / \
* T3 Z T4 T3
*
* 左旋转
* @param node：
* @return ：
*/
private Node leftRotate(Node node){
//后继结点为该结点的右儿子
Node successor = node.right;
//旋转
//node结点的右儿子变成后继结点的左子树
node.right = successor.left;
//后继结点的左子树为node结点
successor.left = node;
//重新上色
//后继结点颜色继承此结点
successor.color = node.color;
//新的叶子结点为红色
node.color = RED;
return successor;
}
-
再添加元素95，即 情况C-1 和 情况B-2
5.png
此过程相当于上述添加78和90的结合,，因此两种变换方式并非是互斥的，是满足条件即触发
-
再添加元素48，即 情况B-2
6.png
此操作与情况B-2一样
-
再添加元素40,即情况C-3转换成情况C-2(转换的过程即情况B-2，父节点为黑是二结点添加，为红则是三结点添加，本质是一样的)，最后成为情况C-1
7.png
在本过程中，颜色转换和左旋之前介绍过，右旋和左旋同理，右旋相当于2-3树中对一个三结点融合一个元素，需要拆分成三个二结点，其中父二结点可能和其父亲结点再次发生融合
/**
* 右旋转：
* node x
* / \ / \
* x T4 向右旋转(y) Z node
* / \ ---------------> / \
* Z T3 T3 T4
* @param node :
* @return :
*/
private Node rightRotate(Node node){
Node successor = node.left;
//旋转
node.left = successor.right;
successor.right = node;
//重新上色
successor.color = node.color;
node.color = RED;
return successor;
}
5.5. 添加操作总结
- 由上述添加过程发现，
1：我们在添加元素后回溯过程中，对同一个结点(此结点可能经过旋转由后继结点变成该结点，所以同一个结点指同一个位置的结点)可能需要采用多种方式来完成红黑树的性质；
2：所有对红黑树的的操作，都可以归结于三种，左旋，右旋，颜色转换，三种操作非互斥，而是满足条件即触发
在新增结点A为红色结点，空结点为黑色结点的前提下，设新增的结点A的值为a,且与结点F,值为f有位置添加关系，且F若存在非空左儿子，则为C，值为c
| 红黑树操作 | 添加位置 | 处理情况 | 对F来说的情况 | 对应2-3树添加关系 |
|---|---|---|---|---|
| 左旋 | A结点为F结点的右儿子，即a > f | 父节点任意颜色，但左孩子为黑色 | A = red && C = balck | 对一个二结点融合新元素，将其转换成左边融合(左倾红黑树，不允许融合的元素大于二结点的值) |
| 右旋 | A结点为C结点的左儿子时，即a < c | 新增结点的父节点为红色 | A = red && C = red(C为A的父亲) | 即对一个三结点融合新元素，暂时成为一个四结点 |
| 颜色反转 | A结点为F结点的右儿子，即a > f | 父节点为黑色，但左孩子为红色 | A = red && C = red (A，C为兄弟) | 对一个添加新结点的三结点暂时融合的四节点，进行拆分，拆分成三个二结点 |
三种操作维护时机和关系(图来源于慕课网数据结构讲解)：
三种操作维护时机与关系
/**
* 向以node为根的红黑树中添加一个元素，
* 并返回插入新结点后，红黑树的根
* @param node ：
* @param key ：
* @param 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 {
node.value = value;
}
//维护红黑树性质
//1.当前结点右孩子是否为红色，且左孩子不为红色 --> 左旋转
if(isRed(node.right) && !isRed(node.left)){
node = leftRotate(node);
}
//2.当前结点的左孩子为红结点，左孩子的左孩子为红结点 --> 右旋转
if(isRed(node.left) && isRed(node.left.left)){
node = rightRotate(node);
}
//3.如果当前结点的左孩子和右孩子都是红色结点 ---> 反转颜色
if(isRed(node.right) && isRed(node.left)){
flipColors(node);
}
return node;
}
6. 测试
- 测试红黑树，我们以上述举例添加的元素来做测试，看看结果是否与图中一样
因此我们需要在代码中增加一下红黑树的结构显示 - 思路：重写toString方法，以根结点深度为0，每增加一个深度在输出元素前添加一个字符串“---”，且再输出元素前判断结点的颜色，以"B-value"或"C-value"代表元素及其颜色
/**
* 输出红黑树形状：
* 以中序遍历形式输出红黑树
* 以根结点为深度0，其子结点深度+1
* 红结点以 R-结点值 形式
* 黑结点以 B-结点值 形式
*
* @return ：
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
getRBTreeStructure(root,str,0);
return str.toString();
}
/**
* 中序遍历以node为根结点的红黑树，描述红黑树形状和颜色
* @param node: 根结点
* @param str :
* @param depth : 结点深度
* @return :
*/
private void getRBTreeStructure(Node node, StringBuilder str, int depth) {
if(node == null){
return;
}
getRBTreeStructure(node.left,str,depth + 1);
str.append(getRBTreeValue(node,depth)+"\n");
getRBTreeStructure(node.right,str,depth + 1);
}
private String getRBTreeValue(Node node, int depth) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < depth; i++) {
sb.append("— — —");
}
if(isRed(node)){
sb.append("R+");
}else {
sb.append("B+");
}
sb.append(node.key);
return sb.toString();
}
-
测试结果
测试结果.png
