深入理解红黑树原理与实现

发表于 | | 阅读次数:

红黑树(RBTree)是一种相比平衡二叉树(AVL)平衡要求较低的的一种二叉搜索树，所谓平衡要求较低的意思是相比AVL树的每个节点的左右子树的高度差不能超过2，红黑树使用红黑两种颜色来标记二叉搜索树中的节点，并对这种着色进行限制，使得在插入删除操作后对不符合的情况必须进行调整来保持这样一种限制，从而实现自我平衡。我们先来看一下红黑树的定义，也就是着色限制

  • 每个节点必须着色成红色或者黑色
  • 根节点是黑色的
  • 空节点是黑色的
  • 父子节点之间不能出现两个连续的红色节点
  • 每个节点到其后代叶子节点的所有路径上均包含相同数目的黑色节点(一个节点出发的所有路径的黑高相同)

通过这样的限制，红黑树可以实现没有一条路径会比最短路径长出两倍，相比AVL树来说平衡要求较低，这种低要求换来的是更高效的调整操作，红黑树可能仅需要进行局部的调整，而AVL树必须要回溯到根节点进行信息更新，这是红黑树的优势，并且红黑树的统计效率比AVL树好，有大量的工程项目已经在实际的使用这种数据结构存储数据，例如Java 8中的HashMap在处理冲突的时候就采用了红黑树代替了原来的链表以加快查询速度。

节点的定义

除了常规的左右子节点，因为我们在插入删除的时候经常需要进行查找当前节点的父节点，所以我们需要一个父节点信息，然后还有一个颜色信息，我们只需要一个Byte就可以指示当前节点是红色还是黑色，红色我们用0来表示，黑色用1来表示，其节点信息如下

1
2
3
4
5
6
7
8
9
10
11
12
public class RBNode<T> {
	T element;
	RBNode<T> left;
	RBNode<T> right;
	RBNode<T> parent;
	byte color;//0为红色，1为黑色
	
	public RBNode(T x) {
		this.element=x;
	}
	
}

另外我们还在RBTree构造方法里初始化了一个全局的nullNode，颜色为黑色，目的是简化繁杂的判空操作，它可以像正常节点一样，只是它的作用仅限于一下两点：

  • root的父节点指向nullNode
  • 树中节点原来指向空指针的地方用nullNode代替

nullNode自身的left，right，parent可以指向任何地方，可以在有需要的时候进行分配，也可以弃之不用，关于nullNode使用到的地方我会在最后进行总结。

基本的旋转操作

旋转操作是恢复红黑树性质的一条基本操作，它包括将一个当前节点的右孩子提到当前节点旋转到当前节点的位置，也就是左旋，对称的是将将当前节点的左孩子旋转到当前节点的位置，也就是右旋，我们用前一种情况作为例子进行分析，我们把它命名为rotateWithRightChild,整个转换过称如图所示，其中转换前图的红色标记为断开的链的序列，转换后图的红色标记为对应断开的链接序列重新修复的链接。

这里采用的断链的序列根据关系对来确定的，比如说p和x1之间的断开修复关系为1,2;p和x的关系修复为3,4两条，x和g的关系修复是5,6两条，在没有图示的情况下这样是比较直观想象的，如果是画出的图例，我们也可以根据每个节点进行逐一修复，比如p的parent和child修复，x的parent,child修复，g的child修复，x1的parent修复，这样的方式进行也是可以的。
另外我们还需要考虑nullNode的情况，那么哪里会出现nullNode呢？p和x不可能，这是由rotateWithRightChild的适用环境所决定的，而x1和g可能为nullNode, 如果x1为nullNode，旋转后x1的parent指向了p，这并不会造成不良的后果，所以可以不予考虑，而如果g是nullNode，则说明p是root，旋转结束后就需要将x置为新根，这是一个必选的操作，不然root还是p。
基于以上考虑此我们有如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 旋转父节点p的右儿子到p的位置
 * @param p
 * @return 
 */
