国内最专业的IT技术学习网

UI设计

当前位置:主页 > UI设计 >

看了这么多篇红黑树文章,你理解了嘛?

发布时间:2019/09/23标签:   节点    点击量:

原标题:看了这么多篇红黑树文章,你理解了嘛?
很早之前就想写一篇对于红黑树的文章,然而因为担忧本人懂得的不透辟,就始终不敢下笔。因而在从新看了许多篇文章和材料以后,决议彻完全底的把红黑树搞清晰。也盼望让你在口试中游刃不足。OK,空话未几说,开端明天的文章。整篇文章的思绪是如许的,红黑树实在就是一种数据构造,计划它的目标就是为了高效地停止增编削查,以是咱们文章的次序也会依照这个思绪来停止。咱们先从二叉查找树逐步引入到红黑树,而后再具体的讲授。你假如看过其余文章想必也必定清晰,红黑树比拟费事,盼望你有点耐烦,当真懂得每一张图再往下剖析。1、二叉查找树在正式开端懂得红黑树之前呢,咱们先来看一下二叉查找树的观点,从浅入深,盼望你不要焦急,上面就是是一颗二叉查找树:

看了这么多篇红黑树文章,你理解了嘛?
从这张图咱们会发觉以下的法则:(1)左子树上全部节点的值均小于或即是它的根结点的值。(2)右子树上全部节点的值均大于或即是它的根结点的值。假如咱们想要查找一个数字11,进程是怎样样的呢?
看了这么多篇红黑树文章,你理解了嘛?
下面的进程曾经很清楚了,在查找的时间,先与根节点比拟,比根节点大则从右子树查找,比根节点小则从左子树查找,而后反复下面的进程,始终到找到咱们须要的元素为止。这个进程是查找操纵,关于增加和删除呢?实在道理也是一样的,咱们第一步就是找到咱们须要拔出的地位,而后把元素拔出便可。如许看二叉查找树挺好的呀?别焦急咱们持续往下看这类情形。假如咱们在方才开端的时间仍是以9为根节点,而后顺次拔出13、15、17、19。咱们看会产生甚么情形:
看了这么多篇红黑树文章,你理解了嘛?
好好地一棵树酿成了这个鬼模样,成了“一边倒”了。这时间再去查找19呢?
看了这么多篇红黑树文章,你理解了嘛?
这效力也太低下了吧,一颗二叉查找树的上风完整损失了。怎样办呢?既然下面的二叉查找树在拔出的时间酿成了“一条腿”,也就是损失了均衡,那咱们罗唆做出一点改良,应用均衡二叉树吧。2、均衡二叉树上面就是一颗均衡二叉树。
看了这么多篇红黑树文章,你理解了嘛?

上一篇:如何在Fedora上建立一个TFTP服务器

下一篇:没有了

返回
版权信息Copyright © 银河官网 版权所有    ICP备案编号:鲁ICP备09013610号