红黑树

article/2025/9/17 10:46:11

一.简介

红黑树作为一种二叉搜索树的一种实现，红黑树的左右子树高度差可能大于 1。所以红黑树不是严格意义上的平衡二叉树（AVL），但红黑树是黑色节点完美平衡， 其平均统计性能要强于 AVL 。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。
1.节点是红色或黑色。

2.根节点是黑色。

3.每个红色节点的两个子节点都是黑色。（红色节点的子节点必须是黑色节点）

4.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

故红黑树是黑色平衡的树，左子树与右子树高度差不会超过2倍。红节点的父节点、子节点只能是黑节点

如果插入节点是黑色则所在路径将多出一个黑色节点，故新插入节点是红色节点（插入/删除红色节点不会改变所在路径黑色节点数量），通过旋转和调整节点颜色保证树的平衡

二.实现

红黑树增加/删除节点时需要保证子树黑节点平衡，有如下情况:

1.插入节点为树的根节点时，把根节点颜色修改为黑色

2.插入节点父节点是黑色节点，由于插入节点是红色节点，不会影响该子树黑色节点数量，故不用任何处理

3.插入节点父节点为红色且父节点的兄弟节点也为红色，父节点、父节点的兄弟节点修改为黑色，父节点的父节点修改为红色，再以父节点的父节点为插入节点递归处理

4.父节点为红色且父节点的兄弟节点为null或为黑节点
由于父节点是红色节点，故父节点的父节点为黑色节点

1)LL型
插入数据父节点的兄弟节点只会为null，如果不为null则父节点的兄弟节点子树与父节点将不是平衡的。

修改父节点为黑色节点，祖父节点修改为红色节点
对祖父节点右旋转，让父节点为子树根节点，由于子树黑节点数量没有发生变化，故旋转后黑节点数量和旋转前一样

2)LR型
父节点左旋转将变为LL型，按LL型处理

3)RR型
修改父节点为黑色，祖父节点修改为红色，对祖父节点左旋转，让父节点为子树根节点，旋转后和旋转前黑色节点数量没有改变，故事黑色节点平衡

4)RL型
父节点右旋转变为RR型，按RR型处理

示例说明：

插入数据：4,3,6,5,7,8,9,10,11

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


