首页 > 基础资料 博客日记
Java中的红黑树（如果想知道Java中有关红黑树的知识点，那么只看这一篇就足够了！）
2024-09-24 00:00:06基础资料围观106次
前言：红黑树作为一种自平衡的二叉搜索树，在计算机科学领域具有极其重要的地位。它通过颜色约束和旋转操作保持树的高度平衡，从而保证了查找、插入、删除等操作的高效性。红黑树广泛应用于操作系统的调度算法、数据库索引、Java集合框架等领域。
✨✨✨这里是秋刀鱼不做梦的BLOG
✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客
写在前面
Java中红黑树是一种高级的数据结构，相较于前边的线性表，二叉树，哈希表难上许多，如何读者没有二叉搜索树、AVL树的基础是很难理解红黑树的，这里我们推荐读者先将二叉搜索树与AVL树理解之后，在来学习红黑树！！！
二叉搜索树知识：Java中的二叉搜索树（如果想知道Java中有关二叉搜索树的知识点，那么只看这一篇就足够了！）-CSDN博客
AVL树知识：
Java中的AVL树（如果想知道Java中有关AVL树的知识点，那么只看这一篇就足够了！）-CSDN博客
那么在开始学习之前，先让我们看一下本文大致的讲解内容：
目录
（2）情况二: cur为红，p为红，g为黑，u不存在/u为黑
（3）情况三: cur为红，p为红，g为黑，u不存在/u为黑
1.红黑树的概念与性质
（1）红黑树的概念
在开始正式的学习Java中的红黑树之前，先让我们了解一下红黑树的概念：
红黑树是一种自平衡的二叉搜索树。二叉搜索树的性质决定了左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。红黑树在此基础上，通过对节点着色及特定的规则来维持树的平衡。其核心特点在于红黑树通过颜色限制和旋转操作来避免二叉搜索树退化成线性链表，从而使得插入、删除和查找操作的时间复杂度始终保持在 O(log n)。
当然根据上述枯燥乏味的文字读者可能立即不了什么是红黑树，这里我们附上一张红黑树的图片：
当然，我们从这张图片中，我们就可以发现红黑树的一些性质
（2）红黑树的性质
从上图中，我们可以发现：
最长路径做多是最短路径的2倍
每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
这里读者可以简单的理解一下，下面我们在自行实现红黑树的时候，能更好的理解这些性质。
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树有什么优势吗？这里我们举出其中的差异：
-
平衡性：AVL树更加“严格平衡”，插入和删除操作后会尽可能保持树的高度平衡，因此查找操作效率较高。红黑树则更“松散”，允许树稍微倾斜，插入和删除操作效率更高。
-
旋转次数：由于红黑树的平衡要求较低，相比AVL树，红黑树在插入和删除操作中所需的旋转次数更少。AVL树为了保持高度平衡，可能会执行更多次旋转操作，因此在插入和删除时的性能稍逊于红黑树。
-
查找效率：由于AVL树保持更严格的平衡，它的查找操作在最坏情况下的性能比红黑树稍好。红黑树在最坏情况下的高度接近
2log(n)，而AVL树的高度接近log(n)，这使得AVL树在查找操作中略有优势。 -
应用场景：红黑树的插入和删除操作比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中红黑树的全部知识点了！
以上就是本篇文章的全部内容了~~~
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
标签：
相关文章
最新发布
点击排行
本站推荐