public void rotateWithRightChild(RBNode<T> p){
	RBNode<T> x=p.right;
	RBNode<T> g=p.parent;
	//break1: p的右换指，同时改父指针
	//tip1: x.left可能为nullNode,因为在处理的过程中对nullNode的parent
	//可以是任意值，所以这里不做处理
	p.right=x.left;
	x.left.parent=p;
	//break2: x的左换指，同时改父指针
	x.left=p;
	p.parent=x;
	
	//break3: g的孩子更换为x
	//tip2: g为nullNode,说明p为root,旋转需要换新根
	if(g==nullNode) {
		root=x;//旋转后换新根
		root.parent=nullNode;
	}
	else if(g.left==p) {
		g.left=x;
		x.parent=g;
	}else {
		g.right=x;
		x.parent=g;
	}
}

对称的你可以写出rotateWithLeftChild，思路是一样的。

红黑树的插入

插入和删除是一个树的基本操作，对于有着色现在的红黑树来说，插入和删除都有可能引起红黑树着色限制的破坏，如何在插入和删除之后进行调整以维持红黑树的性质是红黑树实现的关键也是难点，这一节我们来探讨红黑树的插入。
我们插入的新节点总是红色的，原因是如果插入的节点是黑色的，那么必定会导致一条路径上的黑高增加一，每次插入必须进行调整，而如果插入节点是红色，而其父节点是黑色的话就可以不用调整。所以，我们选择插入红色的节点，在调整之前的插入逻辑和二叉查找树的插入是一样的，唯一不同的是需要在插入后如果插入节点的父节点是红色的话，会出现红红冲突，违反第四条限制规则，需要进行调整。下面是插入逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 输入一个节点值为x到红黑树根root中
 * @param x
 */
public void insert(T x) {
	RBNode<T> p,cur;
	p=nullNode;//p指向cur的父节点
	cur=root;
	while(cur!=nullNode) {
		p=cur;
		if(x.compareTo(cur.element)<0)
			cur=cur.left;
		else if(x.compareTo(cur.element)>0)
			cur=cur.right;
		else //找到重复的，不需要进行进一步操作
			return;
	}
	//此时p位置即为插入位置的父节点
	RBNode<T> newX=getNewNode(x);//新生成的节点为红色
	newX.parent=p;//即便p为nullNode也是符合的
	if(p==nullNode) {
		root=newX;
		root.color=1;
		return;//如果是根的话可以直接返回
	}else if(x.compareTo(p.element)<0) {
		p.left=newX;
	}else {
		p.right=newX;
	}
	//插入完毕，开始调整红色新插入的x节点
	if (p.color==1) //其父节点是黑色，插入完毕
		return;
	else //红红冲突，进行调整
		insertBalance(newX);
}

那么问题转换到如何在出现红红冲突的时候如何进行调整？处理这个问题的一个思路是能否想办法将插入节点x的父节点p变成黑色，这样解决了红红冲突，但是又造成了第五条黑高不同问题，如果能够在保持黑高不变的情况下将p变成黑色就好了。
哎~，p的父节点肯定是黑色的(不然有红红冲突)，我们可以将p的父节点g的黑色交给p,g变成红色，然后将p旋转到g的位置，这样不就行了，黑高没有变换，而且消除了p和x之间的红红冲突。基本思路是这样，但是我们还是要考虑一些细节，以验证这个想法是否合适，首先g变成了红色，g除了p之外的另一个孩子w,也就是p的兄弟节点如果是红色的，我们的这种调整会造成g和w之间的红红冲突，所以，如果w是红色的我们不能进行这种调整。
如果是w是黑色的，我们就没有了这方面的顾虑，旋转操作除了g变色的影响，还有链接的变化，假设p是g的左孩子，x是p的右孩子（之字形），则进行g和p旋后x就会变成g的左孩子,x是红色的，而g也是红色的，这也引入的新的红红冲突，这是我们不想要的；而如果x是p的左孩子呢（一字型），这种变色+旋转操作后x仍是p的左孩子，p变成了黑色，p和x的红红冲突解决，并且没有引入新的红红冲突，黑高也没有改变，看来一字型的情况只需要变色+旋转就可以完成整个调整，使得这个树符合红黑树的结构。
总结来说，我们有一下三种情况（x-红为新插入节点，p-红为x父节点，g为p的父节点，w为p的兄弟节点，假设p为g的左孩子，右孩子的情况可以对称推出）：

  • w为红色,则只需要g的黑色 (由p为红色推出g必为黑色) 分给p和w，g变红，使得黑高不变，而同时将g置为新的待调整节点
  • w为黑色的
    • x为p的右孩子，之字形，p-x进行左旋，p变成待调整节点，将其调整成一字型
    • x为p的左孩子，一字型，g变红，p变黑，g-p进行右旋，调整结束

