当前位置： 首页 > news >正文

Java中的红黑树（如果想知道Java中有关红黑树的知识点，那么只看这一篇就足够了！）

news 来源：原创 2024/9/19 0:06:11

        前言：红黑树作为一种自平衡的二叉搜索树，在计算机科学领域具有极其重要的地位。它通过颜色约束和旋转操作保持树的高度平衡，从而保证了查找、插入、删除等操作的高效性。红黑树广泛应用于操作系统的调度算法、数据库索引、Java集合框架等领域。

✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

写在前面

        Java中红黑树是一种高级的数据结构，相较于前边的线性表，二叉树，哈希表难上许多，如何读者没有二叉搜索树、AVL树的基础是很难理解红黑树的，这里我们推荐读者先将二叉搜索树与AVL树理解之后，在来学习红黑树！！！

二叉搜索树知识：Java中的二叉搜索树（如果想知道Java中有关二叉搜索树的知识点，那么只看这一篇就足够了！）-CSDN博客

AVL树知识：

Java中的AVL树（如果想知道Java中有关AVL树的知识点，那么只看这一篇就足够了！）-CSDN博客

那么在开始学习之前，先让我们看一下本文大致的讲解内容：

目录

写在前面

1.红黑树的概念与性质

        （1）红黑树的概念

        （2）红黑树的性质

2.红黑树的节点的定义

3.红黑树的插入

        （1）情况一: cur为红，p为红，g为黑，u存在且为红

        （2）情况二: cur为红，p为红，g为黑，u不存在/u为黑

        （3）情况三: cur为红，p为红，g为黑，u不存在/u为黑

4.红黑树的验证

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2.检测其是否满足红黑树的性质

解释：

5.红黑树与AVL树的比较

6.红黑树的应用

1. Java中的TreeMap和TreeSet

2. 数据库索引

3. 操作系统调度器

1.红黑树的概念与性质

        （1）红黑树的概念

        在开始正式的学习Java中的红黑树之前，先让我们了解一下红黑树的概念：

        红黑树是一种自平衡的二叉搜索树。二叉搜索树的性质决定了左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。红黑树在此基础上，通过对节点着色及特定的规则来维持树的平衡。其核心特点在于红黑树通过颜色限制和旋转操作来避免二叉搜索树退化成线性链表，从而使得插入、删除和查找操作的时间复杂度始终保持在 O(log n)。

当然根据上述枯燥乏味的文字读者可能立即不了什么是红黑树，这里我们附上一张红黑树的图片：

当然，我们从这张图片中，我们就可以发现红黑树的一些性质

        （2）红黑树的性质

        从上图中，我们可以发现：

  1. 最长路径做多是最短路径的2倍

  2. 每个结点不是红色就是黑色

  3. 根节点是黑色的

  4. 如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】

  5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点

  6. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

这里读者可以简单的理解一下，下面我们在自行实现红黑树的时候，能更好的理解这些性质。

2.红黑树的节点的定义

        在了解完了红黑树的基本概念之后，我们发现，红黑树就是一棵带有颜色的近似平衡的二叉搜索树，那么现在让我们看一下如何去定义红黑树的节点。

        红黑树的节点定义与普通二叉树节点相似，但多了一个颜色属性，用于记录节点的颜色（红或黑），节点的基本定义如下：

public static class TreeNode {public TreeNode left;    // 左子节点public TreeNode right;   // 右子节点public TreeNode parent;  // 父节点public int val;          // 节点值public Color color;      // 节点颜色// 枚举类型定义红色和黑色public enum Color {RED, BLACK}// 构造函数，默认节点颜色为红色public TreeNode(int val) {this.val = val;this.color = Color.RED; // 新插入节点初始为红色}
}

其中的属性为：

  • left：指向左子节点。
  • right：指向右子节点。
  • parent：指向父节点。
  • val：节点的值（整数类型）。
  • color：节点的颜色，表示为Color类型（红色或黑色）。

通过上述的讲解，现在我们就了解了红黑树的节点的定义了！！！

3.红黑树的插入

        当我们了解完了什么是红黑树以及红黑树的节点如何定义之后，现在让我们自行实现一个红黑树的代码，创建一棵红黑树的大致流程为：

