devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

一篇文章让你彻底搞懂红黑树（带图带代码）

作者：Monodyee | 2024-06-06 19:36:38

赞

踩

红黑树

目录

1、概念及特性

2、通俗的节点名称

3、遍历及查找

4、右旋

5、左旋

6、插入

7、前驱节点

8、后继节点

9、删除

1、概念及特性

在满足排序二叉树的前提下，红黑树还满足以下5个特征：

1、每个节点要么是黑色，要么是红色；

2、根节点都是黑色，如下图中的节点40；

3、每个叶子节点（NIL）都是黑色；

4、每个红色结点的两个子结点一定都是黑色（即在任一条到达叶子节点的路径上不可能连续经过两个红色节点）；

5、任意一结点到每个叶子结点的路径都包含数量相同的黑结点，所以红黑树也是黑色完美平衡树。如下图的黑高 = 3。

备注：从特性5可以看出，除开NIL节点的情况下，任一节点不可能只存在一个黑色的子节点。

在红黑树节点中至少包含五个部分的内容：颜色、父节点、左子节点、右子节点以及真正存储的值。

  1. public class Node<T extends Comparable<T>> {
  2.         /**
  3.          * 颜色,true 是红色，false 黑色,所有的节点默认红色
  4.          */
  5.         boolean color;
  6.         /**
  7.          * 实际数值
  8.          */
  9.         T key;
  10.         /**
  11.          * 左孩子
  12.          */
  13.         Node<T> left;
  14.         /**
  15.          * 右孩子
  16.          */
  17.         Node<T> right;
  18.         /**
  19.          * 父结点
  20.          */
  21.         Node<T> parent;
  22.  
  23.         public Node(T key, Node<T> parent, Node<T> left, Node<T> right) {
  24.             this.key = key;
  25.             this.color = true;
  26.             this.parent = parent;
  27.             this.left = left;
  28.             this.right = right;
  29.         }
  30.  
  31.     }

2、通俗的节点名称

在进行红黑树操作之前，先对节点做一个通俗的称谓声明，如下图所示。

3、遍历及查找

红黑树的遍历跟其他二叉树没得任何区别，也存在前序、中序【从小到大的排序方式】及后序遍历三种遍历方式。

前序遍历：先访问当前节点，再访问左子树，最后访问右子树。

示例代码：

  1.     public void preOrder() {
  2.         preOrder(root);
  3.     }
  4.  
  5.  
  6.     private void preOrder(Node<T> tree) {
  7.         if (tree != null) {
  8.             System.out.print(tree.key + " ");
  9.             preOrder(tree.left);
  10.             preOrder(tree.right);
  11.         }
  12.     }

中序遍历：先访问左子树树，在访问当前节点，最后访问右子树。

示例代码：

  1.     public void inOrder() {
  2.         inOrder(root);
  3.     }
  4.  
  5.     private void inOrder(Node<T> tree) {
  6.         if (tree != null) {
  7.             inOrder(tree.left);
  8.             System.out.print(tree.key + " ");
  9.             inOrder(tree.right);
  10.         }
  11.     }

后序遍历：先访问左子树，再访问右子树，最后访问当前节点。

示例代码：

  1.     public void postOrder() {
  2.         postOrder(root);
  3.     }
  4.  
  5.     private void postOrder(Node<T> tree) {
  6.         if (tree != null) {
  7.             postOrder(tree.left);
  8.             postOrder(tree.right);
  9.             System.out.print(tree.key + " ");
  10.         }
  11.     }

