二叉排序树 -- AVL树 红黑树

手撕 – AVL树、红黑树

在这里插入图片描述

个人主页：顾漂亮

文章专栏：Java数据结构

文章目录

  • 手撕 -- AVL树、红黑树
    • 1.AVL树
      • 1.1AVL树的概念
      • 1.2AVL树的性质
      • 1.3AVL树的实现 -- Java代码
      • 1.4AVL树的性能分析
    • 2.红黑树
      • 2.1概念
      • 2.2红黑树的性质
      • 2.3红黑树的实现
      • 2.4AVL树和红黑树的比较
      • 2.5红黑树的应用
      • 2.5红黑树的应用

1.AVL树

1.1AVL树的概念

二叉搜索树虽然可以缩短查找的效率，但是如果**数据有序或者接近有序将退化为单支树，查找元素相当于在顺序表中搜索元素，**效率低下。因此：当向二叉搜索树中插入新节点后，如果能保证每一个节点的左右子树高度只差的绝对值不超过1，即通过旋转降低树的高度，从而减少平均搜索长度

1.2AVL树的性质

  • 左右子树都是AVL树
  • 左右子树高度差（简称平衡因子）的绝对值不超过1
  • AVL是一颗高度平衡的二叉平衡树，如果其有n个节点，其高度可以保持在logn，搜索时间复杂度为O(logn)

1.3AVL树的实现 – Java代码

public class AVLTree {//定义节点static class TreeNode{public int val;public TreeNode left;public TreeNode right;public int bf;//平衡因子public TreeNode parent;//父节点public TreeNode(int val) {this.val = val;}}public TreeNode root;public boolean insert(int val){//先按照二叉搜索树的方式插入新节点TreeNode node = new TreeNode(val);if(root == null){root = node;return true;}TreeNode cur = root;TreeNode parent = null;while(cur != null){if(cur.val > val){parent = cur;cur = cur.left;} else if (cur.val == val) {return false;//AVL树中不存在数值相同的节点，如果找到相等节点直接返回false}else{//cur.val < valparent = cur;cur = cur.right;}}if(parent.val > val){parent.left = node;cur = parent.left;}else{parent.right = node;cur = parent.right;}//不要忘了更新新节点的父亲节点node.parent = parent;//调整节点的平衡因子while(parent != null){//更新双亲节点的平衡因子if(cur == parent.right){parent.bf++;} else if (cur == parent.left) {parent.bf--;}//满足AVL树的性质，插入成功if(parent.bf == 0){break;} else if (parent.bf == -1 || parent.bf == 1) {//继续向上查找cur = parent;parent = parent.parent;} else  {//平衡因子为2if(parent.bf == 2){if(cur.bf == -1){rotateRL(parent);}else{//左旋rotateL(parent);}}else if (parent.bf == -2){//平衡因子为-2if(cur.bf == -1){//右旋rotateR(parent);}else{rotateLR(parent);}}break;}}return true;}private void rotateRL(TreeNode parent) {//记录TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;rotateR(parent.right);rotateL(parent);if(bf == -1){subRL.bf = 0;subR.bf = 1;parent.bf = 0;}else if(bf == 1){subR.bf = 0;parent.bf = -1;subRL.bf = 0;} else if (bf == 0) {subR.bf = 0;parent.bf = 0;subRL.bf = 0;}}private void rotateLR(TreeNode parent) {//记录TreeNode subL = parent.left;TreeNode subLR = subL.right;int bf = subLR.bf;rotateL(parent.left);rotateR(parent);if(bf == -1){subLR.bf = 0;subL.bf = 0;parent.bf = 1;}else if(bf == 1){subL.bf = -1;parent.bf = 0;subLR.bf = 0;} else if (bf == 0) {subLR.bf = 0;subL.bf = 0;parent.bf = 0;}}private void rotateR(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;parent.left = subLR;if(subLR != null){subLR.parent = parent;}subL.right = parent;TreeNode pParent = parent.parent;parent.parent = subL;if(root == parent){root = subL;root.parent = null;}else{if(parent == pParent.right){pParent.right = subL;}else{pParent.left = subL;}subL.parent = pParent;}parent.bf = subL.bf = 0;}private void rotateL(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;parent.right = subRL;if(subRL != null){subRL.parent = parent;}subR.left = parent;TreeNode pParent = parent.parent;parent.parent = subR;if(parent == root){root = subR;root.parent = null;}else{if(parent == pParent.right){pParent.right = subR;}else{pParent.left = subR;}subR.parent = pParent;}parent.bf = subR.bf = 0;}//AVL树的验证public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}//求树的高度public int height(TreeNode root){if(root == null){return 0;}int left = height(root.left);int right = height(root.right);return left > right ? left + 1 : right +1;}//判断树的高度差public boolean isBalance(TreeNode root){if(root == null){return true;}int leftH = height(root.left);int rightH = height(root.right);//检查平衡因子是否有问题if(rightH - leftH != root.bf){System.out.println(root.val + "平衡因子异常");return false;}return Math.abs(leftH-rightH)<=1 && isBalance(root.left) && isBalance(root.right);}
}