1. 按照二叉搜索的树规则插入新节点；
2. 检测新节点插入后，红黑树的性质是否造到破坏；

而对于红黑树中节点的插入（插入节点之后），有以下几种情况：（约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点）

        （1）情况一: cur为红，p为红，g为黑，u存在且为红

        ——解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

        （2）情况二: cur为红，p为红，g为黑，u不存在/u为黑

        ——解决方式：p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转，p、g变色--p变黑，g变红

        （3）情况三: cur为红，p为红，g为黑，u不存在/u为黑

——解决方式：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，则转换成了情况2

        这样我们只需要对每种情况进行处理即可！！！以下为整体实现的代码：

public void insert(int val) {// 如果当前树为空，直接插入根节点，并将根节点设为黑色if (root == null) {root = new TreeNode(val);root.color = Color.BLACK;return;}TreeNode prev = null;TreeNode cur = root;// 寻找插入位置while (cur != null) {if (cur.val < val) {prev = cur;cur = cur.right;  // 继续在右子树查找} else if (cur.val > val) {prev = cur;cur = cur.left;   // 继续在左子树查找} else {return;  // 如果已存在相同值的节点，直接返回，不进行插入}}// 创建新节点，并根据比较结果插入到合适位置TreeNode node = new TreeNode(val);if (prev.val < val) {prev.right = node;  // 插入到右子节点} else {prev.left = node;   // 插入到左子节点}cur = node;TreeNode parent = cur.parent;// 修正红黑树的性质while (parent != null && parent.color == Color.RED) {TreeNode grandParent = parent.parent;// 情况1：父节点是祖父节点的左子节点if (grandParent.left == parent) {TreeNode uncle = grandParent.right;// 情况1.1：叔叔节点为红色if (uncle != null && uncle.color == Color.RED) {parent.color = Color.BLACK;  // 将父节点设为黑色uncle.color = Color.BLACK;   // 将叔叔节点设为黑色grandParent.color = Color.RED;  // 将祖父节点设为红色cur = grandParent;  // 将当前节点指向祖父节点，继续修正parent = cur.parent;  // 更新父节点} else {// 情况1.2：叔叔节点为黑色，当前节点是右子节点if (parent.right == cur) {rotateLeft(parent);  // 左旋父节点TreeNode temp = parent;parent = cur;cur = temp;  // 更新当前节点和父节点}// 情况1.3：叔叔节点为黑色，当前节点是左子节点rotateRight(grandParent);  // 右旋祖父节点parent.color = Color.BLACK;  // 将父节点设为黑色grandParent.color = Color.RED;  // 将祖父节点设为红色}} else {// 情况2：父节点是祖父节点的右子节点TreeNode uncle = grandParent.left;// 情况2.1：叔叔节点为红色if (uncle != null && uncle.color == Color.RED) {parent.color = Color.BLACK;  // 将父节点设为黑色uncle.color = Color.BLACK;   // 将叔叔节点设为黑色grandParent.color = Color.RED;  // 将祖父节点设为红色cur = grandParent;  // 将当前节点指向祖父节点，继续修正parent = cur.parent;  // 更新父节点} else {// 情况2.2：叔叔节点为黑色，当前节点是左子节点if (parent.left == cur) {rotateRight(parent);  // 右旋父节点TreeNode temp = parent;parent = cur;cur = temp;  // 更新当前节点和父节点}// 情况2.3：叔叔节点为黑色，当前节点是右子节点rotateLeft(grandParent);  // 左旋祖父节点grandParent.color = Color.RED;  // 将祖父节点设为红色parent.color = Color.BLACK;  // 将父节点设为黑色}}}// 保证根节点始终是黑色root.color = Color.BLACK;
}

其中的左旋操作：

