教你手写红黑树羞辱面试官

之前在网上看过一个搞笑的关于面试的段子,说的是两个妹子A和B去某司面试前端开发岗位。
A妹子又黑又矮,面试官说“写个二叉树查找”,瞬间写完,面试官又说“写个快速排序”,又秒写,”再写个红黑树的插入”,A妹子挠挠头,走了。
B妹子生的明艳动人,面试官说“额,写个Hello World吧”,B妹子说,“我不会”,面试官喜笑颜开“没事没事,我来教你”。
这个段子折射出一个问题,那就是在面试过程中手写红黑树很难,几乎是一个不可能完成的任务,所以网上才会有很多手写红黑树的段子。

那么数据结构与算法中的红黑树真的很难吗?手写红黑树真的是Mission Impossible吗?其实红黑树并没有很难,算是数据结构中比较初级的算法,不能完整的将这个算法手写或者说手推下来(并不提倡默写),证明对算法的整个流程并没有完全的掌握,对算法的原理和意义一知半解,不是十分清晰。

下面,将教你一步步掌握红黑树,万一我们长得不是那么“明艳动人”,也能凭借实例吊打面试官~

AVL树

提到红黑树,首先要了解的是他的基础,AVL树

在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。 —-维基百科

AVL树是高度平衡树,任何节点的两个子树的高度差不能大于1。所以某一次的插入会破坏这个平衡,如下图所示。

AVL不平衡
一旦AVL树上的某次插入破坏了平衡,就需要通过旋转使之再次平衡。关于旋转,在很多算法书和博客上都有介绍,掌握重要的一点就是分为两个Case:新增节点是外侧插入还是内侧插入。如果是外侧出入,就做一次单旋转;如果是内次插入,需要做两次旋转,详细步骤这里就不罗列了,可以看下面的示意图。

AVL右旋转
AVL双旋转

红黑树

理解了AVL树的旋转,我们再来看红黑树。红黑树也是一种平衡树搜索树。它有几个特性:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

主要看4和5两点,这决定了红黑树什么时候像AVL树一样进行旋转,以及如何进行旋转。

红黑树提前旋转
如上图所示,根据红黑树的性质,红黑树插入后的旋转发生在连续插入两个红色节点之后,与AVL树旋转的发生不同,在红黑树的性质下规范的旋转是为了预防平衡搜索树在某一条路径的插入频率过快儿导致高度不平衡,对比AVL树旋转的条件,可以理解为一种防微杜渐的预防措施。

红黑树case2
红黑树的旋转在AVL树内侧插入和外侧插入两个case的基础上,有增加了一个变量,那就是插入节点叔父节点的颜色。如果叔父节点为黑色节点(或为null),那么旋转方法和AVL树的旋转方法大致相同。如果叔父节点为红色,在很多参考书目中我们看到其旋转方法为先旋转再染色,但是这种方法不利于将其转化为程序语言。根据红黑树的性质4和5,可以将祖父节点从黑色变为红色,再将父亲节点和叔父节点一次性变为黑色,这样就能满足路径上的黑色节点依然相等,且没有两个连续的红色节点。

算法实现

下面我们准备开始手写红黑树,先从旋转函数开始写起。说起旋转,我们首先要明确一个概念——旋转点。旋转点的概念为我们以哪个节点为顶点进行旋转,一般选择旋转局部的顶点。