用来表示这三种转换操作如下
w为红色的情况

之字形情况

一字型情况

这样，根据我们的分析，我们可以很快写出调整代码，调整结束的条件是当前调整节点的父节点是黑色(当w为红色的时候上推的过程可能导致)，另外一个场景是一字型调整后父节点一定是黑色的了，所以也会跳出循环，不过我们在处理完后要将root的颜色置为黑色，因为在上推的过程中可能将根节点变为红色，而根节点的父节点nullNode是黑色的，所以虽然退出了循环，根节点却变成了黑色，所以我们要在最后改一下根节点的颜色，真个实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * x节点和其父节点红红冲突，进行调整
 * @param x
 */
private void insertBalance(RBNode<T> x) {
	while(x.parent.color==0) {//在父节点为红色的情况下进行调整
		RBNode<T>p=x.parent;
		//g一定不为null，因为root为黑色，nullNode也是黑色的，所以x必是三层及一下的
		RBNode<T>g=p.parent;
		RBNode<T>w;//p的兄弟节点
		if(p==g.left) {//p是左孩子
			w=g.right;
			if(w.color==0) {//p的兄弟节点为红色，仅需调整颜色即可
				w.color=1;
				p.color=1;
				g.color=0;
				x=g;
				continue;//调整节点上推
			}
			else {//w的颜色为黑色
				if(x==p.right) {//之字形双红，进行左旋
					rotateWithRightChild(p);
					//更改相应的引用
					x=p;
					p=x.parent;//g不变
				}
				//之字形调整后是一字型，一字型还是一字型，接下来都按一字型处理
				p.color=1;//先变色
				g.color=0;
				rotateWithLeftChild(g);
			}
		}else if(p==g.right) {//p位于右边
			w=g.left;
			if(w.color==0) {
				g.color=0;
				w.color=1;
				p.color=1;
				x=g;
				continue;
			}else {
				if(x==p.left) {
					rotateWithLeftChild(p);
					x=p;
					p=x.parent;
				}
				g.color=0;
				p.color=1;
				rotateWithRightChild(g);
			}
		}
	}
	//最后置root为黑色，w为红或黑都有可能结束循环
	root.color=1;
}

红黑树的删除

