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

数据结构之红黑树_java 红黑树数据结构

作者：Li_阴宅 | 2024-08-19 11:45:49

赞

踩

java 红黑树数据结构

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版） 

 数据结构之AVL树-CSDN博客 通过上篇文章的学习，我们知道了AVL树的一些情况，同时也实现了AVL树的插入与验证，但同时也知道了AVL树在查找方面性能非常高，但是在频繁的插入和删除时的效率就比较低了。因此我们今天来学习一种相对效率较高的数据结构——红黑树。

目录

红黑树概念

红黑树的性质

红黑树节点的定义

红黑树的插入

红黑树的验证 

AVL树和红黑树的比较 

红黑树概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。如下图所示：

注意：这里的 NIL 是空节点的意思，但是在红黑树中空节点是我们平常所说的叶子节点，并且这个节点的颜色为黑色。

红黑树的性质

1、每个结点不是红色就是黑色；
2、根节点是黑色的；
3、如果一个节点是红色的，则它的两个孩子结点是黑色的，也就是说 没有2个连续的红色节点；
4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点数；
5、每个叶子结点都是黑色的（此处的叶子结点指的是空结点)；

由上述性质，便可推出：其中最长路径中节点个数不会超过最短路径节点个数的两倍。如下验证：

红黑树节点的定义

  1.     static class TreeNode {
  2.         public int val;
  3.         public COLOR color; // 颜色
  4.         public TreeNode left; // 左孩子
  5.         public TreeNode right; // 右孩子
  6.         public TreeNode parent; // 父亲
  7.  
  8.         public TreeNode(int val) {
  9.             this.val = val;
  10.             this.color = COLOR.RED; // 默认是红色的节点
  11.         }
  12.     }

之所以把红黑树的节点默认定义为红色，是因为在插入元素时，如果节点为黑色，就会改变从根结点不同路径到叶子结点之间的黑色节点的个数，修改十分困难，而节点为红色，只是可能会违反不能出现两个连续是红色节点的情况，修改起来比较容易。

红黑树的插入

枚举颜色：

  1. public enum COLOR {
  2.     RED,BLACK;
  3. }

根结点： 

public TreeNode root;

思路：和二叉搜索树一样，先得找到合适的位置进行插入节点的操作。 

  1.         // 判断根结点是不是为 null
  2.         if (root == null) {
  3.             root = new TreeNode(val);
  4.             root.color = COLOR.BLACK; // 根结点要改为黑色
  5.             return true;
  6.         }
  7.  
  8.         // 开始寻找要插入节点的位置
  9.         TreeNode cur = root;
  10.         TreeNode parent = null;
  11.         while (cur!= null) {
  12.             parent = cur;
  13.             if (cur.val < val) {
  14.                 cur = cur.right;
  15.             } else if (cur.val > val) {
  16.                 cur = cur.left;
  17.             } else {
  18.                 return false; // 不能插入相同的元素
  19.             }
  20.         }
  21.         // parent 是要插入的前一个位置（判断是哪棵树）
  22.         TreeNode node = new TreeNode(val);
  23.         if (val < parent.val) {
  24.             parent.left = node;
  25.         }else {
  26.             parent.right = node;
  27.         }
  28.         node.parent = parent;
  29.         cur = node;

插入操作完成之后，就得判断当前红黑树是否违反了其性质：不能出现连续的红色节点。

  1.         // 判断是否需要调整
  2.         if (parent.color == COLOR.BLACK) {
  3.             // 父亲节点为黑色，则没有改变性质，无需调整
  4.             return true;
  5.         }

接下来就是需要调整的， 根据叔叔节点是否存在和颜色划分了大概两种情况：

因为 grandfather节点原先的颜色是黑色，当调整为红色之后，可能会出现：有连续的红色节点的情况，因此还得继续往上判断，直至parent为null即可。

从这里我们可以发现：其实叔叔节点为黑色和叔叔节点不存在的处理方式是一样的。 

当然，上面两种只是主要的情况，还有 parent 和 uncle 所处的位置不同，以及cur 所处的位置不同步，会细分出很多种情况。

