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

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

一、二叉查找树

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

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

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

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

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

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

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

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

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