注解：

当前节点的平衡因子：当前节点右子树高度 - 左子树高度

1.4AVL树的性能分析

  1. AVL可以保证高效的查找时间复杂度，为O(logN)
  2. 如果需要对于AVL树的结构做一些修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
  3. 适用场景：适用于需要一种查询高效且有序的数据结构，而且数据的个数是静态的，可以考虑AVL树，但是一个结构需要经常修改，就不太合适

2.红黑树

2.1概念

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

2.2红黑树的性质

  1. 最长路径最多是最短路径的二倍
  2. 每一个节点不是红色就是黑色
  3. 根节点是黑色的
  4. 如果一个节点是红色的，则它的两个孩子节点是黑色的 没有两个连续的红色节点
  5. 对于每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
  6. 每一个叶子节点都是黑色的（此处叶子节点指的是空节点）

在这里插入图片描述

注意：一般情况下，一个正常的红黑树不会出现上述情况，可以用来验证性质1

2.3红黑树的实现

//定义一个枚举
public enum Color {RED,BLACK
}

public class RBTree {//红黑树节点static class RBTreeNode{public int val;public RBTreeNode left;public RBTreeNode right;public RBTreeNode parent;Color color;//节点默认为红色，若为黑色，容易产生不平衡因素--需要新增节点public RBTreeNode(int val) {this.val = val;this.color = Color.RED;}}public RBTreeNode root;public boolean insert(int val){RBTreeNode node = new RBTreeNode(val);if(root == null){root = node;root.color = Color.BLACK;//注意将节点置为黑色，根节点return true;}RBTreeNode cur = root;RBTreeNode parent = null;while(cur != null){if(cur.val > val){parent = cur;cur = cur.left;}else if(cur.val < val){parent = cur;cur = cur.right;}else{return false;//红黑树中不存在相同节点}}if(parent.val > val){parent.left = node;node.parent = parent;//不要忘记确定parent的指向} else if (parent.val < val) {parent.right = node;node.parent = parent;}cur = node;//cur指向新插入的节点//插入节点默认为红色，主要是看插入节点的父节点是否为红色while(parent != null && parent.color == Color.RED){RBTreeNode grandFather = parent.parent;//若满足parent为红色，则节点一定存在if(parent == grandFather.left){RBTreeNode uncle = grandFather.right;//情况1if(uncle!= null && uncle.color == Color.RED){parent.color = Color.BLACK;uncle.color = Color.BLACK;grandFather.color = Color.RED;//判断parent是否为空，即grandparent是否就等于rootif(grandFather == root){grandFather.color = Color.BLACK;//将根节点置为空break;}//继续向上修改cur = grandFather;parent = cur.parent;}else{//情况3if(parent.right == cur){rotateL(parent);//交换RBTreeNode tmp = cur;cur = parent;parent = tmp;}//情况2rotateR(grandFather);parent.color = Color.BLACK;grandFather.color = Color.RED;}}else{//parent == grandFather.rightRBTreeNode uncle = grandFather.left;if(uncle != null && uncle.color == Color.RED){uncle.color = parent.color = Color.BLACK;grandFather.color = Color.RED;if(grandFather == root){grandFather.color = Color.BLACK;}cur = grandFather;parent = cur.parent;}else{//情况3if (cur == parent.right){rotateR(parent);//交换RBTreeNode tmp = cur;cur = parent;parent = tmp;}//情况2rotateL(grandFather);grandFather.color = Color.RED;parent.color = Color.BLACK;}}}return true;}private void rotateR(RBTreeNode parent) {RBTreeNode subL = parent.left;RBTreeNode subLR = subL.right;parent.left = subLR;if(subLR != null){subLR.parent = parent;}subL.right = parent;RBTreeNode pParent = parent.parent;parent.parent = subL;if(root == parent){root = subL;root.parent = null;}else{if(parent == pParent.right){pParent.right = subL;}else{pParent.left = subL;}subL.parent = pParent;}}private void rotateL(RBTreeNode parent) {RBTreeNode subR = parent.right;RBTreeNode subRL = subR.left;parent.right = subRL;if(subRL != null){subRL.parent = parent;}subR.left = parent;RBTreeNode pParent = parent.parent;parent.parent = subR;if(parent == root){root = subR;root.parent = null;}else{if(parent == pParent.right){pParent.right = subR;}else{pParent.left = subR;}subR.parent = pParent;}}//中序遍历public void inOrder(RBTreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}//检测其是否满足红黑树的性质public boolean isValidRBTree(RBTreeNode root) {//如果是空树，满足if (root == null) {return true;}//根节点不是黑色的，不是红黑树if (root.color != Color.BLACK) {System.out.println("违反了红黑树的性质：根节点不是黑色");return false;}//获取单条路径中黑色节点的个数RBTreeNode cur = root;int blackCount = 0;while (cur != null) {if (cur.color == Color.BLACK) {blackCount++;}cur = cur.left;}return _isValidRBtree(root, 0, blackCount);}public boolean _isValidRBtree(RBTreeNode root, int pathCount, int blackCount){if(root == null){return true;}//遇到黑色的，pathCount++if(root.color == Color.BLACK){pathCount++;}RBTreeNode parent = root.parent;if(parent != null && parent.color == Color.RED && root.color == Color.RED){System.out.println("有连在一起的红色节点");return false;}if(root.left == null && root.right == null){if(pathCount != blackCount){System.out.println("路径中黑色节点数量不一致");return false;}}return _isValidRBtree(root.left, pathCount, blackCount) && _isValidRBtree(root.right, pathCount, blackCount);}
}

