图解红黑树及Java进行红黑二叉树遍历的方法

红黑树
红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树，也是技术面试中经常被问到的树，然而无论是书上还是网上的资料，通常都比较刻板难以理解，能不能一种比较直观的方式来理解红黑树呢？本文将以图形的方式来解释红黑树的插入与删除操作。
对树结构的学习是一个递进的过程，我们通常所接触的树都是二叉树，二叉树简单来说就是每个非叶子节点都有且只有两个孩子，分别叫做左孩子和右孩子。二叉树中有一类特殊的树叫二叉查找树，二叉查找树是一种有序的树，对于每个非叶子节点，其左子树的值都小于它，其右子树的值都大于它。比二叉查找树更进一步的是二叉平衡树，二叉平衡树除了保证有序外，还能够保持每个节点左右子树的高度相差不超过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的情况。

二叉树的遍历
二叉树的遍历有三种：前序遍历、中序遍历和后序遍历。每种遍历的实现又有递归和迭代两种，这篇文章我们来讨论如何用比较优雅的代码来实现二叉树的遍历。
首先我来定义一个二叉树的节点：

public class treenode {
  int val;
  treenode left;
  treenode right;
  
  public treenode(int x) {
    val = x;
  }
}

 
一、前序遍历（preorder traversal）
简单来讲，前序遍历就是先访问父节点，再访问左孩子，最后访问右孩子，即以父、左、右的顺序来遍历。
递归实现非常简单，代码如下：

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);
  }
}

迭代实现需要借助一个栈，存储没被访问的右节点，代码如下：

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）
简单来讲，中序遍历就是先访问左孩子，再访问父节点，最后访问右孩子，即以左、父、右的顺序遍历。
递归代码也比较容易，如下所示：

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，所以我们可以以此来区分一个节点的左子树是否已被访问过。代码如下：

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）
简单来讲，后序遍历就是先访问左孩子，在访问右孩子，最后访问父节点， 即以左、右、父的顺序遍历。
仿照中序遍历，可以很容易地写出后序遍历的递归实现：

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 变量来表示上一个访问的节点，如果上一个访问的节点是当前节点的左孩子或右孩子，那么说明当前节点的左右孩子已经访问过了，那么就可以访问该节点了，否则，则需要进入左右孩子依次访问。代码如下：

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;
  }
}

后序遍历的迭代还有另外一种比较简单的实现，我们知道先序遍历的顺序是父、左、右，而后序遍历的顺序是左、右、父，那么如果我们把先序遍历稍作修改，改成父、右、左的顺序，那么就刚好与后序遍历的顺序相反了，以如此顺序访问完，最后我们对访问结果做个反转就可以了。而先序遍历的迭代实现相对来说比较容易，仿照上面写法我们可以如下实现：

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;
  }
}

 
四、总结
三种遍历的递归实现都很容易。前序遍历的迭代实现最好写，只需要一个栈就好；中序遍历最难，循环条件除了判断栈是否为空，还要判断当前节点是否为空，以表示是否左子树已经遍历完毕；后续遍历的迭代如果转化为前序遍历的迭代，就容易很多，否则，也需要记录上一个访问的节点，以表示当前节点的左右子树是否已经访问完毕。