说完了插入，这一节来将红黑树的删除，删除的逻辑和二叉查找树大同小异，第一步是找到删除节点，第二步判断删除节点的孩子情况，如果删除节点没有孩子节点，也就是左右孩子为nullNode，这里可以归结为左孩子为nullNode处理，删除当前节点，并用其右孩子代替其位置。对称的，右孩子为nullNode,则删除后用左孩子代替其位置。如果左右子树都不为nullNode,则将其换成其右子树的最小节点的值，转换成其右子树的最小节点，而这个节点一定没有左孩子，直接用其右孩子代替其位置即可。而剩下的问题就是根据删除节点的颜色来调整代替被删除节点的孩子节点。
如果删除的节点是红色，不需要进行调整。如果删除的节点是黑色节点，那么黑高收到了影响，如果代替它的孩子是红色，那么只需要将这个孩子变为黑色，黑高就得以恢复。而如果代替它的孩子是黑色，那么被删除的黑色无处填补，使得原来任意一个经过这个被删除节点的路径黑高减一，这种删除黑黑情况才是调整的重点，我们将这个调整过程叫做balanceDoubleBlack，在详细介绍之前，我们先写出删除的方法的详细。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public void remove(T x) {
	RBNode<T>cur=root;
	//查找待删除节点
	while(cur!=nullNode &&cur.element.compareTo(x)!=0) {
		if(x.compareTo(cur.element)<0)
			cur=cur.left;
		else
			cur=cur.right;
	}
	
	RBNode<T>balanceNode;//记录删除节点的孩子节点，也就是待调整节点
	int deleteColor;
	if(cur!=nullNode) {
		if(cur.left==nullNode) {//左子树为空和左右子树都为空一并处理
			balanceNode=cur.right;
			transplant(cur,cur.right);
			deleteColor=cur.color;
		}else if(cur.right==nullNode){
			balanceNode=cur.left;
			transplant(cur,cur.left);
			deleteColor=cur.color;
		}else {
			RBNode<T> minNode=findRightMin(cur);
			cur.element=minNode.element;
			deleteColor=minNode.color;
			//这时候可以执行删除minNode，其必没有左孩子，可以直接用右孩子代替
			balanceNode=minNode.right;
			transplant(minNode,minNode.right);
		}
		
		//删除完毕，开始执行调整被删除节点的
		//如果删除的是红色节点，则不影响，只考虑删除的是黑色节点
		if(deleteColor==1)
			if(balanceNode.color==0) {
				//balanceNode为红色，则删除的黑色补充到这个节点即可
				balanceNode.color=1;
			}else {
				balanceDoubleBlack(balanceNode);
			}
			
	}
}

根据上面所陈述的，在删除黑色节点后，补充上来的节点为balanceNode，如果其颜色也为黑色，那我们就可以认为balanceNode具有“双重”的黑色，需要使用某些方法来“消解”它这个过火的黑色，如何消解呢？方法是从balanceNode和其兄弟节点w上各取一层黑色上推给其父节点p，如果p是红色节点，直接将其变成黑色就完成了调整，否则的话其父节点p就变成了新的“双黑节点”，需要进一步调整。
但是从兄弟节点提一层黑色要兄弟节点是黑色节点才行，如果其兄弟节点是红色节点，那么就需要变色+旋转将其兄弟节点w的颜色变成黑色，交给其兄弟节点是黑色的情况进行处理。
如果其兄弟节点是黑色，那么我们是不是可以放心的提色了？也不是的，只有兄弟节点的左右子孩子都是黑色我们才可以提色，因为如果不是这样，我们提过色之后就会造成红红冲突。那么如果balanceNode的兄弟节点w有孩子是红色的，有什么情况是我们比较容易处理的，或者这样问,有没有方法可以调整成功？答案是有的，计算机大佬们已经找到了这种情况，假设balanceNode为p的左孩子，w为p的右孩子的情况下，w的右孩子如果为红色（p,w,wchild成一字型），我们就可以通过变色+旋转的方法一次调整成功。而如果其右孩子是黑色，左孩子为红色（p,w,w-red成之字形），我们可以通过变色+旋转的方法将其变成一字型的情况进一步处理。
总的来说，我们将其分为一下四种情况（balanceNode为双重黑色节点，p为balanceNode的父节点，balance为p的左孩子，w为p的右孩子，w1为w的左孩子，w2为w的右孩子）

  1. w为红色，将p变成红色，将w变为黑色，p-w左旋转
  2. w为黑色
    2.1 w的左右孩子都为黑色，将w变红色，p变为新的双重颜色节点(黑红或黑黑)
    2.2 w的左孩子w1为红色，右孩子w2为黑色，将w1变黑色，w变红色，w-w2右旋转，转到下面一种
    2.3 w的右孩子w2为红色，w变成p的颜色（可能为红，也可能为黑），p变成黑色，w2变成黑色，p-w左旋

整个算法结束的出口是balanceNode为红色，或者balanceNode已经是根了
用图来描述的话也就如下(不确定颜色用蓝色表示)
w为红色，将p变成红色，将w变为黑色，p-w左旋转

w为黑色，并且左右子树都为黑色，将w变红色，p变为新的双重颜色节点(黑红或黑黑)