package com.vincent;import java.util.*;public class Main {public static void main(String[] args) throws Exception {RBTree<Integer> tree = new RBTree<>();for(Integer data : Arrays.asList(4,3,6,5,7,8,9,10,11)){tree.add(data);System.out.println(tree.getRoot());}System.out.println();List<Integer> list = tree.infixList();System.out.println(list);tree.delete(list.get(0));list = tree.infixList();System.out.println(list);tree.delete(list.get(list.size()-1));list = tree.infixList();System.out.println(list);tree.delete(list.get(list.size()/2));list = tree.infixList();System.out.println(list);}
}//红黑树
class RBTree<T extends Comparable<T>>{private static final int RED = 0;private static final int BLACK = 1;static class Node<T extends Comparable<T>> {private T item;private int color = RED;private Node<T> left;private Node<T> right;private Node<T> parent;public Node(T item) {this.item = item;}public T getItem(){return item;}/*** 添加节点到当前节点树* @param node      添加的节点*/public void add(Node<T> node){if(node.item.compareTo(this.item) <= 0){if(this.left == null){this.left = node;node.parent = this;}else{this.left.add(node);}}else{if(this.right == null){this.right = node;node.parent = this;}else{this.right.add(node);}}}/*** 通过item查找所在树的结点* @param item* @return*/public Node<T> searchNode(T item){int cmp = item.compareTo(this.item);if(cmp == 0){return this;}Node<T> node = null;if(cmp < 0 && this.left != null && (node=this.left.searchNode(item)) != null){return node;}else if(cmp > 0 && this.right != null && (node=this.right.searchNode(item)) != null){return node;}return null;}/*** 删除节点,如果删除的节点为根节点将有NullPointerException*/public void del(){Node<T> parent = this.parent;if(this.left==null && this.right==null){//删除节点为叶子节点if(parent.left == this){parent.left = null;}else{parent.right = null;}}else if(this.left == null){//删除节点只有右子树if(parent.left == this){parent.left = this.right;}else{parent.right = this.right;}}else if(this.right == null){//删除节点只有左子树if(parent.left == this){parent.left = this.left;}else{parent.right = this.left;}}else{//删除节点有左右节点,从删除节点左子树中寻找最大值Node<T> maxNode = this.left;while(maxNode.right != null){maxNode = maxNode.right;}if(maxNode == this.left){//删除节点左子树的最大值就是删除节点的左节点this.item = maxNode.item;this.left = maxNode.left;}else{maxNode.parent.right = null;this.item = maxNode.item;}}}/*** 节点的中序遍历* @param dst   遍历节点的存放容器*/public void infixList(List<T> dst){if(this.left != null){this.left.infixList(dst);}dst.add(this.item);if(this.right != null){this.right.infixList(dst);}}/*** 该节点树的最大高度* @return*/public int height(){return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;}/*** 对当前节点左旋转操作* @return  返回左旋转操作后子树根节点(即当前节点的右节点)*/public Node<T> leftRotate(){if(this.right==null){return null;}Node<T> right = this.right;this.right = right.left;if(right.left != null) {right.left.parent = this;}right.left = this;right.parent = this.parent;if(this.parent != null) {if (this.parent.left == this) {this.parent.left = right;} else {this.parent.right = right;}}this.parent = right;return right;}/*** 对当前节点右旋转操作* @return  返回右旋转操作后子树根节点(即当前节点的左节点)*/public Node<T> rightRotate(){if(this.left==null){return null;}Node<T> left = this.left;this.left = left.right;if(left.right != null) {left.right.parent = this;}left.right = this;left.parent = this.parent;if(this.parent != null) {if (this.parent.left == this) {this.parent.left = left;} else {this.parent.right = left;}}this.parent = left;return left;}@Overridepublic String toString() {return "Node{" +"item=" + item +'}';}}private Node<T> root;Node<T> getRoot(){return root;}public void add(T item){Node<T> node = new Node<>(item);if(this.root == null){this.root = node;}else{Node<T> old = this.root.searchNode(item);if(old != null){old.item = item;}else{this.root.add(node);}}rebalance(node);}/*** 调整树的平衡性，会依次回溯到父节点* @param node      当前插入的节点*/private void rebalance(Node<T> node){Node<T> parent = node.parent;if(parent == null){//树的根节点node.color = BLACK;return;}else if(parent.color == RED) {//红节点一定有父节点Node<T> pparent = parent.parent;//父节点的兄弟节点Node<T> psibling = pparent.left == parent ? pparent.right : pparent.left;if (psibling != null && psibling.color == RED) {parent.color = psibling.color = BLACK;pparent.color = RED;rebalance(pparent);}else if (psibling == null || psibling.color == BLACK) {Node<T> subRoot = null;if (pparent.left == parent && parent.left == node) {//LL型parent.color = BLACK;pparent.color = RED;subRoot = pparent.rightRotate();} else if (pparent.left == parent && parent.right == node) {//LR型parent.leftRotate();node.color = BLACK;pparent.color = RED;subRoot = pparent.rightRotate();} else if (pparent.right == parent && parent.left == node) {//RL型parent.rightRotate();node.color = BLACK;pparent.color = RED;subRoot = pparent.leftRotate();} else {//RR型parent.color = BLACK;pparent.color = RED;subRoot = pparent.leftRotate();}//设置树的根节点if (subRoot.parent == null) {this.root = subRoot;}}}}public void delete(T item){Node<T> delNode = null;if(root.item.compareTo(item)==0){//删除根节点delNode = root;if(root.left==null && root.right==null){this.root = null;}else if(root.left==null){this.root = root.right;}else if(root.right==null){this.root = root.left;}else{//根节点有左右节点,扫描右子树最小节点Node<T> node = this.root.right;while(node.left!=null){node = node.left;}if(node == this.root.right){this.root.item = node.item;this.root.right = node.right;}else {node.parent.left = null;this.root.item = node.item;}}}else {Node<T> node = this.root.searchNode(item);delNode = node;if (node != null) {node.del();}}if(delNode != null){this.rebalance(delNode);}}public List<T> infixList(){List<T> rst = new ArrayList<>();this.root.infixList(rst);return rst;}public int height(){return this.root.height();}}

三.总结

红黑树的平衡处理相对AVL较为宽松，数据插入/删除时效率相对较高


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

相关文章

B树最大高度推导

B树最大高度推导

文章目录 B树最大高度推导推导B树的最小高度推导最大高度 B树&#xff1a;MySQL数据库索引是如何实现的&#xff1f;1. 遇到问题2. 尝试用学过的数据结构解决这个问题3. 改造二叉查找树4. 索引的弊端 B树最大高度推导 【声明几个重要概念】 B树的关键字就是要查找的东西 B树…
阅读更多...
红黑树详解

红黑树详解

1&#xff0c;红黑树特点 每一个结点都有颜色&#xff0c;要么红色&#xff0c;要么黑色。根结点必须是黑色的。红色结点的子结点必须是黑色的。任何一个结点&#xff0c;到它所有叶子结点&#xff0c;经过相同个数的黑色结点。&#xff08;红黑树的平衡含义&#xff0c;左右高…
阅读更多...
MYSQL的B+Tree索引树高度如何计算

MYSQL的B+Tree索引树高度如何计算

我们使用MySQL数据库的时候&#xff0c;绝大部分的情况下在使用InnoDB存储引擎&#xff0c;偶尔会使用MyISAM存储引擎&#xff0c;至于其他存储引擎&#xff0c;我相信大家都很少接触到&#xff0c;甚至可能都没有听说过。所以本文只讲解InnoDB和MyISAM两个存储引擎的索引&…
阅读更多...
红黑树高度上限的证明（通俗易懂）

红黑树高度上限的证明（通俗易懂）

先把结论放上&#xff0c;设红黑树的高度为h&#xff0c;总结点数为n&#xff0c;那么h与n的关系就是 下面开始证明过程 首先&#xff0c;从任意节点出发&#xff0c;到其子树的叶子节点的路径中黑色节点的数量称为该节点的黑高&#xff0c;即 bh 我们设根节点为T,那么根节点…
阅读更多...
数据结构与算法（一）： 树的高度和深度的区别

数据结构与算法（一）： 树的高度和深度的区别

1.高度 对于高度的理解&#xff0c;我们不管他数据结构什么什么知识&#xff0c;就拿楼房来说&#xff0c;假如一个人提问&#xff1a;楼房的高度有好高&#xff1f;我们会下意识的从底层开始往上数&#xff0c;假如楼有6层&#xff0c;则我们会说&#xff0c;这个楼有6层楼那…
阅读更多...
经典PID算法

经典PID算法

首先感谢黄工&#xff0c;公众号strongerHuang&#xff0c;以下为三篇文章整合而成。 文章链接&#xff1a; https://mp.weixin.qq.com/s/6Ew431m4nXhScpNVp8mGxQ https://mp.weixin.qq.com/s/JYWnu67HEx2uMrntcUhggQ https://mp.weixin.qq.com/s/IrTehHvTofXWP_BapoN1NQ 在工…
阅读更多...
PID控制原理

PID控制原理

PID控制原理 在模拟控制系统中，控制器最常用的控制规律是PID控制。 PID控制器是一种线性控制器，它根据给定值与实际输出值构成控制偏差。 PID控制规律为 数学表达形式为： 进行拉普拉斯变换，写出传递函数的形式： kp为比例系数，T1为积分时间常数，Td为微分时间常数。…
阅读更多...
SMART PLC PID算法基本解析（附公式）

SMART PLC PID算法基本解析（附公式）

在稳态运行中，控制器调节输出值，使偏差 (e) 为零。偏差是设定值（目标值）与过程变量（实际值、反馈值）之差。输出 = 比例项 + 积分项 + 微分项 离散化的PID公式基本框架几乎一样，不同的厂家描述符号，变量名称定义可能不太一样， 从公式中可以看出，积分项是从第一次采样到…
阅读更多...
PID算法-理论分析

PID算法-理论分析

连续PID算法 典型PID算法框图 r(t)&#xff1a;设定状态量y(t)&#xff1a;实际状态量e(t)&#xff1a;当前误差u(t)&#xff1a;控制 器输出 P-比例环节 u p ( t ) K p ∗ e ( t ) K p [ r ( t ) − y ( t ) ] u_{p}(t)Kp*e(t)Kp[r(t)-y(t)] up​(t)Kp∗e(t)Kp[r(t)−y(t)…
阅读更多...
PID详解

PID详解

PID在控制领域应该是应用最为广泛的算法了&#xff0c;在工业控制&#xff0c;汽车电子等诸多领域中运用 下面我用一个例子和算法过程来讲解PID的概念 PID&#xff1a; P比例控制&#xff1a;基本作用就是控制对象以线性的方式增加&#xff0c;在一个常量比例下&#xff0c;动态…
阅读更多...
模糊PID算法

模糊PID算法

在讲解模糊PID前&#xff0c;我们先要了解PID控制器的原理&#xff08;本文主要介绍模糊PID的运用,对PID控制器的原理不做详细介绍&#xff09;。PID控制器&#xff08;比例-积分-微分控制器&#xff09;是一个在工业控制应用中常见的反馈回路部件&#xff0c;由比例单元P、积分…
阅读更多...
PID控制器整理分享

PID控制器整理分享

概述 日常开发中&#xff0c;常常需要对速度、温度等物理量进行稳态控制&#xff0c;而在目前的自动化控制原理中&#xff0c;使用最为广泛的方法就是PID控制算法。本文简要整理分享PID控制器的使用。 正文 PID控制器&#xff0c;即比例-积分-微分控制器。它是一个不依赖系统…
阅读更多...
PID算法详解

PID算法详解

文章目录 什么是pid比例&#xff08;p&#xff09;控制积分&#xff08;I&#xff09;控制微分&#xff08;D&#xff09;控制PID使用增量式PIDC语言实现pid算法 什么是pid PID算法是一种具有预见性的控制算法&#xff0c;其核心思想是&#xff1a; 1>. PID算法不但考虑控制…
阅读更多...
《PID》一篇文章带你搞懂使用PID

《PID》一篇文章带你搞懂使用PID

节选自本人博客&#xff1a;https://www.blog.zeeland.cn/archives/pid-learning 本文为笔者参考了网上众多大神的解析之后加上自己的理解整合起来的&#xff0c;因此在内容上部分参考了其他作者&#xff0c;目的仅用作参考以便更好地学习&#xff0c;如有侵犯&#xff0c;可联…
阅读更多...
PID几种公式总结

PID几种公式总结

模拟式PID 其中&#xff0c;t为采样时间 位置式PID 其中&#xff0c;为采样间隔 增量式PID 增量式PID和位置式PID都是数字式PID&#xff08;模拟式PID的离散化&#xff09;的不同表达形式&#xff0c;因为计算机只能处理离散数据&#xff0c;将连续信号变为离散信号&#xff…
阅读更多...
PID控制及公式讲解

PID控制及公式讲解

1、PID引入 2、PID代码 /*******************************************************************位置式pid********************************************************************/ double PID(double Actual,double SET){ static double E_sum,Error_last; //上一…
阅读更多...
增量式PID计算公式完整详细推导过程

增量式PID计算公式完整详细推导过程

相关文章&#xff1a;添加链接描述
阅读更多...
一文读懂PID控制算法（抛弃公式，从原理上真正理解PID控制）

一文读懂PID控制算法（抛弃公式，从原理上真正理解PID控制）

一文读懂PID控制算法&#xff08;抛弃公式&#xff0c;从原理上真正理解PID控制&#xff09; PID控制应该算是应用非常广泛的控制算法了。小到控制一个元件的温度&#xff0c;大到控制无人机的飞行姿态和飞行速度等等&#xff0c;都可以使用PID控制。这里我们从原理上来理解PI…
阅读更多...
PID公式的推导过程及实现代码

PID公式的推导过程及实现代码

一、PID框图&#xff1a; n0(t)是要稳定的值 n(t)是当前输出值 e(t) n0(t) - n(t) 一、模拟PID控制原理 这个公式网络上很好找&#xff1a; 二、数字PID控制 由于模拟的微积分运算对应计算机来说是不太好写代码的&#xff0c;所以要利用采样将数据离散化 于是公式就可以转换…
阅读更多...
经典的pid公式，好脑子不如烂笔头。

经典的pid公式，好脑子不如烂笔头。

这个算法涉及昨天&#xff0c;今天&#xff0c;明天。 思路就是以史为鉴&#xff0c;预测明天&#xff0c;改革当前。
阅读更多...
推荐文章

Copyright @ 2022~2023