查找：从根节点开始逐个比较。

  • 如果【key】与当前节点的【key】相等，即找到节点，返回当前节点；
  • 如果【key】大于当前节点的【key】，就在当前节点的右子树查找；
  • 如果【key】小于当前节点的【key】，就在当前节点的左子树查找。

 示例代码（递归）：

  1.     public Node<T> search(T key) {
  2.         return search(root, key);
  3.     }
  4.  
  5.     /**
  6.      * (递归实现)查找"红黑树x"中键值为key的节点
  7.      */
  8.     private Node<T> search(Node<T> x, T key) {
  9.         if (x == null)
  10.             return x;
  11.         // 比较他们的数据值，如果是大于在右子树查找，小于在左子树查找，相等的话，直接返回该节点
  12.         int cmp = key.compareTo(x.key);
  13.         if (cmp < 0)
  14.             return search(x.left, key);
  15.         else if (cmp > 0)
  16.             return search(x.right, key);
  17.         else
  18.             return x;
  19.     }

  示例代码（非递归）：

  1.     public Node<T> iterativeSearch(T key) {
  2.         return iterativeSearch(root, key);
  3.     }
  4.  
  5.     /**
  6.      * (非递归实现)查找"红黑树x"中键值为key的节点
  7.      */
  8.     private Node<T> iterativeSearch(Node<T> node, T key) {
  9.         while (node != null) {
  10.             int cmp = key.compareTo(node.key);
  11.             if (cmp < 0)
  12.                 node = node.left;
  13.             else if (cmp > 0)
  14.                 node = node.right;
  15.             else
  16.                 return node;
  17.         }
  18.         return null;
  19.     }

4、右旋

右旋概念：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

如下图所示，为以【41】为基点进行的右旋操作，红色为新增的连接线，黑色的虚线为删除的连接线。

  1. 【56】的左子节点指向【41】的右子节点【47】，同时修改【47】的父节点指向【56】；
  2. 【41】的右子节点指向【56】；
  3. 如果【56】的父节点不存在的话，设置【41】为根节点；
  4. 如果【56】的父节点存在，设置【41】的父节点指向【56】的父节点；
    1. 如果【56】是其父节点左子节点，设置【41】为【56】父节点的左子节点；
    2. 如果【56】是其父节点右子节点，设置【41】为【56】父节点的右子节点；
  5. 设置【56】的父节点指向【41】。

 

 

示例代码：

  1.     /**
  2.      * 右旋操作
  3.      *
  4.      * @param pp 旋转支点
  5.      * @return void
  6.      * @Author muyi
  7.      * @Date 15:35 2020/7/23
  8.      */
  9.     public void rightRotate(Node<T> pp) {
  10.         // 如果旋转支点为空或者其左孩子为空，无法进行旋转，直接返回
  11.         if (pp == null || pp.left == null) {
  12.             return;
  13.         }
  14.         // 获取旋转支点左孩子节点
  15.         Node<T> ppl = pp.left;
  16.         // 第一步：修改旋转支点的左子节点
  17.         // 旋转支点的左孩子节点指向其左孩子的右节点，如果左孩子的右节点不为空，同时修改其父节点的指向
  18.         pp.left = ppl.right;
  19.         if (ppl.right != null)
  20.             ppl.right.parent = pp;
  21.  
  22.         // 第二步：修改旋转支点左孩子节点父节点
  23.         ppl.parent = pp.parent;
  24.         // 父节点为空，旋转支点旋转完成后就是根节点
  25.         if (pp.parent == null) {
  26.             this.root = ppl;
  27.         } else {
  28.             // 旋转支点是右孩子节点
  29.             if (pp == pp.parent.right)
  30.                 pp.parent.right = ppl;
  31.                 // 旋转支点是左孩子节点
  32.             else
  33.                 pp.parent.left = ppl;
  34.         }
  35.         // 第三步：修改旋转支点的父节点
  36.         ppl.right = pp;
  37.         pp.parent = ppl;
  38.     }

5、左旋

左旋概念：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

