设为首页 - 加入收藏 铜仁站长网 (http://www.0856zz.com)- 国内知名站长资讯网站,提供最新最全的站长资讯,创业经验,网站建设等!
热搜: 系统 平台 vivo
当前位置: 首页 > 运营中心 > 建站资源 > 优化 > 正文

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

发布时间:2019-09-26 10:48 所属栏目:[优化] 来源:Java的架构师技术栈
导读:很早之前就想写一篇关于红黑树的文章,但是由于担心自己理解的不透彻,就一直不敢下笔。于是在重新看了很多篇文章和资料之后,决定彻彻底底的把红黑树搞清楚。也希望让你在面试中游刃有余。OK,废话不多说,开始今天的文章。 整篇文章的思路是这样的,红黑

很早之前就想写一篇关于红黑树的文章,但是由于担心自己理解的不透彻,就一直不敢下笔。于是在重新看了很多篇文章和资料之后,决定彻彻底底的把红黑树搞清楚。也希望让你在面试中游刃有余。OK,废话不多说,开始今天的文章。

整篇文章的思路是这样的,红黑树其实就是一种数据结构,设计它的目的就是为了高效地进行增删改查,所以我们文章的顺序也会按照这个思路来进行。我们先从二叉查找树逐渐引入到红黑树,然后再详细的讲解。你如果看过其他文章想必也一定清楚,红黑树比较麻烦,希望你有点耐心,认真理解每一张图再往下分析。

一、二叉查找树

在正式开始了解红黑树之前呢,我们先来看一下二叉查找树的概念,从浅入深,希望你不要着急,下面就是是一颗二叉查找树:

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

从这张图我们会发现如下的规律:

(1)左子树上所有节点的值均小于或等于它的根结点的值。

(2)右子树上所有节点的值均大于或等于它的根结点的值。

如果我们想要查找一个数字11,过程是怎么样的呢?

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

上面的过程已经很清晰了,在查找的时候,先与根节点比较,比根节点大则从右子树查找,比根节点小则从左子树查找,然后重复上面的过程,一直到找到我们需要的元素为止。

这个过程是查找操作,对于添加和删除呢?其实原理也是一样的,我们第一步就是找到我们需要插入的位置,然后把元素插入即可。这样看二叉查找树挺好的呀?别着急我们继续往下看这种情况。

如果我们在刚刚开始的时候还是以9为根节点,然后依次插入13、15、17、19。我们看会发生什么情况:

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

好好地一棵树变成了这个鬼样子,成了“一边倒”了。这时候再去查找19呢?

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

这效率也太低下了吧,一颗二叉查找树的优势完全丧失了。怎么办呢?既然上面的二叉查找树在插入的时候变成了“一条腿”,也就是丧失了平衡,那我们干脆做出一点改进,使用平衡二叉树吧。

二、平衡二叉树

下面就是一颗平衡二叉树。

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

上面这颗二叉树就是平衡二叉树,也叫作AVL树。仔细分析你会发现如下特点:

(1)从任何一个节点出发,左右子树深度之差的绝对值不超过1。

(2)左右子树仍然为平衡二叉树。

现在我们再往里插入一个元素4,这时候会发生什么呢?

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

从图中我们可以看到,插入了4之后破坏了平衡,怎么办呢?既然破坏了平衡,那就想办法纠正过来。

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

我们发现经过调整之后,我们二叉树就重新回到了平衡。对于其他插入的情况,大家可以自己私下试一遍,最终你会发现一个结论,那就是平衡二叉树在插入时最多只需要两次旋转就会重新恢复平衡。

从上面这个过程我们会发现,平衡二叉树真的很不错,在查找时既有着二叉查找树的优越性,在插入时还能通过调整继续保持着。那么为什么还要使用到红黑树呢?我觉得可以从以下两个方面来考虑:

(1)删除:对于平衡二叉树来说,在最坏情况下,需要维护从被删节点到根节点这条路径上所有节点的平衡性,旋转的量级是O(logN)。但是红黑树就不一样了,最多只需3次旋转就会重新平衡,旋转的量级是O(1)。

(2)保持平衡:平衡二叉树高度平衡,这也就意味着在大量插入和删除节点的场景下,平衡二叉树为了保持平衡需要调整的频率会更高。

注意:在大量查找的情况下,平衡二叉树的效率更高,也是首要选择。在大量增删的情况下,红黑树是首选。

鉴于以上原因,因此我们才使用到了红黑树这种更好的结构。上面提了这么多次红黑树,相信你已经迫不及待的想要认识一下了。下面就正式拉开红黑树的序幕。

三、红黑树

红黑树听名字就知道,里面涉及到两种颜色:红色和黑色。我们直接来看一下:

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

上面这张图就是红黑树,你会发现他有如下特征(下面的特征最好看一个特征重新看一遍红黑树):

(1)每个节点只有两种颜色:红色和黑色。

(2)根节点是黑色的。

(3)每个叶子节点(NIL)都是黑色的空节点。

(4)从根节点到叶子节点,不会出现两个连续的红色节点。

(5)从任何一个节点出发,到叶子节点,这条路径上都有相同数目的黑色节点。

这五条就是红黑树的特征,你每看一个特征最好重新看一遍图,这样可以加深理解。这五条特征看起来真的很复杂,不过正是由于这些复杂的特征才保证了红黑树的良好特性。如何保证的呢?我们从增删改查四个角度来一个一个分析一下:

1、查询节点

查询节点是最简单的一个,他的查找过程和二叉查找树一样,查找元素比当前节点大,就从右子树继续查找比较,查找元素比当前节点小,就从左子树继续查找比较。查找过程就不再赘述了。

2、插入节点

插入节点是最麻烦的一个,它分为三种情况。我们一种一种看,这样比较有条理性。

第一种情况:新节点没有父节点

没有父节点只有一种情况,就是插入的节点是整棵树第一个节点,也就是根节点,为此我们只需要把插入节点涂成黑色就OK了。这也就保证了性质2:根节点是黑色的。

第二种情况:新节点的父节点是黑色

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章