2.4AVL树和红黑树的比较

树类型AVL树红黑树
查找效率O(logN)O(logN)
特点追求绝对平衡，插入、删除需要进行大量旋转不追求绝对平衡，相对而言降低了插入和旋转的次数
在增删结构中性能比较相对较低更高的效率

2.5红黑树的应用

树类型AVL树红黑树
查找效率O(logN)O(logN)
特点追求绝对平衡，插入、删除需要进行大量旋转不追求绝对平衡，相对而言降低了插入和旋转的次数
在增删结构中性能比较相对较低更高的效率

2.5红黑树的应用

Java集合框架中：TreeMap、TreeMap底层使用的就是红黑树

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/22694.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

在 .NET 8/9 中使用 AppUser 进行 JWT 令牌身份验证

在 .NET 8/9 中使用 AppUser 进行 JWT 令牌身份验证

文章目录 一、引言二、什么是 JSON Web 令牌&#xff1f;三、什么是 JSON Web 令牌结构&#xff1f;四、设置 JWT 令牌身份验证4.1 创建新的 .NET 8 Web API 项目4.2 安装所需的 NuGet 软件包4.3 创建 JWT 配置模型4.4 将 JWT 配置添加到您的 appsettings.json 中4.5 为 Config…
阅读更多...
问卷数据分析|SPSS实操之相关分析

问卷数据分析|SPSS实操之相关分析

皮尔逊还是斯皮尔曼的选取主要看数据的分布 当数据满足正态分布且具有线性关系时&#xff0c;用皮尔逊相关系数 当有一个不满住时&#xff0c;用斯皮尔曼相关系数 1. 选择分析--相关--双变量 2. 将Z1-Y2加入到变量中&#xff0c;选择皮尔逊 3. 此处为结果&#xff0c;可看我案…
阅读更多...
自动化办公|xlwings生成图表

自动化办公|xlwings生成图表