如下图所示，为以【56】为基点进行的右旋操作，红色为新增的连接线，黑色的虚线为删除的连接线。

  1. 【41】的右子节点指向【56】的左子节点【47】，同时修改【47】的父节点指向【41】；
  2. 【56】的左子节点指向【41】；
  3. 如果【41】的父节点不存在的话，设置【56】为根节点；
  4. 如果【41】的父节点存在，设置【56】的父节点指向【41】的父节点；
    1. 如果【41】是其父节点左子节点，设置【56】为【41】父节点的左子节点；
    2. 如果【41】是其父节点右子节点，设置【56】为【41】父节点的右子节点；
  5. 设置【56】的父节点指向【41】。

示例代码：

  1.     /**
  2.      * 左旋操作
  3.      *
  4.      * @param pp 旋转支点
  5.      * @return void
  6.      * @Author muyi
  7.      * @Date 15:07 2020/7/23
  8.      */
  9.     public void leftRotate(Node<T> pp) {
  10.         // 如果旋转支点为空或者其右孩子节点为空，无法进行旋转，直接返回
  11.         if (pp == null || pp.right == null) {
  12.             return;
  13.         }
  14.         // 获取旋转支点的右孩子节点
  15.         Node<T> ppr = pp.right;
  16.         // 将旋转支点的右孩子节点设置为右孩子节点的左节点，如果该节点不为空，同时指定其父节点为旋转支点
  17.         pp.right = ppr.left;
  18.         if (ppr.left != null) {
  19.             ppr.left.parent = pp;
  20.         }
  21.         // 将旋转支点右孩子节点的父节点设置为旋转支点的父节点
  22.         ppr.parent = pp.parent;
  23.         // 如果旋转支点为根节点，旋转完成后，旋转支点的右孩子变成根节点
  24.         if (pp.parent == null) {
  25.             this.root = ppr;
  26.         } else {
  27.             // 旋转支点是其父亲的左子节点
  28.             if (pp.parent.left == pp)
  29.                 pp.parent.left = ppr;
  30.             else
  31.                 // 旋转支点是其父亲的右子节点
  32.                 pp.parent.right = ppr;
  33.         }
  34.         // 将旋转支点变成其右孩子节点左孩子节点
  35.         ppr.left = pp;
  36.         // 将旋转支点的父节点指向起右孩子节点
  37.         pp.parent = ppr;
  38.     }

6、插入

插入操作包括两部分工作：

6.1、查找插入的位置，这一部分工作较简单，以插入节点的【key】进行查找，直到找到其父节点即可，这个同查找操作

Ⅰ、从根结点开始查找；

Ⅱ、若根结点为空，那么插入结点作为根结点，结束返回，若根结点不为空，把根节点设为当前节点。

Ⅲ、比较当前节点的【key】和待插入节点 【key】：

  •  如果大于，且右子树为空，那么待插入节点应该作为当前节点的右孩子，插入红黑树，结束返回；否则把当前节点的右孩子设置为当前节点（移动当前节点的指针指向其右孩子），重复【Ⅲ】的操作；
  • 如果小于，且左子树为空，那么待插入节点应该作为当前节点的左孩子，插入红黑树，结束返回；否则把当前节点的左孩子设置为当前节点（移动当前节点的指针指向其左孩子），重复【Ⅲ】的操作；
  • 如果相等，那么该【key】所在节点就是插入节点，更新节点的值（也可以不更新直接返回），结束返回。

示例代码：

  1.     public void add(T data) {
  2.         Node<T> node = new Node<>(data, null, null, null);
  3.         // 如果新建结点失败，则返回。
  4.         if (node != null)
  5.             this.add(node);
  6.     }
  7.  
  8.     private void add(Node<T> node) {
  9.         // 比较结果值，小于为负数，放置于左子树，大于为正数，放置于右子树，等于为0（尽量避免等于）
  10.         int cmp;
  11.         // 用于存储新添加节点的父节点
  12.         Node<T> newParent = null;
  13.         // 中间节点，默认为根节点
  14.         Node<T> tempNode = this.root;
  15.  
  16.         // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
  17.         while (tempNode != null) {
  18.             newParent = tempNode;
  19.             cmp = node.key.compareTo(tempNode.key);
  20.             if (cmp < 0)
  21.                 tempNode = tempNode.left;
  22.             else
  23.                 tempNode = tempNode.right;
  24.         }
  25.  
  26.         node.parent = newParent;
  27.         // 如果父节点不为空，则判断当前节点是位于父节点的左子树还是右子树
  28.         if (newParent != null) {
  29.             cmp = node.key.compareTo(newParent.key);
  30.             if (cmp < 0)
  31.                 newParent.left = node;
  32.             else
  33.                 newParent.right = node;
  34.             // 如果newParent为null，说明当前添加的节点为根节点
  35.         } else {
  36.             this.root = node;
  37.         }
  38.         // 3. 将它重新修正为一颗二叉查找树(以该节点为根节点进行调整)
  39.         insertFixUp(node);
  40.     }