public void rotateLeft(TreeNode prev) {// 取得当前节点的右子节点TreeNode subR = prev.right;// 取得右子节点的左子节点TreeNode subRL = subR.left;// 将右子节点的左子节点连接到当前节点的右子节点上subR.left = prev;// 将当前节点的右子节点连接到右子节点的左子节点上prev.right = subRL;// 取得当前节点的父节点TreeNode parParent = prev.parent;// 更新当前节点的父节点为右子节点prev.parent = subR;// 如果右子节点的左子节点不为空，更新它的父节点为当前节点if (subRL != null) {subRL.parent = prev;}// 如果当前节点是根节点，将右子节点设为新的根节点if (prev == root) {root = subR;subR.parent = null; // 更新根节点的父节点为 null} else {// 否则，根据当前节点是父节点的左子节点还是右子节点来更新父节点的子节点if (parParent.left == prev) {parParent.left = subR;subR.parent = parParent;} else {parParent.right = subR;subR.parent = parParent;}}
}

其中右旋操作：

public void rotateRight(TreeNode prev) {// 取得当前节点的左子节点TreeNode subL = prev.left;// 取得左子节点的右子节点TreeNode subLR = subL.right;// 将左子节点的右子节点连接到当前节点的左子节点上prev.left = subLR;// 将当前节点连接到左子节点的右子节点上subL.right = prev;// 如果左子节点的右子节点不为空，更新它的父节点为当前节点if (subLR != null) {subLR.parent = prev;}// 取得当前节点的父节点TreeNode parParent = prev.parent;// 更新当前节点的父节点为左子节点prev.parent = subL;// 如果当前节点是根节点，将左子节点设为新的根节点if (prev == root) {root = subL;subL.parent = null; // 更新根节点的父节点为 null} else {// 否则，根据当前节点是父节点的左子节点还是右子节点来更新父节点的子节点if (parParent.left == prev) {parParent.left = subL;subL.parent = parParent;} else {parParent.right = subL;subL.parent = parParent;}}
}

——这里的左旋与右旋和AVL树中的左旋与右旋是相同的！！！

当读者耐心的读完并理解完上述的代码之后，现在我们在总体的梳理一下上述代码的整理逻辑：

1. 查找插入位置：

        从根节点开始，比较插入的值 val 和当前节点的值，确定插入位置。如果插入值小于当前节点，则继续在左子树查找；否则在右子树查找。这样确保了插入的新节点满足二叉搜索树的性质。

2. 插入节点：

        一旦找到合适的位置，就将新节点插入到树中。如果父节点的值小于插入值，新节点作为父节点的右子节点；否则作为左子节点。

3. 调整红黑树的性质：

        由于插入的新节点默认是红色，可能会违反红黑树的性质。红黑树的主要性质包括：

  • 根节点必须是黑色。

  • 红色节点的子节点必须是黑色（即红色节点不能有红色子节点）。

  • 从任意节点到其叶子节点的每条路径上黑色节点的数量必须相同。

为了恢复红黑树的平衡性，可能需要进行以下调整：

  • 重新着色：如果插入节点的父节点和叔叔节点都是红色，那么父节点和叔叔节点重新染成黑色，祖父节点染成红色，并继续检查祖父节点。

  • 旋转操作：当叔叔节点是黑色或不存在时，通过旋转来调整树的结构。左旋或右旋操作可以修正父节点和祖父节点之间的关系，使树重新达到平衡。

4. 保持根节点为黑色：

        红黑树的一个重要性质是根节点必须始终是黑色，因此在所有调整完成后，确保根节点被设置为黑色。

这样我们就完成了红黑树节点的插入操作了！！！

4.红黑树的验证

        当我们创建完了一棵红黑树之后，我们如何去验证其为一棵红黑树呢？验证一棵树为红黑树，我们需要从其定义性质入手。

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

public void inorder(TreeNode root) {// 如果当前节点为空，则返回（递归终止条件）if (root == null) {return;}// 递归访问左子树inorder(root.left);// 访问当前节点System.out.println(root.val);// 递归访问右子树inorder(root.right);
}

2.检测其是否满足红黑树的性质