红黑树右旋点
如上图所示,右旋的旋转点为A
考虑到受众,这里使用群众喜闻乐见的JAVA

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//首先定义节点的数据结构
public enum Color {
RED, BLACK
}
public class TreeNode {
private TreeNode parent;
private TreeNode left;
private TreeNode right;
private Color color;
private int val;
Public TreeNode(int val) {
this.val = val;
this.parent = Null;
this.left = Null;
this.right = Null;
this.color = Color.RED;
}
public TreeNode getParent() {
return this.parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode getLeft() {
return this.left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return this.right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public TreeNode getColor() {
return this.color;
}
public void setColor(Color color) {
this.color = color;
}
public int getVal() {
return this.val;
}
public void setVal(val) {
this.val = val;
}
}
//右旋函数
public static void rotate_right(TreeNode x, TreeNode root) {
TreeNode y = x.getLeft();
x.setLeft(y.getRight());
if(y.getRight() != Null) {
y.getRight().setParent(x);
}
/**
* 注意要判断边界条件,如果祖父节点是root
* 还要注意插入节点在左边和右边两种镜面的情况
**/
if(x == root) {
root = y;
}
else if(x == x.getParent().getLeft()) {
x.getParent().setLeft(y);
}
else {
x.getParent().setRight(y);
}
y.setParent(x.getParent());
x.setParent(y);
y.setRight(x);
}
//左旋函数
public static void rotate_left(TreeNode x, TreeNode root) {
TreeNode y = x.getRight();
x.setRight(y.getLeft());
if(y.getLeft() != Null) {
y.getLeft().setParent(x);
}
if(x == root) {
root = y;
}
else if(x == x.getParent().getLeft()) {
x.getParent().setLeft(y);
}
else {
x.getParent().setRight(y);
}
y.setParent(x.getParent());
x.setParent(y);
y.setLeft(x);
}

下面写调整函数,这是一个从插入点开始的自底向上的过程,因为在红黑树的case2,父亲节点和叔父节点都为红色的情况下,我们需要将祖父节点变红,这样有可能会碰到祖父节点的父亲节点也为红色的情况,需要以祖父节点为新的插入节点,继续向上迭代的调整红黑树。

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
public static void rebalance_tree(TreeNode x, TreeNode root) {
while(x.getParent().getColor()==Color.RED && x.getParent() != root) {
//插入节点的父亲节点在左侧
if(x.getParent().getParent().getLeft()==x.getParrrent()) {
TreeNode y = x.getParent().getParent().getRight(); //领y为叔父节点
if(y!=Null && y.getColor()==Color.RED) { //叔父节点y为红色
y.getParent().setColor(Color.RED);
x.getParent().setColor(Color.BLACK);
y.setColor(Color.BLACK);
x = x.getParent().getParent();
}
else { //叔父节点为空或为黑色
if(x==x.getParent().getRight()) { //插入节点为内侧插入
x = x.getParent();
rotate_left(x, root);
}
x.getParent().getParent().setColor(Color.RED);
x.getParent().setColor(Color.BLACK);
rotate_right(x.getParent().getParent(), root);
}
}
//插入节点的父亲节点在右侧
else {
TreeNode y = x.getParent().getParent().getLeft(); //另y为叔父节点
if(y!=Null && y.getColor()==Color.RED) { //叔父节点为红色
y.getParent().setColor(Color.RED);
x.getParent().setColor(Color.BLACK);
y.setColor(Color.BLACK);
x = x.getParent().getParent();
}
else { //叔父节点为空或为黑色
if(x==x.getParent().getLeft()) { //插入节点为内侧插入
x = x.getParent();
rotate_right(x, root);
}
x.getParent().getParent().setColor(Color.RED);
x.getParent().setColor(Color.BLACK);
rotate_left(x.getParent().getParent(), root);
}
}
}
}

最后才是真正的插入函数,因为前面已经做了大量的铺垫,在书写插入函数的时候反而变的简单起来。利用二叉搜索树的性质,找到要插入节点的位置插入,然后对插入造成的不平衡状态进行调整。

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
public static Boolean insert_unique(int x, TreeNode root) {
TreeNode y;
TreeNode curNode = root;
while(curNode!=Null) {
y = curNode;
if(x==curNode.getVal()) {
return false;
}
else if(x<curNode.getVal()) {
curNode = curNode.getLeft();
}
else {
curNode = curNode.getRight();
}
}
TreeNode newNode = new TreeNode(x);
if(x<y.getVal()) {
newNode.setParent(y);
y.setLeft(newNode);
}
else {
newNode.setParent(y);
y.setRight(newNode);
}
rebalance_tree(newNode, root);
}

本篇只是简单的介绍了如何手写红黑树的插入,希望能给大家建立学习算法的信心。诸如红黑树的查找,红黑树的遍历等操作,因为和二叉搜索树的相关基础操作类同,这里就不实现了。另外红黑树的删除因为篇幅原因也同样不列出了,有兴趣的同学可以在网上找找帖子参考下,如果确实理解了红黑树的5个性质,实现起来也并不复杂。
理解和掌握算法,看书和查资料是一方面,最重要的还是结合理论自己动手进行实践。在磕磕碰碰的再现过程中加深理解,直至完全掌握,最终做到信手拈来。
看完此文,何不也马上动手一练呢?