6.2、二插入后自平衡（insertFixUp）

红黑树的5个特性：

（1）、每个节点要么是黑色，要么是红色；

（2）、根节点都是黑色；

（3）、每个叶子节点（NIL）都是黑色；

（4）、每个红色结点的两个子结点一定都是黑色（即在任一条到达叶子节点的路径上不可能连续经过两个红色节点）；

（5）、任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

首先要记住一点，在红黑树的插入操作中，所插入的节点颜色默认为【红色】，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。那它到底会违背哪些特性呢？

  • 对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。
  • 对于"特性(2)"，显然也不会违背。在插入操作中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
  • 对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。
  • 对于"特性(4)"，是有可能违背的！

那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了，红黑树的平衡是自下而上的，如果所有的子树平衡了，那么由子树组建的红黑树肯定是平衡的。对于前面三种情况都比较简单，就不再做过多的赘述。

Ⅰ、叔叔节点（U）存在且为红色（tempNode为临时节点，指向当前待插入的节点，后面的描述亦是如此）

Ⅱ、叔叔节点不存在或者为黑色且父节点为祖父节点的左孩子—插入节点是父节点的左孩子（P.left == D）

Ⅲ、叔叔节点不存在或者为黑色且父节点为祖父节点的左孩子—插入节点是父节点的右孩子（P.right == D）

Ⅳ、叔叔节点不存在或者为黑色且父节点为祖父节点的右孩子—插入节点是父节点的右孩子（P.right== D）

Ⅴ、叔叔节点不存在或者为黑色且父节点为祖父节点的右孩子—插入节点是父节点的左孩子（P.left== D）

