红黑二叉树

顾名思义，节点颜色为红或黑色的二叉树，也称为“红黑二叉树”、“自平衡二叉树”

红黑树与普通二叉树有什么区别？

下面是普通二叉树的两种情况

如上图所示，在极端情况下，普通二叉树就会出现“一边倒”的情况(只有右/左子树)，而这样势必会导致二叉树的检索效率大大降低(O(n))，而“红黑二叉树”的出现就是为了解决这个问题。

红黑二叉树是通过颜色的约束来维持树的平衡，所以需要添加以下几个规则约束:

1. 每个节点都只能是红色或者黑色(除了根节点，其余节点初始化都是红色的)
2. 根节点是黑色
3. 每个叶节点（NIL节点，空节点）是黑色的。
4. 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

前4点比较好理解，第5点看图说话：

如上图，从节点8到其所有的叶子结点的所有路径:
8->7->a
8->7->b
8->9->c
8->9->d
可以看出上面4条路径的黑色节点数都是一样的

接下来先了解一下"左旋"、“右旋”的含义，还是看图说话:

如上图，节点X的“左旋”就是将X变成其右子节点Y的左子节点，原先节点Y的左子节点变成节点X右子节点

(可以理解为X往左边掉下去，然后Y拉住X，代价是X要帮忙拿Y手机的东西，因为Y的手用来拉住X了)

如上图，节点Y的“右旋”就是将Y变成其左子节点X的右子节点，原先节点X的右子节点变成节点Y左子节点

(可以理解为Y往右边掉下去，然后X拉住Y，代价是Y要帮忙拿X手里的东西，因为X的手用来拉住Y了)

接下来开始实践一下，如图所示：

我们可以看出，上图是一颗不符合第5点约束的红黑树(节点8->节点2的路径下黑色节点数不符合)，我们可以通过“左旋”、“右旋”以及变色的方式使其符合第5点约束，并趋于平衡；

具体操作：将节点8左旋，再变色

如下图(左旋)：

上图可以看出，通过左旋之后又出现新的问题，即违反了约束4，不能出现相邻的两个红色节点，所以需要进行变色

如下图(变色)：