一、红黑树的概念

红黑树的每个节点都有颜色（非黑即红），通过颜色来保证红黑树的平衡，是平衡搜索二叉树的一种。

二、红黑树的特性

1、任意一条路径上的节点都不能出现连续的红色节点。

2、最长路径不会超过最短路径的2倍。

3、任何一条路径的黑色节点都相同。

4、根节点一定是黑色。

5、叶子节点指向的空节点也是黑色。

三、如何保证红黑树的特性不被改变

1、当我们插入一个节点时应当插入什么颜色？

应当插入红色节点因为如果插入黑色节点那么这条路劲上的黑色节点会多一个其他路径上的黑色节点个数均少于该路径的黑色节点违反了特性3（任何一条路径的黑色节点都相同。）当我们插入红色节点时只会改变该路径上的黑白树特性1（任意一条路径上的节点都不能出现连续的红色节点。）

2、当我们插入一个红色节点单其父亲节点是红色应该怎么办呢？

有两种方法：

（1）改变颜色叔节点的颜色：如下图所示当我们要插入一个节点（30）时其父节点（20）是红色当（20）有兄弟节点（10）时那么该节点一定是红色（如果是黑色则该树违背了特性3）因此我们只需要将节点（15）改为红色，叔节点（10）和父亲节点（20）改为黑色即可。

（2）进行旋转： 

• 左旋转：当插入新节点（20）时由于父亲节点（15）是红色进行左旋，将（15）的左边指向（10），将（10）的右边指向（15）的右边，再将（15）改为黑色，（10）改为红色。

• 右旋转：当插入新节点（5）时由于父亲节点（8）是红色进行右旋，将（8）的右边指向（10），将（10）的左边指向（8）的右边，再将（8）改为黑色，（10）改为红色。

• 右左双旋：所谓的左右双旋就是先进行右旋在进行左旋，当插入节点（15）时先将（20）进行右旋，（20）的左边指向（15）的右边，（15）的右边指向（20），然后再将（10）进行左旋，将（15）的左边指向（10），将（10）的右边指向（15）的右边，再将（15）改为黑色，（10）改为红色。

• 左右双旋： 所谓的左右双旋就是先进行左旋在进行右旋，当插入节点（8）时先将（5）进行左旋，（5）的右边指向（8）的左边，（8）的左边指向（5），然后再将（10）进行左旋，将（8）的右边指向（10），将（10）的左边指向（8）的右边，再将（8）改为黑色，（10）改为红色。

3、 通过上述步奏可以保证每条路径上的黑色节点都相同，并且没有连续的两个红色节点，但是为什么就保证了最长路径不超过最短路径的两倍呢？

最长路径：黑节点和红节点相互交替的路径。

最短路径：全是黑节点的路径。

由于最长路径相当于在全是黑色节点的路径上间接插入红色节点，由于根节点是黑色的，叶子节点指向的空节点也是黑色，因此最长路径永远不可能比最短路径的两倍大。