示例代码：

  1.      private void insertFixUp(Node<T> node) {
  2.         /**
  3.          * 红黑树的特性：
  4.          * (1) 每个节点或者是黑色，或者是红色。
  5.          * (2) 根节点是黑色。
  6.          * (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
  7.          * (4) 如果一个节点是红色的，则它的子节点必须是黑色的。
  8.          * (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
  9.          */
  10.         // 以下参数分别是：parent-父节点，uncle-叔叔节点，gParent-祖父节点
  11.         Node<T> parent, uncle, gParent, tempNode;
  12.         while (((parent = node.parent) != null) && parent.color == RED) {
  13.             // 父节点为红色，祖父节点肯定存在
  14.             gParent = parent.parent;
  15.             // 若“父节点”是“祖父节点的左孩子”
  16.             if (parent == gParent.left) {
  17.                 // Case 1条件：叔叔节点是红色：父节点、叔叔节点及祖父节点进行变色，祖父节点作为当前节点继续操作
  18.                 uncle = gParent.right;
  19.                 if ((uncle != null) && uncle.color == RED) {
  20.                     uncle.color = BLACK;
  21.                     parent.color = BLACK;
  22.                     gParent.color = RED;
  23.                     node = gParent;
  24.                     continue;
  25.                 }
  26.                 // Case 2条件：叔叔是黑色，且当前节点是右孩子：以父节点为支点进行左旋
  27.                 if (parent.right == node) {
  28.                     // 以父节点为支点进行左旋
  29.                     this.leftRotate(parent);
  30.                     // 父节点变为新的当前节点
  31.                     tempNode = parent;
  32.                     parent = node;
  33.                     node = tempNode;
  34.                     // 当完成以上操作以后，变成叔叔节点为黑色，当前节点为父节点的左孩子节点，即Case3的情况
  35.                 }
  36.                 // Case 3条件：叔叔是黑色，且当前节点是左孩子：父节点、祖父节点变色，祖父节点为支点进行右旋
  37.                 parent.color = BLACK;
  38.                 gParent.color = RED;
  39.                 this.rightRotate(gParent);
  40.             }
  41.             //若“z的父节点”是“z的祖父节点的右孩子”
  42.             else {
  43.                 // Case 1条件：叔叔节点是红色：父节点、叔叔节点及祖父节点进行变色，祖父节点作为当前节点继续操作
  44.                 uncle = gParent.left;
  45.                 if ((uncle != null) && uncle.color == RED) {
  46.                     uncle.color = BLACK;
  47.                     parent.color = BLACK;
  48.                     gParent.color = RED;
  49.                     node = gParent;
  50.                     continue;
  51.                 }
  52.                 // Case 2条件：叔叔是黑色，且当前节点是左孩子：以父节点为支点进行右旋，即Case3的情况
  53.                 if (parent.left == node) {
  54.                     this.rightRotate(parent);
  55.                     tempNode = parent;
  56.                     parent = node;
  57.                     node = tempNode;
  58.                 }
  59.                 // Case 3条件：叔叔是黑色，且当前节点是右孩子：父节点、祖父节点变色，祖父节点为支点进行左旋
  60.                 parent.color = BLACK;
  61.                 gParent.color = RED;
  62.                 this.leftRotate(gParent);
  63.             }
  64.         }
  65.         // 如果“父节点”为空，说明当前节点为根节点，将根节点设为黑色
  66.         this.root.color = false;
  67.     }

7、前驱节点

前驱节点：小于节点值的最大节点

示例代码：

  1.     public T minimum() {
  2.         Node<T> p = minimum(root);
  3.         if (p != null)
  4.             return p.key;
  5.         return null;
  6.     }
  7.  
  8.     /**
  9.      * 查找最小结点：返回tree为根结点的红黑树的最小结点。
  10.      */
  11.     private Node<T> minimum(Node<T> tree) {
  12.         if (tree == null)
  13.             return null;
  14.         while (tree.left != null)
  15.             tree = tree.left;
  16.         return tree;
  17.     }

8、后继节点

 后继节点：大于节点值的最小节点

示例代码：

  1.     public T maximum() {
  2.         Node<T> p = this.maximum(root);
  3.         if (p != null)
  4.             return p.key;
  5.  
  6.         return null;
  7.     }
  8.  
  9.     /**
  10.      * 查找最小结点：返回tree为根结点的红黑树的最大结点。
  11.      */
  12.     private Node<T> maximum(Node<T> tree) {
  13.         if (tree == null)
  14.             return null;
  15.         while (tree.right != null)
  16.             tree = tree.right;
  17.         return tree;
  18.     }

9、删除

删除操作同样分两部分进行

9.1、找到节点，并删除

这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：

① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。

② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。

③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子（只有一个右孩子，不可能是左孩子，如果是左孩子，那么后继节点就不会是它）。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。