w为黑色，w的左孩子w1为红色，右孩子w2为黑色，将w1变黑色，w变红色，w-w2右旋转，转到2.3的情况

w为黑色，w的右孩子w2为红色，w变成p的颜色（可能为红，也可能为黑），p变成黑色，w2变成黑色，p-w左旋，调整结束

根据上面的分析，我们有如下实现代码,算法出口为balanceNode为root或者balanceNode为红色，也就是在balanceNode不为root并且balanceNode为黑色的时候进行循环调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * balanceNode为双重黑色，进行调整
 * @param balanceNode
 */
private void balanceDoubleBlack(RBNode<T> balanceNode) {
	//在balanceNode不为根节点，并且颜色为黑的情况下进行调整
	while(balanceNode!=root&& balanceNode.color==1) {
		RBNode<T> p=balanceNode.parent;
		RBNode<T> w;
		if(p.left==balanceNode) {
			//balanceNode为其父节点的左孩子
			//按balanceNode的兄弟节点的颜色分两大类
			w=p.right;
			if(w.color==0) {
				//兄弟节点为红色
				w.color=1;
				p.color=0;
				rotateWithRightChild(p);
				w=p.right;//w变了
			}else {
				//兄弟节点为黑色
				//当兄弟节点的颜色为黑色的时候分为3种情况
				//1. 兄弟节点左右子还是都是黑色节点，则从两边各提一层黑
				if(w.left.color==1&&w.right.color==1) {
					w.color=0;
					balanceNode=p;
				}else {
					//2. 兄弟节点的左孩子为红色，右还是为黑色，w与w-leftchild,p构成之字形
					//在不改变黑高的情况下调整成一字型
					if(w.left.color==0&&w.right.color==1) {
						w.color=0;
						w.left.color=1;
						rotateWithLeftChild(w);
						w=p.right;
					}
					//3. 兄弟节点的右孩子为红色，p,w与w.right一字型，
					//w变成p的颜色，p变成黑色，w.right变成黑色，左旋
					w.color=p.color;
					p.color=1;
					w.right.color=1;
					rotateWithRightChild(p);
					//调整结束,最后将根节点调为黑色
					balanceNode=root;
				}
			}
			
		}else {
			//balanceNode为其父节点的右孩子
			w=p.left;
			if(w.color==0) {
				//兄弟节点为红色
				p.color=0;
				w.color=1;
				rotateWithLeftChild(p);
				w=p.left;
			}else {
				//兄弟节点为黑色
				if(w.left.color==1&& w.right.color==1) {
					w.color=0;
					balanceNode=p;
				}else {
					if(w.left.color==1&& w.right.color==0) {
						w.right.color=1;
						w.color=0;
						rotateWithRightChild(w);
						w=p.left;
					}
					w.color=p.color;
					p.color=1;
					w.left.color=1;
					rotateWithLeftChild(p);
					balanceNode=root;
				}
			}
		}
	}
	balanceNode.color=1;//防止最后的调整好的根节点为红色
}

nullNode的作用之处

nullNode在简化我们编程的过程中起到了很重要的作用，这使得我们避免NullpointException的情况，它的作用和链表中的头节点一样，其唯一的目的是简化我们的操作，但是我们还是不能避免对是nullNode的情况下进行特殊处理，那么在整个红黑树的过程中，我们都是在哪里需要nullNode的情况的呢，总结如下：

  1. 旋转的时候判断祖父节点g是否为nullNode，如果是的话旋转后就换新根
  2. 用一个节点代替另一个节点的时候，如果被代替节点的父节点为空的话（被代替节点为根节点），则需要将新节点置为根
  3. 插入的时候，如果插入节点的父节点为nullNode的话，直接置插入节点为根节点
  4. 删除时候的判空操作

关于源码

本文所有源码可以从这里获得，本文首发表于我的博客,欢迎关注！转载须注明文章出处，作者保留文章所有权。

参考文献

算法导论

坚持原创技术分享，您的支持将鼓励我继续创作！