public boolean isRBTree(TreeNode root) {// 如果根节点为空，空树被认为是红黑树if (root == null) {return true;}// 根节点必须是黑色if (root.color == Color.RED) {return false;}// 计算从根节点到最左边叶子节点路径上的黑色节点数量int prevBlackNodeNum = calBlackNumber(root);// 检查红色节点是否有连续的红色节点，并检查所有路径上的黑色节点数量是否一致return examRedNode(root) && examBlackNode(root, 0, prevBlackNodeNum);
}// 计算从根节点到最左边叶子节点路径上的黑色节点数量
private int calBlackNumber(TreeNode root) {int prevBlackNodeNum = 0;TreeNode cur = root;// 沿着左子树遍历，计算黑色节点数量while (cur.left != null) {if (cur.color == Color.BLACK) {prevBlackNodeNum++;}cur = cur.left;}return prevBlackNodeNum;
}// 检查红色节点的父节点是否也为红色，红色节点不能连续
private boolean examRedNode(TreeNode root) {if (root == null) {return true;}// 如果当前节点是红色，检查其父节点是否也为红色if (root.color == Color.RED) {TreeNode parent = root.parent;if (parent.color == Color.RED) {return false;}}// 递归检查左右子树return examRedNode(root.left) && examRedNode(root.right);
}// 检查从根节点到每个叶子节点路径上的黑色节点数量是否一致
private boolean examBlackNode(TreeNode root, int blackNodeNum, int prevBlackNodeNum) {if (root == null) {return true;}// 如果当前节点是黑色，黑色节点计数加一if (root.color == Color.BLACK) {blackNodeNum++;}// 如果到达叶子节点，检查路径上的黑色节点数量是否与最左边路径一致if (root.left == null && root.right == null) {if (blackNodeNum != prevBlackNodeNum) {return false;}}// 递归检查左右子树return examBlackNode(root.left, blackNodeNum, prevBlackNodeNum)&& examBlackNode(root.right, blackNodeNum, prevBlackNodeNum);
}

解释：

  • isRBTree 方法：

    • 如果根节点为空，认为是红黑树。
    • 根节点必须是黑色。
    • 计算最左边路径的黑色节点数量。
    • 检查红色节点是否有连续红色节点，并确保所有路径上的黑色节点数量一致。

  • calBlackNumber 方法：

    • 计算从根节点到最左边叶子节点路径上的黑色节点数量。

  • examRedNode 方法：

    • 确保红色节点不能有红色的父节点。

  • examBlackNode 方法：

    • 确保从根节点到每个叶子节点的路径上黑色节点数量一致。

        这样我们就知道了如何判断一棵树是否为红黑树了！

5.红黑树与AVL树的比较

        学习完了红黑树之后，读者可能会有疑问了，红黑树相较于前面所学的AVL树有什么优势吗？这里我们举出其中的差异：

  1. 平衡性：AVL树更加“严格平衡”，插入和删除操作后会尽可能保持树的高度平衡，因此查找操作效率较高。红黑树则更“松散”，允许树稍微倾斜，插入和删除操作效率更高。

  2. 旋转次数：由于红黑树的平衡要求较低，相比AVL树，红黑树在插入和删除操作中所需的旋转次数更少。AVL树为了保持高度平衡，可能会执行更多次旋转操作，因此在插入和删除时的性能稍逊于红黑树。

  3. 查找效率：由于AVL树保持更严格的平衡，它的查找操作在最坏情况下的性能比红黑树稍好。红黑树在最坏情况下的高度接近 2log(n)，而AVL树的高度接近 log(n)，这使得AVL树在查找操作中略有优势。

  4. 应用场景：红黑树的插入和删除操作比AVL树更快，因此在需要频繁插入和删除的场景中，红黑树更为合适。比如Java中的TreeMap和TreeSet等数据结构都采用了红黑树。而AVL树则更适合用于查找频率较高且对平衡性要求较高的场景。

AVL树与红黑树的总结对比：

特性红黑树AVL树
平衡策略较为宽松严格平衡
插入删除效率高较低
查找效率较低高
旋转次数较少较多
应用场景插入/删除频繁查找频繁

这样我们就了解了红黑树与AVL树差异了

6.红黑树的应用

        红黑树因其高效的性能和自平衡性质，广泛应用于各种数据结构中。Java标准库中的一些重要类也基于红黑树来实现。

1. Java中的TreeMap和TreeSet