示例代码：

  1.     public Node remove(T key) {
  2.         Node<T> node;
  3.  
  4.         if ((node = this.search(root, key)) != null)
  5.             remove(node);
  6.         return node;
  7.     }
  8.  
  9.     private void remove(Node<T> node) {
  10.         // child-孩子节点，parent-父节点，successorNode-后继节点
  11.         Node<T> child, parent, successorNode;
  12.         boolean color = node.color;
  13.         parent = node.parent;
  14.         // 被删除节点的"左右孩子都不为空"的情况。
  15.         if ((node.left != null) && (node.right != null)) {
  16.             // 被删节点的后继节点。(称为"取代节点")
  17.             // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
  18.             successorNode = node;
  19.             // 获取后继节点(大于该节点的最小值)
  20.             successorNode = successorNode.right;
  21.             while (successorNode.left != null)
  22.                 successorNode = successorNode.left;
  23.             // 以后继节点去代替node节点，"node节点"不是根节点(只有根节点不存在父节点)
  24.             if (parent != null) {
  25.                 if (parent.left == node)
  26.                     parent.left = successorNode;
  27.                 else
  28.                     parent.right = successorNode;
  29.             } else {
  30.                 // "node节点"是根节点，更新根节点。
  31.                 this.root = successorNode;
  32.             }
  33.             // child是"后继节点"的右孩子，也是需要"调整的节点"。
  34.             // "后继节点"肯定不存在左孩子！因为它是一个后继节点。
  35.             child = successorNode.right;
  36.             parent = successorNode.parent;
  37.             // 保存"取代节点"的颜色
  38.             color = successorNode.color;
  39.             // "被删除节点"是"它的后继节点的父节点"
  40.             if (parent == node) {
  41.                 parent = successorNode;
  42.             } else {
  43.                 // 如果后继节点的父节点不是node节点
  44.                 // 如果后继节点不为NULL，将父节点指向后继节点的父节点
  45.                 if (child != null)
  46.                     child.parent = parent;
  47.                 // 后继节点的父节点的左节点指向后继节点的孩子节点
  48.                 parent.left = child;
  49.                 // 后继节点的右孩子指向node节点的右节点
  50.                 successorNode.right = node.right;
  51.                 // node节点右孩子的父节点指向后继节点
  52.                 node.right.parent = successorNode;
  53.             }
  54.             // 保持node节点的元素不变
  55.             successorNode.parent = node.parent;
  56.             successorNode.color = node.color;
  57.             successorNode.left = node.left;
  58.             node.left.parent = successorNode;
  59.  
  60.             if (color == BLACK)
  61.                 removeFixUp(child, parent);
  62.             return;
  63.         }
  64.  
  65.         // 删除节点的“左孩子或右孩子不为空”的情况
  66.         if (node.left != null) {
  67.             child = node.left;
  68.         } else {
  69.             child = node.right;
  70.         }
  71.  
  72.         // 如果孩子节点不为空，设置父节点的指向
  73.         if (child != null)
  74.             child.parent = parent;
  75.  
  76.         // "node节点"不是根节点，根据node节点的位置，完成父节点孩子节点的指向
  77.         if (parent != null) {
  78.             if (parent.left == node)
  79.                 parent.left = child;
  80.             else
  81.                 parent.right = child;
  82.         } else {
  83.             this.root = child;
  84.         }
  85.  
  86.         if (color == BLACK)
  87.             removeFixUp(child, parent);
  88.     }

9.2、删除后自平衡操作

红黑树的5个特性：

（1）、每个节点要么是黑色，要么是红色；

（2）、根节点都是黑色；

（3）、每个叶子节点（NIL）都是黑色；

（4）、每个红色结点的两个子结点一定都是黑色（即在任一条到达叶子节点的路径上不可能连续经过两个红色节点）；

（5）、任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

将节点删除"后，可能违反"特性(2)、(4)、(5)"三个特性。第二步需要解决上面的三个问题，进而保持红黑树的全部特性

 

Ⅰ、替换节点是红色

换到了删除结点的位置时，由于替换节点红色，删除也了不会影响红黑树的平衡，只要把替换结点的颜色设为删除的节点的颜色即可重新平衡。

Ⅱ、替换节点是黑色

一、替换节点是其父节点的左子节点

（1）、兄弟节点是红色，根据性质4，父节点和兄弟的子节点肯定为黑色，不会有其他子情景。

处理方式：

处理：兄弟节点设置为黑色 B.red = False；父节点设置为红色 P.red = True；以父节点为支点进行左旋 leftRotate（P）。
以上操作完成后，变成情况 （2）-情况c，然后继续处理。

