看了这么多篇红黑树文章，你领略了嘛？

很早之前就想写一篇关于红黑树的文章，可是因为担忧本身领略的不透彻，就一向不敢下笔。于是在从头看了许多篇文章和资料之后，抉择彻彻底底的把红黑树搞清晰。也但愿让你在口试中游刃有余。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：根节点是玄色的。

第二种环境：新节点的父节点是玄色

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!