检查修改代码实现：

  1.         // 判断是否需要调整
  2.         if (parent.color == COLOR.BLACK) {
  3.             // 父亲节点为黑色，则没有改变性质，无需调整
  4.             return true;
  5.         }
  6.  
  7.         // 父亲节点为红色，则与性质发生冲突，需要调整
  8.         while (parent!= null && parent.color == COLOR.RED) {
  9.             // 判断叔叔节点的颜色是啥，根据这个来判断调整方式
  10.             TreeNode grandfather = parent.parent;
  11.             // 根据叔叔节点和父亲节点位置来划分不同的情况
  12.             if (parent == grandfather.left) {
  13.                 // 再判断叔叔节点是否存在，根据叔叔节点的情况来处理
  14.                 TreeNode uncle = grandfather.right;
  15.                 if (uncle!= null && uncle.color == COLOR.RED) {
  16.                     // 修改叔叔节点、父亲节点和祖父节点的颜色，然后继续判断
  17.                     grandfather.color = COLOR.RED;
  18.                     uncle.color = COLOR.BLACK;
  19.                     parent.color = COLOR.BLACK;
  20.                     cur = grandfather;
  21.                     parent = cur.parent;
  22.                 } else { // uncle 为 null 或者 uncle 为黑色
  23.                     // 判断 cur 的位置在 parent 的哪边
  24.                     if (cur == parent.left) {
  25.                         // uncle 为 null 和不为 null 直接右旋祖父节点，然后再修改颜色
  26.                         rotateRight(grandfather);
  27.                         grandfather.color = COLOR.RED;
  28.                         parent.color = COLOR.BLACK;
  29.                     } else { // cur == parent.right
  30.                         // 左旋parent，再交换
  31.                         rotateLeft(parent);
  32.                         TreeNode tmp = parent;
  33.                         parent = cur;
  34.                         cur = tmp;
  35.                         // 经过上面的处理，变成了cur为parent的left的情况
  36.                         rotateRight(grandfather);
  37.                         grandfather.color = COLOR.RED;
  38.                         parent.color = COLOR.BLACK;
  39.                     }
  40.                 }
  41.             } else { // parent == grandfather.right
  42.                 // 再判断叔叔节点是否存在，根据叔叔节点的情况来处理
  43.                 TreeNode uncle = grandfather.left;
  44.                 if (uncle!= null && uncle.color == COLOR.RED) {
  45.                     // 修改叔叔节点、父亲节点和祖父节点的颜色，然后继续判断
  46.                     grandfather.color = COLOR.RED;
  47.                     uncle.color = COLOR.BLACK;
  48.                     parent.color = COLOR.BLACK;
  49.                     cur = grandfather;
  50.                     parent = cur.parent;
  51.                 } else { // uncle 为 null 或者 uncle 为黑色
  52.                     // 判断 cur 的位置在 parent 的哪边
  53.                     if (cur == parent.right) {
  54.                         rotateLeft(grandfather);
  55.                         grandfather.color = COLOR.RED;
  56.                         parent.color = COLOR.BLACK;
  57.                     } else { // cur == parent.left
  58.                         // 先变为cur == parent.right的情况
  59.                         rotateRight(parent);
  60.                         TreeNode tmp = parent;
  61.                         parent = cur;
  62.                         cur = tmp;
  63.                         // 再进行上面的处理
  64.                         rotateLeft(grandfather);
  65.                         grandfather.color = COLOR.RED;
  66.                         parent.color = COLOR.BLACK;
  67.                     }
  68.                 }
  69.             }
  70.         }
  71.         root.color = COLOR.BLACK; // 把根结点修改为黑色
  72.         return true;

左单旋代码实现：（思路可见AVL树的博客文章）

  1.     private void rotateLeft(TreeNode parent) {
  2.         TreeNode subR = parent.right;
  3.         TreeNode subRL = subR.left;
  4.  
  5.         TreeNode parentP = parent.parent;
  6.         // 修改四个指针的指向
  7.         parent.parent = subR;
  8.         parent.right = subRL;
  9.         if (subRL != null) {
  10.             subRL.parent = parent;
  11.         }
  12.         subR.left = parent;
  13.         // 修改本级根结点和上级树的指向
  14.         if (root == parent) {
  15.             root = subR;
  16.             root.parent = null;
  17.         } else {
  18.             subR.parent = parentP;
  19.             if (parentP.left == parent) {
  20.                 parentP.left = subR;
  21.             } else {
  22.                 parentP.right = subR;
  23.             }
  24.         }
  25.     }

右单旋代码实现：（思路可见AVL树博客文章）

  1.     private void rotateRight(TreeNode parent) {
  2.         TreeNode subL = parent.left;
  3.         TreeNode subLR = subL.right;
  4.  
  5.         TreeNode parentP = parent.parent;
  6.         // 修改四个指针的指向
  7.         parent.parent = subL;
  8.         parent.left = subLR;
  9.         if (subLR != null) {
  10.             subLR.parent = parent;
  11.         }
  12.         subL.right = parent;
  13.         // 修改本级根结点和上级树的指向
  14.         if (parent == root) {
  15.             root = subL;
  16.             root.parent = null;
  17.         } else {
  18.             subL.parent = parentP;
  19.             if (parentP.left == parent) {
  20.                 parentP.left = subL;
  21.             } else {
  22.                 parentP.right = subL;
  23.             }
  24.         }
  25.     }

