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

      2020-01-12 05:27      JAVA编程
红黑树问题是各大计算机考研命题以及面试算法题目中的热门,接下来我们为大家图解红黑树及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;  }}


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