（2）、兄弟节点是黑色（父节点和兄弟的子节点颜色均不能确定，需要再分情况）

情况a、兄弟的右子节点是红色，左子节点任意颜色。

处理方式：兄弟节点的颜色设置为父亲的颜色 B.red = P.red；父节点的颜色设为黑色 P.red = False；兄弟节点的右子节点设为黑色 BR.red = False；以父节点为支点进行左旋 leftRotate（P）。

情况b、兄弟节点的右子节点是黑色，左子节点是红色。

处理方式：兄弟节点设为红色 B.red = True；兄弟节点的左子设为黑色 BL.red = False；以兄弟节点为支点进行右旋 rightRotate（B）。以上操作完成后，变成（2）-情况a，然后继续处理。

情况c、兄弟节点的右、左子节点均是黑色。

处理方式：兄弟节点设为红色 B.red = True；将父节点作为新的替换节点 D = P，重新进行删除节点的处理。

二、替换节点是其父节点的右子结点

（1）、兄弟节点是红色，根据性质4，父节点和兄弟的子节点肯定为黑色，不会有其他子情景。

处理方式：

处理：兄弟节点设置为黑色 B.red = False；父节点设置为红色 P.red = True；以父节点为支点进行左旋rightRotate（P）。
以上操作完成后，变成情况（2）-情况c，然后继续处理。

（2）、兄弟节点是黑色（父节点和兄弟的子节点颜色均不能确定，需要再分情况）

情况a、兄弟的左子节点是红色，右子节点任意颜色。

处理方式：兄弟节点的颜色设置为父亲的颜色 B.red = P.red；父节点的颜色设为黑色 P.red = False；兄弟节点的右子设为黑色 BL.red = False；以父节点为支点进行右旋 rightRotate（P）。

情况b、兄弟节点的左子节点是黑色，右子节点是红色

处理方式：兄弟节点设为红色 B.red = True；兄弟节点的左孩子设为黑色 BR.red = False；以兄弟节点为支点进行左旋 leftRotate（B）。以上操作完成后，变成（2）-情况a，然后继续处理。

情况c、兄弟节点的右、左子节点均是黑色。

处理方式：兄弟节点设为红色 B.red = True；将父节点作为新的替换节点 D = P，重新进行删除节点的处理。

