为什么红黑树比AVL树效率高?

文章目录

  • 前言
  • 红黑树的提出
  • 都知道的几个定义
  • 理解红黑树的高效
  • 总结

前言

红黑树为什么这么火呢?大家应该都很清楚,面试的时候不管三七二十一,就问你:什么是红黑树,为什么要用红黑树?就好像他很懂,就好像知道红黑树就很牛逼一样。

在这里插入图片描述

whatever,如果还不懂红黑树,不管有没有基础的,希望通过本次的介绍,可以帮助你更容易的理解红黑树。

红黑树的提出

首先,什么是红黑树?红黑树也是一个自平衡的二叉查找树,如果没有基础的,可以先去前面的文章了解一下数据结构以及AVL树。

为什么要用红黑树?相比AVL树红黑树的效率更高。为什么?

我们知道AVL树是在插入或删除节点时通过旋转操作使节点的左右子树高度差不大于1,从而保证了树的平衡。但是AVL树平衡比较严格,基本上每添加或删除一个节点都会旋转一次,频繁的旋转会导致效率低下,为此红黑树就被提出了。

都知道的几个定义

相信大家在学习红黑树的时候都看过以下几个定义:

  • 每个节点必须是红色或黑色。
  • 根节点必须是黑色。
  • 所有叶子结点都是黑色。
  • 两个红节点不能相邻,如果当前节点是红色,子节点必须是黑色。
  • 从任意节点到每个叶子节点的路径中,黑色节点数量是相同的。

还有等等。

这个定义看完之后你能理解为什么红黑树的效率会比AVL树高吗?反正我是理解不了,所以不要被这些定义影响,更不用死记硬背这些东西。

还有红黑树本质是2-3-4树、红黑树利用了缓存这些说法,我个人是没理解。

理解红黑树的高效

说实话,我在刚接触到红黑树的时候,首先是被开篇的定义所影响,其次发现也是通过左旋右旋保持平衡,感觉与AVL树没什么区别,反而比AVL树更加复杂,更加难以理解,所谓的“红黑树比AVL树的效率高”就更不用说了。

如何理解红黑树比AVL树的效率高呢?

红黑树相对AVL树平衡性比较宽松,没有那么严格,也就是红黑树的旋转次数不会那么频繁,这也是红黑树为什么比AVL树效率高的原因。

那么红黑树的平衡性宽松怎么体现?为什么旋转次数相对较少呢?以上的两个定义重点关注一下:

  1. 两个红节点不能相邻,如果当前节点是红色,子节点必须是黑色。
  2. 从任意节点到每个叶子节点的路径中,黑色节点数量是相同的。

这两个定义意味着树上的最长链上的节点是红黑相间,因为上述1。最短链全是黑节点,因为上述2。

在这里插入图片描述

如上图可以看到,最长链(右)和最短链(左)之间的长度差是2:4,如果此时在右树插入一个节点就会进行旋转保持平衡,如下图

在这里插入图片描述

因此可以知道:红黑树的最长链和最短链之间的长度差不会超过两倍,也正因如此,其旋转次数在比AVL树少的情况下也保持了相对宽松的平衡,效率也就较AVL树高一些。但是,红黑树和AVL树两者整体的复杂度都为O(log n)。

总结

  1. 红黑树是为了解决AVL树频繁旋转导致效率低下被提出。
  2. AVL树平衡性取决于左右子树高度差(不能大于1,比较严格),红黑树平衡性取决于红黑节点的分布(模糊,宽松)。
  3. 红黑树效率高于AVL树具体体现在:红黑树的最长链和最短链之间的长度差不会超过两倍。
  4. 红黑树和AVL树两者整体的复杂度都为O(log n)。

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

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

相关文章

CUDA学习笔记5——CUDA程序错误检测

CUDA程序错误检测 所有CUDA的API函数都有一个类型为cudaError_t的返回值&#xff0c;代表了一种错误信息&#xff1b;只有返回cudaSuccess时&#xff0c;才是成功调用。 cudaGetLastError()用来检测核函数的执行是否出错cudaGetErrorString()输出错误信息 #include <stdi…

