红黑树

定义

是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找(搜索)树，满足下列性质：

1）节点是红色或黑色；

2）根节点是黑色；

3）所有叶子节点都是黑色节点(NULL)；

4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

红黑树可以解决二叉树搜索树出现的长短腿情况

构建过程

红黑树是一种自平衡二叉查找树，从上面红黑树的图可以看到，根结点右子树显然比左子树高，但左子树和右子树的黑结 点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点。所以我们叫红黑树这种平衡为黑色完美平衡。

给定如下数组来构建红黑树

1.使用第一个元素创建一个根结点(黑色)。

2.插入13，根据二叉搜索树规则，应该插入到左侧，此时插入红色结点不会破坏红黑树平衡，直接插入即可。

3.插入16，插入红色结点不会破坏平衡，直接插入。

4.插入11，此时插入红色结点会破坏平衡(红色结点下面必须是两个黑色结点)，但插入黑色结点也会破坏平衡(从任一结点到其每个叶子结点的所有简单路径都包含相同数量的黑色结点)，所以对此进行调整。

5.插入9，应该插入到11的下方，无论插入红色结点还是黑色结点都会破坏平衡，所以，进行调整。

6.插入7，应该到9的下方，插入红色结点或是黑色结点都会破坏平衡，进行调整。旋转处理。

7.插入5，应该插入到7的下方，此时插入红色结点或是黑色结点都会破坏平衡，进行调整。变色处理。

8.插入3，应该插入到5的下方，无论插入黑色结点还是红色结点都会破坏平衡。进行调整。对根节点进行右旋。