看了这么多篇红黑树文章，你理解了嘛？ _红黑树

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

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

文章插图

从这张图我们会发现如下的规律：
（1）左子树上所有节点的值均小于或等于它的根结点的值。
（2）右子树上所有节点的值均大于或等于它的根结点的值。
如果我们想要查找一个数字11，过程是怎么样的呢？

文章插图

上面的过程已经很清晰了，在查找的时候，先与根节点比较，比根节点大则从右子树查找，比根节点小则从左子树查找，然后重复上面的过程，一直到找到我们需要的元素为止。
这个过程是查找操作，对于添加和删除呢？其实原理也是一样的，我们第一步就是找到我们需要插入的位置，然后把元素插入即可。这样看二叉查找树挺好的呀？别着急我们继续往下看这种情况。
如果我们在刚刚开始的时候还是以9为根节点，然后依次插入13、15、17、19 。我们看会发生什么情况：

文章插图

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

文章插图

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

文章插图

上面这颗二叉树就是平衡二叉树，也叫作AVL树。仔细分析你会发现如下特点：
（1）从任何一个节点出发，左右子树深度之差的绝对值不超过1 。
（2）左右子树仍然为平衡二叉树。
现在我们再往里插入一个元素4，这时候会发生什么呢？

文章插图
【看了这么多篇红黑树文章，你理解了嘛？】
从图中我们可以看到，插入了4之后破坏了平衡，怎么办呢？既然破坏了平衡，那就想办法纠正过来。

文章插图

我们发现经过调整之后，我们二叉树就重新回到了平衡。对于其他插入的情况，大家可以自己私下试一遍，最终你会发现一个结论，那就是平衡二叉树在插入时最多只需要两次旋转就会重新恢复平衡。
从上面这个过程我们会发现，平衡二叉树真的很不错，在查找时既有着二叉查找树的优越性，在插入时还能通过调整继续保持着。那么为什么还要使用到红黑树呢？我觉得可以从以下两个方面来考虑：
（1）删除：对于平衡二叉树来说，在最坏情况下，需要维护从被删节点到根节点这条路径上所有节点的平衡性，旋转的量级是O(logN) 。但是红黑树就不一样了，最多只需3次旋转就会重新平衡，旋转的量级是O(1) 。
（2）保持平衡：平衡二叉树高度平衡，这也就意味着在大量插入和删除节点的场景下，平衡二叉树为了保持平衡需要调整的频率会更高。