项目快讯|深汕特别合作区气膜羽毛球馆正式开工

“永不坍塌”的气膜运动馆 “安全”是每个行业可持续发展的核心原则、是每个企业长久生存的重要底线、是每个人追求幸福生活的基本保障。 任何新行业、新技术、新材料、新工艺的发展都需要逐步规范化的企业标准、行业标准、国家标准。 气承膜技术发展的初期&#xff0c;面临行业…

springboot+vue基于Spark的共享单车数据存储系统的设计与实现【内含源码+文档+部署教程】

博主介绍&#xff1a;✌全网粉丝10W,前互联网大厂软件研发、集结硕博英豪成立工作室。专注于计算机相关专业毕业设计项目实战6年之久&#xff0c;选择我们就是选择放心、选择安心毕业✌ &#x1f345;由于篇幅限制&#xff0c;想要获取完整文章或者源码&#xff0c;或者代做&am…

BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain

BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain----《BadNets:识别机器学习模型供应链中的漏洞》 背景&#xff1a; 许多用户将训练过程外包给云计算&#xff0c;或者依赖于经过训练的模型&#xff0c;然后根据特定的任务对模型进行微调。这…

【python】机器学习-K-近邻(KNN)算法

目录 一 . K-近邻算法&#xff08;KNN&#xff09;概述 二、KNN算法实现 三、 MATLAB实现 四、 实战 一 . K-近邻算法&#xff08;KNN&#xff09;概述 K-近邻算法&#xff08;KNN&#xff09;是一种基本的分类算法&#xff0c;它通过计算数据点之间的距离来进行分类。在…

TCP--拥塞控制

大家好&#xff0c;我叫徐锦桐&#xff0c;个人博客地址为www.xujintong.com。平时记录一下学习计算机过程中获取的知识&#xff0c;还有日常折腾的经验&#xff0c;欢迎大家来访。 TCP中另一个重要的点就是拥塞控制&#xff0c;TCP是无私的当它感受到网络拥堵了&#xff0c;就…

transformer理解

李宏毅老师讲解的Transformer&#xff0c;非常简单易懂&#xff1a;https://www.youtube.com/watch? RNN存在的问题是&#xff0c;只有得到t(i)时刻的向量信息才能够计算t(i1)时刻的向量信息&#xff0c;无法实现并行化。无法实现长序列的特征信息提取&#xff0c;超过一篇文章…

【C++】哈希应用——海量数据面试题

哈希应用——海量数据面试题 一、位图应用1、给定100亿个整数&#xff0c;设计算法找到只出现一次的整数&#xff1f;2、给两个文件&#xff0c;分别有100亿个整数&#xff0c;我们只有1G内存&#xff0c;如何找到两个文件交集&#xff1f;&#xff08;1&#xff09;用一个位图…

Node.js与npm版本比对

Node.js与npm版本比对 Node.js与npm版本比对版本对比表Node版本对比 Node.js与npm版本比对 我们在项目开发过程中&#xff0c;经常会遇到公司一些老的前端工程项目&#xff0c;而我们当前的node及npm版本都是相对比较新的了。 在运行以前工程时&#xff0c;会遇到相关环境不匹…

浅谈uniapp中开发安卓原生插件

其实官方文档介绍的比较清楚而且详细,但是有时候他太墨迹,你一下子找不到自己想要的,所以我总结了一下开发的提纲,也是为了自己方便下次使用。 1.第一步,下载官方提供的Android的示例工程,然后倒入UniPlugin-Hello-AS工程请在App离线SDK中查找,之后Android studio,编译运行项目…

不会用PS抠图?教你懒人抠图法,必须学会!