示例代码：

  1.      /**
  2.      * 红黑树删除修正函数
  3.      * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
  4.      * 目的是将它重新塑造成一颗红黑树。
  5.      * 参数说明：
  6.      * node 待修正的节点
  7.      * parent 待修正节点的父节点
  8.      */
  9.     private void removeFixUp(Node<T> node, Node<T> parent) {
  10.         Node<T> brother;
  11.         while ((node == null || node.color == BLACK) && (node != root)) {
  12.             if (parent.left == node) {
  13.                 brother = parent.right;
  14.                 /**
  15.                  * Case 1: 兄弟节点是红色，这样操作完成后，会变成case2、3、4情况中的一种
  16.                  * (01) 将x的兄弟节点设为“黑色”。
  17.                  * (02) 将x的父节点设为“红色”。
  18.                  * (03) 对x的父节点进行左旋。
  19.                  * (04) 左旋后，重新设置x的兄弟节点。
  20.                  */
  21.                 if (brother != null && brother.color == RED) {
  22.                     brother.color = BLACK;
  23.                     parent.color = RED;
  24.                     this.leftRotate(parent);
  25.                     brother = parent.right;
  26.                 }
  27.                 /**
  28.                  * Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
  29.                  * (01) 将x的兄弟节点设为“红色”。
  30.                  * (02) 设置“x的父节点”为“新的x节点”。
  31.                  */
  32.                 if ((brother.left == null || brother.left.color == BLACK) && (brother.right == null || brother.right.color == BLACK)) {
  33.                     brother.color = RED;
  34.                     node = parent;
  35.                     parent = node.parent;
  36.                 } else {
  37.                     /**
  38.                      * Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。操作完成后变成case 4的情况
  39.                      * (01) 将x兄弟节点的左孩子设为“黑色”。
  40.                      * (02) 将x兄弟节点设为“红色”。
  41.                      * (03) 对x的兄弟节点进行右旋。
  42.                      * (04) 右旋后，重新设置x的兄弟节点
  43.                      */
  44.                     if (brother.right == null || brother.right.color == BLACK) {
  45.                         brother.left.color = BLACK;
  46.                         brother.color = RED;
  47.                         this.rightRotate(brother);
  48.                         brother = parent.right;
  49.                     }
  50.                     /**
  51.                      *  Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
  52.                      * (01) 将x父节点颜色 赋值给 x的兄弟节点。
  53.                      * (02) 将x父节点设为“黑色”。
  54.                      * (03) 将x兄弟节点的右子节设为“黑色”。
  55.                      * (04) 对x的父节点进行左旋。
  56.                      * (05) 设置“x”为“根节点”。
  57.                      */
  58.                     brother.color = parent.color;
  59.                     parent.color = BLACK;
  60.                     brother.right.color = BLACK;
  61.                     this.leftRotate(parent);
  62.                     node = root;
  63.                     break;
  64.                 }
  65.             } else {
  66.                 // 当前节点是父节点的右节点
  67.                 brother = parent.left;
  68.                 /**
  69.                  * Case 1: 兄弟节点是红色，
  70.                  * (01) 将x的兄弟节点设为“黑色”。
  71.                  * (02) 将x的父节点设为“红色”。
  72.                  * (03) 对x的父节点进行右旋。
  73.                  * (04) 左旋后，重新设置x的兄弟节点
  74.                  * 这样操作完成后，会变成case2、3、4情况中的一种
  75.                  */
  76.                 if (brother.color == RED) {
  77.                     brother.color = BLACK;
  78.                     parent.color = RED;
  79.                     this.rightRotate(parent);
  80.                     brother = parent.left;
  81.                 }
  82.                 /**
  83.                  * Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
  84.                  * (01) 将x的兄弟节点设为“红色”。
  85.                  * (02) 设置“x的父节点”为“新的x节点”。
  86.                  */
  87.                 if ((brother.left == null || brother.left.color == BLACK) && (brother.right == null || brother.right.color == BLACK)) {
  88.                     brother.color = RED;
  89.                     node = parent;
  90.                     parent = node.parent;
  91.                 } else {
  92.                     /**
  93.                      * Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。这样操作完成后就变成Case 4
  94.                      * (01) 将x兄弟节点的左孩子设为“黑色”。
  95.                      * (02) 将x兄弟节点设为“红色”。
  96.                      * (03) 对x的兄弟节点进行左旋。
  97.                      * (04) 右旋后，重新设置x的兄弟节点。
  98.                      */
  99.                     if (brother.left == null || brother.left.color == BLACK) {
  100.                         brother.right.color = BLACK;
  101.                         brother.color = RED;
  102.                         this.leftRotate(brother);
  103.                         brother = parent.left;
  104.                     }
  105.                     /**
  106.                      * Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
  107.                      * (01) 将x父节点颜色 赋值给 x的兄弟节点。
  108.                      * (02) 将x父节点设为“黑色”。
  109.                      * (03) 将x兄弟节点的右子节设为“黑色”。
  110.                      * (04) 对x的父节点进行左旋。
  111.                      * (05) 设置“x”为“根节点”。
  112.                      */
  113.                     brother.color = parent.color;
  114.                     parent.color = BLACK;
  115.                     brother.left.color = BLACK;
  116.                     this.rightRotate(parent);
  117.                     node = this.root;
  118.                     break;
  119.                 }
  120.             }
  121.         }
  122.         if (node != null)
  123.             node.color = BLACK;
  124.     }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/682291
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号