红黑树
红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树，也是技术面试中经常被问到的树，然而无论是书上还是网上的资料，通常都比较刻板难以理解，能不能一种比较直观的方式来理解红黑树呢？本文将以图形的方式来解释红黑树的插入与删除操作。
对树结构的学习是一个递进的过程，我们通常所接触的树都是二叉树，二叉树简单来说就是每个非叶子节点都有且只有两个孩子，分别叫做左孩子和右孩子。二叉树中有一类特殊的树叫二叉查找树，二叉查找树是一种有序的树，对于每个非叶子节点，其左子树的值都小于它，其右子树的值都大于它。比二叉查找树更进一步的是二叉平衡树，二叉平衡树除了保证有序外，还能够保持每个节点左右子树的高度相差不超过1。常见的平衡树有AVL树，Treap，红黑树，伸展树，等等。
红黑树是一种二叉查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
红黑树满足一下5个性质：
- 每个节点是红色或者黑色；
- 根节点是黑色；
- 每个叶子节点NIL是黑色；
- 如果一个节点是红色，则它的两个孩子都是黑色；（每条路径上不能有两个连续的红色节点）
- 任一节点到其所有子孙叶子节点NIL的路径上包含相同数目的黑色节点。
注意，在红黑树中，把传统二叉树的叶子节点的孩子指向NIL，称NIL为红黑树中的叶子节点。NIL节点中含有指向父节点的指针，这可能是需要把null改为NIL的原因。
一、插入操作
首先以二叉查找树的插入方式（插入的新节点都在叶子节点处）插入新的节点，并将其绘为红色。然后再重绘其颜色或旋转以保持红黑树的性质，调整分为以下三种情况：
1 新节点N没有父节点（即位于根上）
将新节点N绘为黑色。
2 新节点N的父节点P为黑色
不用调整。
3 新节点N的父节点P为红色
因为红黑树不允许有两个连续的红色节点（性质4），所以需要调整，根据N的叔父节点颜色分为两种情况：（我们以 N的父节点P为左孩子为例，P为右孩子的情况类似，不再详述）
3.1 新节点N的叔父节点U为红色
将新节点N的父节点P和叔父节点U都绘为黑色，将其祖父节点G绘为红色，这样保证从G到每个null节点的路径上所包含的黑色节点个数与原来保持一致。但由于我们把G变成了红色，如果G的父亲也是红色，就可能导致连续两个红色节点（违反性质4），所以，需要重新检查G是否违反了红黑树性质。
3.2 新节点N的叔父节点U为黑色
若新节点N是其父节点P的左孩子：将其父节点P绘为黑色，祖父节点G绘为红色，然后对G进行一次右旋转。
若新节点N是其父节点P的右孩子：对其父节点进行一次左旋转，问题转化为左孩子的情况。
二、删除操作
《算法导论》和维基百科上的做法都是，当删除一个黑色节点D时，把D的黑色“下推”至其子节点C，也就是说C除了本身的颜色外多了一重额外的黑色，然后不断把这重额外的黑色沿树上移，直到碰到一个红色节点，把其变为黑色以保证路径上黑色节点数目不变，或者移到树的根部，这样所有路径上的黑色节点数目都减一，保持相等。上移过程中可能需要旋转和修改一些节点的颜色，以保证路径上黑色节点数目不变。
这种做法可能有利于代码的实现（可用迭代的方式），但却不便于理解（个人认为）。本着理解优先的目的，我根据被删除节点D的孩子是否为NIL做如下分类：
1 被删除节点D的两个孩子都是NIL
1.1 被删除节点D是红色
用NIL替换D即可。
1.2 被删除节点D是黑色（我们以D是左孩子为例）
1.2.1 被删除节点D的兄弟节点B的两个孩子都为NIL
将D的兄弟节点B绘为红色，父节点P绘为黑色。
图中半红半黑表示该节点可能为红色，也可能为黑色。如果P原来是红色，这样修改后路径上的黑色节点数目和删除D之前一样；如果P原来是黑色，那么删除D后会导致路径上黑色节点的数目比删除前少了一个，所以还需继续检查经过P的路径上黑色节点数目的改变是否影响了红黑树的性质。
1.2.2 被删除节点D的兄弟节点B有一个孩子不为NIL
这个孩子一定是红色的，否则从D的父节点到各个叶子节点的路径上黑色节点的数目就会不等（违反性质5）。
若这个孩子为右孩子，将B的这个右孩子绘为黑色，B绘为其父节点P原来的颜色，P绘为黑色，然后对P进行一次左旋转。
若这个孩子为左孩子，将B的这个左孩子绘为黑色，B绘为红色，然后对B进行一次右旋转，问题转化为右孩子的情况。
1.2.3 被删除节点D的兄弟节点B的两个孩子都不为NIL
若B为红色，则B的两个孩子一定为黑色。将B绘为黑色，B的左孩子绘为红色，然后对P进行一次左旋转。
若B为黑色，则B的两个孩子一定为红色。将B的父节点P绘为黑色，B的右孩子绘为黑色，B绘为其父节点P原来的颜色，然后对P进行一次左旋转。
2 被删除节点D的两个孩子都不是NIL
按照二叉查找树删除节点的方法找到D的后继节点S，交换D和S的内容（颜色保持不变），被删除节点变为S，如果S有不为NIL的节点，那么继续用S的后继节点替换S，直到被删除节点的两个孩子都为NIL，问题转化为被删除节点D的两个孩子都为NIL的情况。
3 被删除节点D有一个孩子不是NIL
这个孩子C一定是红色节点，否则从D到各个NIL节点的路径上的黑色节点数目就会不同（违反性质5）。
交换D和C的内容（颜色保持不变），被删除节点变为C，问题转化为被删除节点D的两个孩子都为NIL的情况。
二叉树的遍历
二叉树的遍历有三种：前序遍历、中序遍历和后序遍历。每种遍历的实现又有递归和迭代两种，这篇文章我们来讨论如何用比较优雅的代码来实现二叉树的遍历。
首先我来定义一个二叉树的节点：
|
1
2
3
4
5
6
7
8
9
|
public class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int x) { val = x; }} |
一、前序遍历（Preorder Traversal）
简单来讲，前序遍历就是先访问父节点，再访问左孩子，最后访问右孩子，即以父、左、右的顺序来遍历。
递归实现非常简单，代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class Solution { List<Integer> result = new ArrayList<Integer>(); public List<Integer> preorderTraversal(TreeNode root) { dfs(root); return result; } private void dfs(TreeNode root) { if (root == null) { return; } result.add(root.val); dfs(root.left); dfs(root.right); }} |
迭代实现需要借助一个栈，存储没被访问的右节点，代码如下：
|
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
|
public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode curr = stack.pop(); result.add(curr.val); if (curr.right != null) { stack.push(curr.right); } if (curr.left != null) { stack.push(curr.left); } } return result; }} |
二、中序遍历（Inorder Traversal）
简单来讲，中序遍历就是先访问左孩子，再访问父节点，最后访问右孩子，即以左、父、右的顺序遍历。
递归代码也比较容易，如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); recurse(root, result); return result; } private void recurse(TreeNode root, List<Integer> result) { if (root == null) return; recurse(root.left, result); result.add(root.val); recurse(root.right, result); }} |
上面这种写法有别于前序遍历的递归代码，前序遍历的递归我们使用了成员变量来存储遍历的结果，这里我们使用方法参数来保存遍历的结果。两种写法都可以，喜欢哪种就使用哪种。
中序遍历的迭代实现没有前序遍历那么简单，虽然也需要借助一个栈，但迭代终止的条件却有所不同。想象一下，对于一棵二叉树，我们最先访问的节点是其最左边的节点，我们当然可以通过一个 while 循环到达其最左边，可是当我们回退时，我们如何知道某个节点的左孩子是否已经访问过了？我们使用一个 curr 变量记录当前访问的节点，当我们把一棵子树的右节点都访问完毕时，我们就该回退该子树的父节点了，而此时 curr 为 null，所以我们可以以此来区分一个节点的左子树是否已被访问过。代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; }} |
三、后序遍历（Postorder Traversal）
简单来讲，后序遍历就是先访问左孩子，在访问右孩子，最后访问父节点， 即以左、右、父的顺序遍历。
仿照中序遍历，可以很容易地写出后序遍历的递归实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); recurse(root, result); return result; } private void recurse(TreeNode root, List<Integer> result) { if (root == null) return; recurse(root.left, result); recurse(root.right, result); result.add(root.val); }} |
后序遍历的迭代，也需要一个标识要区分一个节点的左右孩子是否已经访问过了，如果没有，则依次访问其左右孩子，如果访问过了，则访问该节点。为此，我们用一个 pre 变量来表示上一个访问的节点，如果上一个访问的节点是当前节点的左孩子或右孩子，那么说明当前节点的左右孩子已经访问过了，那么就可以访问该节点了，否则，则需要进入左右孩子依次访问。代码如下：
|
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
|
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if (root != null) stack.push(root); TreeNode pre = root; while (!stack.isEmpty()) { TreeNode curr = stack.peek(); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) { result.add(curr.val); stack.pop(); pre = curr; } else { if (curr.right != null) stack.push(curr.right); if (curr.left != null) stack.push(curr.left); } } return result; }} |
后序遍历的迭代还有另外一种比较简单的实现，我们知道先序遍历的顺序是父、左、右，而后序遍历的顺序是左、右、父，那么如果我们把先序遍历稍作修改，改成父、右、左的顺序，那么就刚好与后序遍历的顺序相反了，以如此顺序访问完，最后我们对访问结果做个反转就可以了。而先序遍历的迭代实现相对来说比较容易，仿照上面写法我们可以如下实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if (root != null) stack.push(root); while (!stack.isEmpty()) { TreeNode curr = stack.pop(); result.add(curr.val); if (curr.left != null) stack.push(curr.left); if (curr.right != null) stack.push(curr.right); } Collections.reverse(result); return result; }} |
四、总结
三种遍历的递归实现都很容易。前序遍历的迭代实现最好写，只需要一个栈就好；中序遍历最难，循环条件除了判断栈是否为空，还要判断当前节点是否为空，以表示是否左子树已经遍历完毕；后续遍历的迭代如果转化为前序遍历的迭代，就容易很多，否则，也需要记录上一个访问的节点，以表示当前节点的左右子树是否已经访问完毕。