相信很多小伙伴都有遇到这样的窘境——好不容易找到得素材图片&#xff0c;中间的图案很好看&#xff0c;可是特别想去掉后面的背景&#xff0c;应该如何抠图呢&#xff1f; 能够将图片中的物品或人物抠出来是一种很有用的技巧&#xff0c;可以在很多场景下应用&#xff0c;比…

MySQL -- 环境安装(CentOS7)

MySQL – 环境安装&#xff08;CentOS7&#xff09; 文章目录 MySQL -- 环境安装&#xff08;CentOS7&#xff09;一、环境安装1.卸载不必要的环境2.检查系统安装包3.卸载默认安装包4.获取MySQL官方yum源6.看看yum源能不能正常工作7.安装mysql服务 二、MySQL登录与配置1.启动My…

论文阅读 - Coordinated Behavior on Social Media in 2019 UK General Election

论文链接&#xff1a; https://arxiv.org/abs/2008.08370 目录 摘要&#xff1a; Introduction Contributions Related Work Dataset Method Overview Surfacing Coordination in 2019 UK GE Analysis of Coordinated Behaviors 摘要&#xff1a; 协调的在线行为是信息…

造车先做三蹦子220101--机器学习字符(字母、和数字识别)的“小白鼠”与“果蝇”

“0”数字字符零 的图片(16*16点阵)&#xff1a; #Letter23Digital23R231006d.pyimport torch import torch.nn as nn import torch.optim as optim #optimizer optim.SGD(model.parameters(), lr0.01) from PIL import Image from PIL import ImageDraw from PIL import Im…

取证之查看本机保存的WiFi密码

一、电脑保存有WiFi密码&#xff0c;且正常连接该WiFi 1、打开网络适配器高级选项 2、双击无线网卡&#xff0c;选择无线属性 3、点击安全&#xff0c;显示字符&#xff0c;即可看到WiFi密码。 二、电脑保存有密码&#xff0c;但是没有链接WiFi。 1、查看wlan接口上的配置文件…

OSPF的网络类型

1.3配置OSPF的网络类型 1.3.1实验3&#xff1a;配置P2P网络类型 实验需求 实现单区域OSPF的配置实现通过display命令查看OSPF的网络类型 实验拓扑 实验拓扑如图1-11所示 图1-11 配置P2P网络类型 实验步骤 步骤1&#xff1a;[1] 配置IP地址 路由器R1[2] 的配置 <Huawe…

【鸿蒙软件开发】文本显示(Text/Span)

文章目录 前言一、Text控件1.1 创建文本string字符串引用Resource资源 1.2 添加子组件创建Span文本装饰线和样式文本装饰线设置文字一直保持大写/小写添加事件。 1.3 自定义文本样式文本对齐长文本处理设置行高通过decoration属性设置文本装饰线样式及其颜色。通过baselineOffs…

Excel·VBA制作工资条

看到一篇博客《excel表头_Excel工资表怎么做&#xff1f;3分钟学会利用函数生成工资表》&#xff0c;使用排序功能、函数制作工资条。但如果需要经常制作工资条&#xff0c;显然使用VBA更加方便 VBA制作工资条 Sub 制作工资条()Dim title_row&, blank_row&, ws_new$,…

在 Python 中使用 Pillow 进行图像处理【3/4】

第三部分 一、腐蚀和膨胀 您可以查看名为 的图像文件dot_and_hole.jpg&#xff0c;您可以从本教程链接的存储库中下载该文件&#xff1a; 该二值图像的左侧显示黑色背景上的白点&#xff0c;而右侧显示纯白色部分中的黑洞。 侵蚀是从图像边界去除白色像素的过程。您可以通过使用…

【CANoe】文件处理_hex文件读取解析

hex文件里面只有00&#xff0c;01&#xff0c;04三种码。那么我们在解析的时候只需要对这三种不同状态的进行不同的解析即可。 hex文件格式的解析&#xff0c;可阅读&#xff1a;HEX文件格式详解 首先创建一个Block的结构体&#xff0c;根据经验我们知道&#xff0c;一个数据…