TreeMap和TreeSet是Java集合框架中的重要实现，底层数据结构是红黑树。TreeMap提供了有序的键值对存储，而TreeSet则提供了有序的集合元素存储。它们都通过红黑树保证插入、删除和查找操作的时间复杂度为 O(log n)。

2. 数据库索引

在某些数据库系统中，红黑树也可以用于索引结构的实现。通过红黑树的数据平衡特性，数据库可以高效地执行增删改查操作，尤其是在处理大量数据时，红黑树能保证数据的有序性和访问效率。

3. 操作系统调度器

红黑树也被广泛用于操作系统调度器中。例如，在Linux的CFS（完全公平调度器）中，红黑树被用来高效地管理进程的优先级和时间片，确保进程调度的公平性和效率。

        这样我们就学完了有关Java中红黑树的全部知识点了！

以上就是本篇文章的全部内容了~~~

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【渗透测试】-vulnhub源码框架漏洞-Os-hackNos-1
  • 运维工程师面试整理-数据库
  • el-input设置type=‘number‘和v-model.number的区别
  • Longman Dictionary of Contemporary English (朗文当代高级英语辞典)
  • 【ARM】Trustzone和安全架构
  • golang学习笔记18——golang 访问 mysql 数据库全解析
  • Amoco：一款针对二进制源码的安全分析工具
  • HC-SR04超声波传感器详解（STM32）
  • scantf
  • k8s介绍及部署
  • 【Kubernetes】常见面试题汇总（二十四）
  • PWN二进制安全修仙秘籍【第一章#工具篇01】WLS配置tmux分屏、oh-my-zsh命令补全
  • SOCKS4和SOCKS5的区别是什么？
  • Redis Universe: 探索无边界的数据处理星系
  • 上线跨境电商商城的步骤
  • #Java异常处理
  • [数据结构]链表的实现在PHP中
  • 【399天】跃迁之路——程序员高效学习方法论探索系列（实验阶段156-2018.03.11）...
  • git 常用命令
  • Idea+maven+scala构建包并在spark on yarn 运行
  • leetcode-27. Remove Element
  • log4j2输出到kafka
  • React as a UI Runtime(五、列表)
  • React16时代，该用什么姿势写 React ?
  • 产品三维模型在线预览
  • 初识MongoDB分片
  • 动手做个聊天室，前端工程师百无聊赖的人生
  • 给Prometheus造假数据的方法
  • 实战：基于Spring Boot快速开发RESTful风格API接口
  • 使用前端开发工具包WijmoJS - 创建自定义DropDownTree控件（包含源代码）
  • 新版博客前端前瞻
  • 学习HTTP相关知识笔记
  • 用Visual Studio开发以太坊智能合约
  • postgresql行列转换函数
  • 微龛半导体获数千万Pre-A轮融资，投资方为国中创投 ...
  • ​【已解决】npm install​卡主不动的情况
  • ​LeetCode解法汇总2670. 找出不同元素数目差数组
  • ​TypeScript都不会用，也敢说会前端？
  • #数据结构 笔记一
  • ( )的作用是将计算机中的信息传送给用户,计算机应用基础 吉大15春学期《计算机应用基础》在线作业二及答案...
  • （11）MSP430F5529 定时器B
  • (day18) leetcode 204.计数质数
  • （react踩过的坑）Antd Select（设置了labelInValue）在FormItem中initialValue的问题
  • （不用互三）AI绘画：科技赋能艺术的崭新时代
  • （附源码）springboot工单管理系统 毕业设计 964158
  • （理论篇）httpmoudle和httphandler一览
  • (生成器)yield与(迭代器)generator
  • （一）UDP基本编程步骤
  • (转)ORM
  • (转)scrum常见工具列表
  • （转载）（官方）UE4--图像编程----着色器开发
  • ****Linux下Mysql的安装和配置
  • ./indexer: error while loading shared libraries: libmysqlclient.so.18: cannot open shared object fil
  • .[backups@airmail.cc].faust勒索病毒的最新威胁：如何恢复您的数据？
  • .bat批处理（九）：替换带有等号=的字符串的子串