处理的思路：

1、先判断父亲节点和叔叔节点在哪边；

2、再根据叔叔节点是否存在以及颜色来分别处理：

        2.1、叔叔节点存在且为红色，就是修改颜色再继续检查；

        2.2、叔叔节点不存在（NIL也是黑色）或者叔叔节点为红色，就是进行旋转处理（旋转需要判断cur具体是在哪边，从而进行不同的旋转）； 

红黑树构建完成之后，就得开始验证这棵二叉树是不是一棵红黑树。

红黑树的验证 

我们是利用红黑树的性质来进行验证的。

1、是一棵二叉搜索树。因此采取中序遍历的方式输出，看是不是一棵二叉搜索树；

代码实现：

  1.     // 中序遍历：检查是否为有序序列
  2.     public void inorder(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         inorder(root.left);
  7.         System.out.print(root.val+" ");
  8.         inorder(root.right);
  9.     }

  2、根结点一定得是黑色的；

3、不能出现两个连续的红色节点；

思路：遍历树的所有结点，判断这个节点的颜色是不是和其父亲节点一样都是红色。如果是，则返回false，否则一直判断下去，直至全部遍历完成，返回true。

代码实现：

  1.     private boolean isContinuousRedNodes(TreeNode root) {
  2.         if (root == null) {
  3.             return true;
  4.         }
  5.         // 该节点为红色
  6.         if (root.color == COLOR.RED) {
  7.             // 其父亲节点也为红色
  8.             if (root.parent != null && root.parent.color == COLOR.RED) {
  9.                 System.out.println("违反了性质：连续出现了两个红色的节点");
  10.                 // return false; 这个可有可无
  11.             }
  12.         }
  13.         // 递归判断左子树和右子树
  14.         return isContinuousRedNodes(root.left) && isContinuousRedNodes(root.right);
  15.     }

4、从根结点到不同路径上的叶子节点之间的黑色节点个数要相同。 

思路：先记录任意一条从根结点到叶子结点之间的黑色节点的个数。然后再遍历树的路径判断是否一致。如果不一致，就返回false，一致就一直判断，直至返回true。

代码实现：

  1.     // 求某条路径上的所有黑色节点个数
  2.     private int getBlckCount(TreeNode root) {
  3.         TreeNode cur = root;
  4.         int count = 0;
  5.         while (cur != null) {
  6.             if (cur.color == COLOR.BLACK) {
  7.                 count++;
  8.             }
  9.             cur = cur.left;
  10.         }
  11.         return count;
  12.     }
  13.  
  14.  
  15.     private boolean sameBlackNodes(TreeNode root, int pathBlack, int sameBlackCount) {
  16.         if (root == null) {
  17.             return true;
  18.         }
  19.         if (root.color == COLOR.BLACK) {
  20.             pathBlack++;
  21.         }
  22.         // 到叶子节点了，就得进行比较
  23.         if (root.left == null && root.right == null) {
  24.             if (pathBlack != sameBlackCount) {
  25.                 System.out.println("违反了性质：每条路径上黑色的节点个数是不一样的！");
  26.                 // return false; 可有可无
  27.             } 
  28.         }
  29.         return sameBlackNodes(root.left, pathBlack, sameBlackCount)
  30.                 && sameBlackNodes(root.right, pathBlack, sameBlackCount);
  31.     }

剩余代码：

  1.     public boolean isRBTree(TreeNode root) {
  2.         // 就是看是否满足红黑树的性质
  3.         // 1、根结点是不是黑色
  4.         if (root.color != COLOR.BLACK) {
  5.             System.out.println("违反了性质：根节点必须是黑色的！");
  6.         }
  7.         int sameBlackCount = getBlckCount(root);
  8.         // 是不是存在两个连续的红色节点 && 是不是不同；路径上有相同的黑色节点个数
  9.         return isContinuousRedNodes(root) && sameBlackNodes(root, 0, sameBlackCount);
  10.     }

测试代码：

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         //int[] array =  {16, 3, 7, 11, 9, 26, 18, 14, 15};
  4.         int[] array = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};
  5.         RBTree rbTree = new RBTree();
  6.         for (int i = 0; i < array.length; i++) {
  7.             rbTree.insert(array[i]);
  8.         }
  9.         System.out.println(rbTree.isRBTree(rbTree.root));
  10.         rbTree.inorder(rbTree.root);
  11.     }
  12. }

AVL树和红黑树的比较 

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。 就像在 Java集合框架中的：TreeMap、TreeSet底层使用的就是红黑树。

好啦！本期 数据结构之红黑树 的学习之旅就到此结束啦！我们下一期再一起学习吧！

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

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

  

闽ICP备14008679号