红黑树理解以及Java实现

article/2025/9/21 1:21:32

红黑树本身并不复杂，只是在插入删除的时候情况比较多，如果强行记忆的话会显得比较困难，而且容易忘记。所以以前对红黑树一直没有很好的掌握。恰好这次借着复习数据结构的机会，静下心来仔细的学习了一下红黑树，并用Java实现了一番。所以用这篇文章把我对红黑树的操作的理解记录下来，在理解的基础上记忆会容易得多，这样以后就不用重复学习啦！

1. 红黑树的定义

红黑树是一颗二叉查找树，且具有如下特性：
    (1) 每个节点或者是黑色，或者是红色。
    (2) 根节点是黑色。
    (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
    (4) 如果一个节点是红色的，则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。

2. 操作的核心思想

    通过上面的定义，可以看到红黑树本质上还是一颗二叉查找树，所以，对红黑树的插入删除操作都可以分为两阶段来完成，首先，将红黑树看成一颗普通的二叉查找树完成插入删除操作，然后，通过旋转以及颜色调整来使得操作后的树满足红黑树的所有特性即可。

3. 基础操作之左旋右旋

旋转操作是基础操作，后面的一些情况处理就是基于旋转来完成的。所以，首先我们需要理解左旋右旋的工作方式。
对x点进行右旋：
这里写图片描述
对y点进行左旋：
这里写图片描述

4. 核心操作之插入

说明：以下的讨论，在如下前提下进行：插入的节点为S（son），S的父亲节点为F（father），F的父亲节点为G（grandfather），而F的兄弟节点为U（uncle）。并且F为G的左儿子。（F为G的右儿子对称操作即可）

  • Step 1：执行二叉搜索树插入逻辑

  • Step 2：将插入的节点着色为红色

        我们希望这次插入尽可能不破坏红黑树的性质，这样我们就可以不用进行额外的调整操作！所以，根据特性(5)，我们显然不能将节点涂成黑色，因为这样所有经过点S的路径的黑色节点都多了一个，就破坏了特性(5)，所以我们将S的颜色首先着色为红。

  • Step 3：进行适当得旋转以及颜色调整

    如果插入节点的父节点是红，那么违反了特性(4)，所以需要进行调整，共有三个case

    • case 1：F为红，U为红


      操作：将F以及U设置为黑，G设为红，并将G看成新插入的节点（即下一轮的S），递归操作。
      这里写图片描述


      原因：这个操作实际是想将红色往根处移动。将红色往上移了一层，并不会打破红黑树的特性，不断的把红色往上移动，当移动到根时，直接将根设置为黑色，就完全符合红黑树的性质了。

    • case 2：F为红，U为黑，并且，S为F的右儿子


      操作：将F左旋，并把F看成新加入的节点（即下一轮的S），继续后面的判断。
      这里写图片描述


      原因：这个操作是为了将这一case转换为case 3，

    • case 3：F为红，U为黑，并且，S为F的左儿子


      操作：先将F设为黑，G设为红，然后G右旋。这样操作后，就完全符合红黑树的性质了。
      这里写图片描述


      原因：G与F颜色互换，对左边路并没有影响，不过，对于右边路来说，由于G变为了红，其实少了一个黑，因此，将G右旋，使得黑色的F变为新的G，这样，就为右边路加回去了一个黑，而左边路只是损失了一个红，并不影响红黑树的平衡，这样操作后将会完全符合红黑树的性质，之所以说是完全符合，因为原来G的地方是个黑色节点，后来用了黑色的F去代替了G，对于G往上的层来说，并没有发生颜色变化，自然就是平衡的，所以，经过这一步的操作，红黑树恢复所有特性。

5. 核心操作之删除

说明：S的父亲节点为P，S的兄弟节点为B，B的左儿子为BL，B的右儿子为BR，且S为P的左儿子。（S为P的右儿子对称操作即可）

  • step 1：进行二叉查找树的删除操作

    二叉查找树的删除操作相对来说还是比较复杂，涉及到替代节点的选择等一些情况，如果不了解这一过程的可以自己去百度一下。我们假设想要删除的节点是X，找到的替代节点为Y（选择方式是X的右子树的最小点），那么我们可以将Y的值拷贝到X，然后将这个Y删除，将Y删除，也会需要有一个人顶替现在的Y的位置，我们设为S，接下来的讨论就会围绕着S展开。

  • step 2：红黑树性质判断

    由于我们将Y删除了，并且用S代替了Y的位置，如果Y原来是红色的，那么并不会破坏红黑树的颜色平衡，我们不需要额外的操作，删除成功！如果Y是黑色的，那么相当于经过Y的路径（现在是经过S）都会少了一个黑。那么我们怎么把这个黑弥补回来呢？那就是给S再加上一个黑，用来弥补删除Y而损失的那个黑。这时候，相当于S节点拥有了两个颜色，违反了特性(1)，所以，我们现在想办法把这个多出来的黑色删除掉！
    如果原来S是红色的，那么我们直接不要S的红色，将S设置为黑色即可，因为丢弃红色是不会打破红黑树的颜色平衡的，我们这一操作时安全的。可是，如果S原来就是黑色呢？那就要看S是不是根了，如果是根，将黑色丢弃了也没啥，相当于所有的路径都减少了一个黑，也是不影响平衡的，最糟糕的情况在于S原来时黑，且不是根，这时候，我们就要进行一些旋转以及颜色调整来恢复红黑树的特性了！

  • step 3旋转以及颜色调整

    共有四个case：

    • Case 1: S是“黑+黑”，且B为红。


      操作：将P设为红，B设为黑，然后将P左旋，这时S获得了新的B，用新的B进行后续的判断
      这里写图片描述


      原因：在这种情况下，我们可以得到P必定为黑，并且BL & BR 也都为黑。由于我们想要左旋，而又不能破坏红黑树的平衡，所以，将P设为红，B设为黑。左旋的目的是让S有新的B，从而转化为后面的case 2 or 3 or 4，进行下一步的操作。

    • Case 2：S是“黑+黑”，且B为黑，并且BL BR也都是黑。


      操作：将B设为红，并且让P为新的S，进行新一轮的递归。
      这里写图片描述


      原因：我们的目的就是想让多余的黑往上走，这时候，把这个多余的黑给到P，左边路的黑是不变的，而右边路多了一个，为了平衡，恰好BL BR都是黑，所以我们直接把B设为红就好啦，这样，黑就上浮到了P，将P看作新的起点，递归后面的操作就好啦~！

    • Case 3：S是“黑+黑”，且B为黑，并且BL为红，BR为黑。


      操作：将B设为红，BL设为黑，然后B右旋
      这里写图片描述


      原因：这个操作是为了转换到case 4。B和BL的颜色互换也是为了平衡。

    • S是“黑+黑”，且B为黑，并且BR为红，BL任意颜色。


      操作：将P的颜色给到B，将P设为黑，将BR设为黑，对P左旋，最后将S设置为root以结束循环。
      这里写图片描述
      （注：蓝色表示任意颜色）


      原因：这是最复杂的一种情况了。我们将P的颜色给到B，然后将P左旋，这时候，不管P初始是什么颜色，对于左边路来说，都多了一个黑色，为了保证颜色平衡，正好把S中多余的那个黑丢掉啦！但是左旋带来了一些后遗症，首先是BL变成了P的儿子，而这里我们不关心BL的颜色，所以，必须要把P设置为黑色，这样即使BL为红色也不会破坏红黑树，还有一点，不管P的初始颜色，左旋之后，右边路少了一个黑，为了补回来，我们让BR由红变黑就好啦！这就是完整的操作，精髓在于通过左旋P来消除多余的那个黑色，但由于左旋带来的后遗症需要相应的<改变颜色>措施来弥补。

6. 完整java实现

节点：

package RBTree;import java.util.Objects;public class RBTreeNode {private final boolean RED = false;private final boolean BLACK = true;private int key;private boolean color;private RBTreeNode left;private RBTreeNode right;private RBTreeNode parent;public RBTreeNode(int key) {this.key = key;this.color = RED;}public int getKey() {return key;}public void setKey(int key) {this.key = key;}public boolean getColor() {return color;}public void setColor(boolean color) {this.color = color;}public RBTreeNode getLeft() {return left;}public void setLeft(RBTreeNode left) {this.left = left;}public RBTreeNode getRight() {return right;}public void setRight(RBTreeNode right) {this.right = right;}public RBTreeNode getParent() {return parent;}public void setParent(RBTreeNode parent) {this.parent = parent;}@Overridepublic String toString() {return "RBTreeNode{" +",key=" + key +", color=" + color +'}';}
}

树：

package RBTree;public class RBTree {RBTreeNode root;private final boolean RED = false;private final boolean BLACK = true;public RBTreeNode query(int key) {RBTreeNode tmp = root;while (tmp != null) {if (tmp.getKey() == key)return tmp;else if (tmp.getKey() > key)tmp = tmp.getLeft();elsetmp = tmp.getRight();}return null;}public void insert(int key) {RBTreeNode node = new RBTreeNode(key);if (root == null) {root = node;node.setColor(BLACK);return;}RBTreeNode parent = root;RBTreeNode son = null;if (key <= parent.getKey()) {son = parent.getLeft();} else {son = parent.getRight();}//find the positionwhile (son != null) {parent = son;if (key <= parent.getKey()) {son = parent.getLeft();} else {son = parent.getRight();}}if (key <= parent.getKey()) {parent.setLeft(node);} else {parent.setRight(node);}node.setParent(parent);//fix upinsertFix(node);}private void insertFix(RBTreeNode node) {RBTreeNode father, grandFather;while ((father = node.getParent()) != null && father.getColor() == RED) {grandFather = father.getParent();if (grandFather.getLeft() == father) {  //F为G左儿子的情况，如之前的分析RBTreeNode uncle = grandFather.getRight();if (uncle != null && uncle.getColor() == RED) {setBlack(father);setBlack(uncle);setRed(grandFather);node = grandFather;continue;}if (node == father.getRight()) {leftRotate(father);RBTreeNode tmp = node;node = father;father = tmp;}setBlack(father);setRed(grandFather);rightRotate(grandFather);} else {                               //F为G的右儿子的情况，对称操作RBTreeNode uncle = grandFather.getLeft();if (uncle != null && uncle.getColor() == RED) {setBlack(father);setBlack(uncle);setRed(grandFather);node = grandFather;continue;}if (node == father.getLeft()) {rightRotate(father);RBTreeNode tmp = node;node = father;father = tmp;}setBlack(father);setRed(grandFather);leftRotate(grandFather);}}setBlack(root);}public void delete(int key) {delete(query(key));}private void delete(RBTreeNode node) {if (node == null)return;if (node.getLeft() != null && node.getRight() != null) {RBTreeNode replaceNode = node;RBTreeNode tmp = node.getRight();while (tmp != null) {replaceNode = tmp;tmp = tmp.getLeft();}int t = replaceNode.getKey();replaceNode.setKey(node.getKey());node.setKey(t);delete(replaceNode);return;}RBTreeNode replaceNode = null;if (node.getLeft() != null)replaceNode = node.getLeft();elsereplaceNode = node.getRight();RBTreeNode parent = node.getParent();if (parent == null) {root = replaceNode;if (replaceNode != null)replaceNode.setParent(null);} else {if (replaceNode != null)replaceNode.setParent(parent);if (parent.getLeft() == node)parent.setLeft(replaceNode);else {parent.setRight(replaceNode);}}if (node.getColor() == BLACK)removeFix(parent, replaceNode);}//多余的颜色在node里private void removeFix(RBTreeNode father, RBTreeNode node) {while ((node == null || node.getColor() == BLACK) && node != root) {if (father.getLeft() == node) {  //S为P的左儿子的情况，如之前的分析RBTreeNode brother = father.getRight();if (brother != null && brother.getColor() == RED) {setRed(father);setBlack(brother);leftRotate(father);brother = father.getRight();}if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) {setRed(brother);node = father;father = node.getParent();continue;}if (isRed(brother.getLeft())) {setBlack(brother.getLeft());setRed(brother);rightRotate(brother);brother = brother.getParent();}brother.setColor(father.getColor());setBlack(father);setBlack(brother.getRight());leftRotate(father);node = root;//跳出循环} else {                         //S为P的右儿子的情况，对称操作RBTreeNode brother = father.getLeft();if (brother != null && brother.getColor() == RED) {setRed(father);setBlack(brother);rightRotate(father);brother = father.getLeft();}if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) {setRed(brother);node = father;father = node.getParent();continue;}if (isRed(brother.getRight())) {setBlack(brother.getRight());setRed(brother);leftRotate(brother);brother = brother.getParent();}brother.setColor(father.getColor());setBlack(father);setBlack(brother.getLeft());rightRotate(father);node = root;//跳出循环}}if (node != null)node.setColor(BLACK);}private boolean isBlack(RBTreeNode node) {if (node == null)return true;return node.getColor() == BLACK;}private boolean isRed(RBTreeNode node) {if (node == null)return false;return node.getColor() == RED;}private void leftRotate(RBTreeNode node) {RBTreeNode right = node.getRight();RBTreeNode parent = node.getParent();if (parent == null) {root = right;right.setParent(null);} else {if (parent.getLeft() != null && parent.getLeft() == node) {parent.setLeft(right);} else {parent.setRight(right);}right.setParent(parent);}node.setParent(right);node.setRight(right.getLeft());if (right.getLeft() != null) {right.getLeft().setParent(node);}right.setLeft(node);}private void rightRotate(RBTreeNode node) {RBTreeNode left = node.getLeft();RBTreeNode parent = node.getParent();if (parent == null) {root = left;left.setParent(null);} else {if (parent.getLeft() != null && parent.getLeft() == node) {parent.setLeft(left);} else {parent.setRight(left);}left.setParent(parent);}node.setParent(left);node.setLeft(left.getRight());if (left.getRight() != null) {left.getRight().setParent(node);}left.setRight(node);}private void setBlack(RBTreeNode node) {if(node != null) {node.setColor(BLACK);}}private void setRed(RBTreeNode node) {if(node != null) {node.setColor(RED);}}public void inOrder() {inOrder(root);}private void inOrder(RBTreeNode node) {if (node == null)return;inOrder(node.getLeft());System.out.println(node);inOrder(node.getRight());}
}

7. 参考资料

    我从这里：https://www.cnblogs.com/skywang12345/p/3624343.html学到了很多的思想，不过，他的图有好些画错了。
    这里：http://www.cnblogs.com/geekma/archive/2012/06/27/2566226.html 有一个完整的红黑树操作过程的图示，可以当作很好的测试用例，看看自己的代码是否写对了。


http://chatgpt.dhexx.cn/article/oWnVxeYE.shtml

相关文章

Java 9 vs Java 8：引入模块化和JShell的全面升级

Java 9 vs Java 8：引入模块化和JShell的全面升级

Java 9 是 Java 语言的一个重大版本升级&#xff0c;带来了许多新的特性和改进。 在本篇博客中&#xff0c;我将为您介绍 Java 9 的一些重要特性。 &#x1f3c5; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01; 目录 一、模块化二、JShell三…
阅读更多...
HashMap 在 JDK 1.8 后新增的红黑树结构

HashMap 在 JDK 1.8 后新增的红黑树结构

读完本文你将了解到&#xff1a; 点击查看 Java 集合框架深入理解 系列 - - 乾杯传统 HashMap 的缺点HashMap 在 JDK 18 中新增的数据结构 红黑树HashMap 中关于红黑树的三个关键参数HashMap 在 JDK 18 中新增的操作桶的树形化 treeifyBinHashMap 在 JDK 18 中新增的操作 红黑树…
阅读更多...
epoll底层红黑树使用部分源码剖析：为什么使用红黑树以及如何使用红黑树

epoll底层红黑树使用部分源码剖析：为什么使用红黑树以及如何使用红黑树

我们知道epoll的底层使用了红黑树来管理文件描述符&#xff0c;为什么会选择红黑树这种结构呢&#xff1f; 以下是个人理解&#xff1a; epoll和poll的一个很大的区别在于&#xff0c;poll每次调用时都会存在一个将pollfd结构体数组中的每个结构体元素从用户态向内核态中的一…
阅读更多...
HashMap在jdk1.8为何引入了红黑树?

HashMap在jdk1.8为何引入了红黑树?

原创不易，麻烦点个关注，点个赞，谢谢各位。 二叉查找树 二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任…
阅读更多...
从电路的角度理解特征阻抗

从电路的角度理解特征阻抗

传输显得特征阻抗不是真实的电阻&#xff0c;微波技术课程会从波的角度描述特征阻抗&#xff0c;这次试图从电路的角度来理解 无损传输线是分布的L C 网络&#xff0c;假设是无限长传输线 从a,b两点看入的阻抗是相等的&#xff0c;所以可以简化成下图&#xff1a; 化简可得 这…
阅读更多...
同轴电缆阻抗总结（电阻、阻抗、特性阻抗）

同轴电缆阻抗总结（电阻、阻抗、特性阻抗）

文章目录 同轴电缆电阻、阻抗、特性阻抗电阻阻抗&#xff08;Impedance&#xff09;特性阻抗 总结 同轴电缆 同轴电缆是一种电线及信号传输线&#xff0c;一般是由四层物料造成&#xff1a;最内里是一条导电铜线&#xff0c;线的外面有一层塑胶&#xff08;作绝缘体、电介质之…
阅读更多...
传输线阻抗方程的推导

传输线阻抗方程的推导

在传输线理论中&#xff0c;当一段特征阻抗为 Z 0 Z_0 Z0​ 的传输线的终端连接了一个阻抗为 Z L Z_L ZL​ 的负载时&#xff0c;看向这段传输线的输入阻抗 Z i n Z_{in} Zin​ 将不再是 Z 0 Z_0 Z0​。 传输线阻抗方程 (Transmission Line Impedance Equation) 就是计算…
阅读更多...
PCB阻抗计算

PCB阻抗计算

阻抗匹配是指在能量传输时&#xff0c;要求负载阻抗要和传输线的特征阻抗相等&#xff0c;此时的传输不会产生反射&#xff0c;这表明所有能量都被负载吸收了。反之则在传输中有能量损失。在高速PCB设计中&#xff0c;阻抗的匹配与否关系到信号的质量优劣&#xff0c;下面简单介…
阅读更多...
特征阻抗和阻抗匹配_没有诸如对象关系阻抗不匹配之类的东西

特征阻抗和阻抗匹配_没有诸如对象关系阻抗不匹配之类的东西

特征阻抗和阻抗匹配 过去十年来&#xff0c;ORM的许多批评都错了这一点&#xff0c;因为它不准确。 到本文结尾&#xff0c;我们将得出以下结论&#xff1a; 关系&#xff08;数据&#xff09;模型和面向对象的模型之间没有显着差异 如何得出这个结论&#xff1f; 继续阅读&a…
阅读更多...
传输线特征阻抗计算

传输线特征阻抗计算

一直有很多人问我阻抗怎么计算的. 人家问多了,我想给大家整理个材料,于己于人都是个方便.如果大家还有什么问题或者文档有什么错误,欢迎讨论与指教! 在计算阻抗之前,我想很有必yi要理解这儿阻抗的意义 传输线阻抗的由来以及意义 传输线阻抗是从电报方程推导出来(具体可以查询微…
阅读更多...
PCB特征阻抗计算

PCB特征阻抗计算

见教程&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1V4UbEoKfMD1bilwu-Qwdyg 密码&#xff1a;ml6t
阅读更多...
射频特征阻抗

射频特征阻抗

Characteris Impendance(特性阻抗&#xff0c;也称为‘特征阻抗’)是我们经常看到并使用自己的术语之一&#xff0c;但非常模糊且难以解释。以下是来自几个不同来源的Characteris Impendance(特性阻抗)的一些定义。 &#xff08;如果您检查10个不同的来源&#xff0c;您会看到1…
阅读更多...
高速PCB的特征阻抗设计

高速PCB的特征阻抗设计

我们在高速PCB设计当中，经常对高速信号线做特征阻抗控制来优化信号质量。那特征阻抗是什么东西呢？ 1.传输线原理 介绍特征阻抗之前，我们复习下《信号完整性视频》介绍的传输线基本原理。如下图左边是低频电路采用集总参数的RLGC模型，右边高频电路采用分布参数的RLGC模型。…
阅读更多...
传输线的波阻抗与特征阻抗

传输线的波阻抗与特征阻抗

以上是时域方程&#xff0c;而我们的“波阻抗”是定义在频域下的&#xff08;正弦激励&#xff09;。 1&#xff09;“相电压/电流”的第一、二项分别代表了前向传输、反向传输分量&#xff1b; 2&#xff09;前向传输和反向传输分量两者无必然联系。 补充修改&#xff1a; 1&…
阅读更多...
PCB寄生参数和特征阻抗

PCB寄生参数和特征阻抗

1、微带线Microstrip 相同情况下&#xff0c;PCB板厚H越厚&#xff08;影响很大&#xff09;&#xff1a; 特征阻抗越大&#xff08;H↑ > ln()↑ > Z0↑&#xff09;传输延时几乎不变&#xff08;与H无关&#xff09;寄生电感越大&#xff08;H↑ > ln()↑ > L…
阅读更多...
传输线的特征阻抗

传输线的特征阻抗

要理解特征阻抗首先要建立一个模型。传输线零阶模型 在这个模型中&#xff0c;每一个步长是△X&#xff0c;单位长度的电容为CL&#xff0c;所以每个步长的电容 CCL*△X 然后我们根据电荷量 QU*CI*t &#xff0c;电流I Q / t C * U / t&#xff0c;其中t △X / v得到 电流 …
阅读更多...
阻抗，特征阻抗与等效阻抗

阻抗，特征阻抗与等效阻抗

目录 一、阻抗 二、 特征阻抗 三、等效阻抗 射频的黄金三角之一就是阻抗&#xff0c;我们在射频设计中&#xff0c;会经常与阻抗打交道&#xff0c;比如特征阻抗&#xff0c;负载阻抗&#xff0c;阻抗匹配等等。更多的时候&#xff0c;我们所设计的射频电路就是一个阻抗匹配…
阅读更多...
特性阻抗介绍

特性阻抗介绍

特性阻抗：又称“特征阻抗”，它不是直流电阻，属于长线传输中的概念。在高频范围内，信号传输过程中，信号沿到达的地方，信号线和参考平面（电源或地平面）间由于电场的建立，会产生一个瞬间电流，如果传输线是各向同性的，那么只要信号在传输，就始终存在一个电流I，而如果信…
阅读更多...
单播、广播和多播地址以及组播ip与组播mac间的换算

单播、广播和多播地址以及组播ip与组播mac间的换算

转自&#xff1a;https://www.cnblogs.com/songdada/articles/4039468.html 除地址类外&#xff0c;还可根据传输的消息特征将IP地址分为单播、广播或多播。主机使用IP地址进行一对一&#xff08;单播&#xff09;、一对多&#xff08;多播&#xff09;或一对所有&#xff08;…
阅读更多...
IP组播----组播基础 组播服务模型、组播地址

IP组播----组播基础 组播服务模型、组播地址

一、简介 IPv4传输方式有三种&#xff1a;单播、组播、广播 单播&#xff1a;信息源为每个需要信息的主机都发送一份独立的报文组播&#xff1a;信息源将保温发送到一个特定的组播IP地址&#xff0c;只有加入了这个组的主机才能接收广播&#xff1a;信息源将信息发送给网段中…
阅读更多...
推荐文章

Copyright @ 2022~2023