在日常的数据分析和报告生成中&#xff0c;Excel图表是一个非常重要的工具。它能够帮助我们直观地展示数据&#xff0c;发现数据中的规律和趋势。然而&#xff0c;手动创建和调整图表往往耗时且容易出错。幸运的是&#xff0c;借助Python的xlwings库&#xff0c;我们可以自动化…
阅读更多...
Javascript使用Sodium库实现 aead_xchacha20poly1305_ietf加密解密，以及与后端的密文交互

Javascript使用Sodium库实现 aead_xchacha20poly1305_ietf加密解密，以及与后端的密文交互

Node.js环境安装 sodium-native (其他库可能会出现加密解密失败&#xff0c;如果要使用不一样的库&#xff0c;请自行验证) npm install sodium-native 示例代码&#xff0c;使用的是 sodium-native v4.3.2 (其他版本可能会有变化&#xff0c;如果要使用&#xff0c;请自行验…
阅读更多...
【Linux】匿名管道的应用场景-----管道进程池

【Linux】匿名管道的应用场景-----管道进程池

目录 一、池化技术 二、简易进程池的实现&#xff1a; Makefile task.h task.cpp Initchannel函数&#xff1a; 创建任务&#xff1a; 控制子进程&#xff1a; 子进程执行任务&#xff1a; 清理收尾&#xff1a; 三、全部代码&#xff1a; 前言&#xff1a; 对于管…
阅读更多...
使用LangChain构建第一个ReAct Agent

使用LangChain构建第一个ReAct Agent

使用LangChain构建第一个ReAct Agent 准备环境 使用Anaconda 安装python 3.10 安装langchain、langchain_openai、langchain_community &#xff08;安装命令 pip install XXX&#xff09; 申请DeepSeek API&#xff1a;https://platform.deepseek.com/api_keys&#xff08;也…
阅读更多...
多人协同创作gitea

多人协同创作gitea

多人协同创作gitea 在多台设备上协同使用Gitea&#xff0c;主要是通过网络访问Gitea服务器上的仓库来进行代码管理和协作。以下是一些关键步骤和建议&#xff0c;帮助你在多台设备上高效地使用Gitea进行协作&#xff1a; 1. 确保Gitea服务可访问 首先&#xff0c;你需要确保…
阅读更多...
【个人开源】——从零开始在高通手机上部署sd（二）

【个人开源】——从零开始在高通手机上部署sd（二）

代码&#xff1a;https://github.com/chenjun2hao/qualcomm.ai 推理耗时统计 单位/ms 硬件qnncpu_clipqnncpu_unetqnncpu_vaehtp_cliphtp_unethtp_vae骁龙8 gen124716.994133440.39723.215411.097696.327 1. 下载依赖 下载opencv_x64.tar,提取码: rrbp下载opencv_aarch64.t…
阅读更多...
SpringCloud系列教程：微服务的未来（二十五）-基于注解的声明队列交换机、消息转换器、业务改造

SpringCloud系列教程：微服务的未来（二十五）-基于注解的声明队列交换机、消息转换器、业务改造

前言 在现代分布式系统中&#xff0c;消息队列是实现服务解耦和异步处理的关键组件。Spring框架提供了强大的支持&#xff0c;使得与消息队列&#xff08;如RabbitMQ、Kafka等&#xff09;的集成变得更加便捷和灵活。本文将深入探讨如何利用Spring的注解驱动方式来配置和管理队…
阅读更多...
学习经验分享【39】YOLOv12——2025 年 2 月 19 日发布的以注意力为核心的实时目标检测器

学习经验分享【39】YOLOv12——2025 年 2 月 19 日发布的以注意力为核心的实时目标检测器

YOLO算法更新速度很快&#xff0c;已经出到V12版本&#xff0c;后续大家有想发论文或者搞项目可更新自己的baseline了。 代码&#xff1a;GitHub - sunsmarterjie/yolov12: YOLOv12: Attention-Centric Real-Time Object Detectors 摘要&#xff1a;长期以来&#xff0c;增强 …
阅读更多...
Pytorch实现之特征损失与残差结构稳定GAN训练，并训练自己的数据集

Pytorch实现之特征损失与残差结构稳定GAN训练，并训练自己的数据集

简介 简介：生成器和鉴别器分别采用了4个新颖设计的残差结构实现，同时在损失中结合了鉴别器层的特征损失来提高模型性能。 论文题目：Image Generation by Residual Block Based Generative Adversarial Networks（基于残留块的生成对抗网络产生图像） 会议：2022 IEEE Int…
阅读更多...
后“智驾平权”时代，谁为安全冗余和体验升级“买单”

后“智驾平权”时代，谁为安全冗余和体验升级“买单”

线控底盘&#xff0c;正在成为新势力争夺下一个技术普及红利的新赛点。 尤其是进入2025年&#xff0c;比亚迪、长安等一线传统自主品牌率先开启高阶智驾的普及战&#xff0c;加上此前已经普及的智能座舱&#xff0c;舱驾智能的「科技平权」进一步加速行业启动「线控底盘」上车窗…
阅读更多...
【Node.js】express框架

【Node.js】express框架

目录 1初识express框架 2 初步使用 2.1 安装 2.2 创建基本的Web服务器 2.3 监听方法 2.3.1 监听get请求 2.3.2 监听post请求 2.4 响应客户端 2.5 获取url中的参数(get) 2.5.1 获取查询参数 2.5.2 获取动态参数 2.6 托管静态资源 2.6.1 挂载路径前缀 2.6.2 托管多…
阅读更多...
树形DP（树形背包+换根DP）

树形DP（树形背包+换根DP）

树形DP 没有上司的舞会 家常便饭了&#xff0c;写了好几遍&#xff0c;没啥好说的&#xff0c;正常独立集问题。 int head[B]; int cnt; struct node {int v,nxt; }e[B<<1]; void modify(int u,int v) {e[cnt].nxthead[u];e[cnt].vv;head[u]cnt; } int a[B]; int f[B]…
阅读更多...
REACT--组件通信

REACT--组件通信

组件之间如何进行通信&#xff1f; 组件通信 组件的通信主要借助props传递值 分为整体接收、解构接收 整体接收 import PropTypes from prop-types;//子组件 function Welcome(props){return (<div>hello Welcome,{props.count},{props.msg}</div>) }// 对 We…
阅读更多...
【排序算法】六大比较类排序算法——插入排序、选择排序、冒泡排序、希尔排序、快速排序、归并排序【详解】

【排序算法】六大比较类排序算法——插入排序、选择排序、冒泡排序、希尔排序、快速排序、归并排序【详解】

文章目录 六大比较类排序算法&#xff08;插入排序、选择排序、冒泡排序、希尔排序、快速排序、归并排序&#xff09;前言1. 插入排序算法描述代码示例算法分析 2. 选择排序算法描述优化代码示例算法分析 3. 冒泡排序算法描述代码示例算法分析与插入排序对比 4. 希尔排序算法描…
阅读更多...
纠错检索增广生成论文

纠错检索增广生成论文

一、摘要 动机&#xff1a;RAG严重依赖于检索文档的相关性&#xff0c;如果检索出错&#xff0c;那么LLM的输出结果也会出现问题 解决方案&#xff1a;提出纠正性检索增强生成&#xff08;CRAG&#xff09;即设计一个轻量级的检索评估器&#xff0c;用来评估针对某个查询检索…
阅读更多...
Java NIO与传统IO性能对比分析

Java NIO与传统IO性能对比分析

Java NIO与传统IO性能对比分析 在Java中&#xff0c;I/O&#xff08;输入输出&#xff09;操作是开发中最常见的任务之一。传统的I/O方式基于阻塞模型&#xff0c;而Java NIO&#xff08;New I/O&#xff09;引入了非阻塞和基于通道&#xff08;Channel&#xff09;和缓冲区&a…
阅读更多...
easelog(1)基础C++日志功能实现

easelog(1)基础C++日志功能实现

EaseLog(1)基础C日志功能实现 Author: Once Day Date: 2025年2月22日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 注&#xff1a;本简易日志组件代码实现参考了Google …
阅读更多...
Vue面试2

Vue面试2

1.跨域问题以及如何解决跨域 跨域问题&#xff08;Cross-Origin Resource Sharing, CORS&#xff09;是指在浏览器中&#xff0c;当一个资源试图从一个不同的源请求另一个资源时所遇到的限制。这种限制是浏览器为了保护用户安全而实施的一种同源策略&#xff08;Same-origin p…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023