红黑树：基于红黑规则实现自平衡排序二叉树

红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。1972年出现，当时被称之为平衡二叉B树。1978年被修改为如今的"红黑树"。每一个节点可以是红或者黑;红黑树不是通过高度平衡的，它的平衡是通过“红黑规则”进行实现的。

红黑规则：

每一个节点或是红色的，或者是黑色的，根节点必须是黑色。

如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。

对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

添加的节点的颜色，可以是红色的，也可以是黑色的。红黑树默认用红色效率高。如下假设添加20、18、23三个元素，一共需要调整两次。

根节点是黑色，添加20、18、23三个元素，一共需要调整一次。所以，添加节点时，默认为红色，效率高。

当添加的节点为根节点时，根节点直接变成黑色就可以了

当父节点为黑色，则不需要做任何操作。其父节点为红色，叔叔节点也是红色。将“父节点23”设为黑色，将“叔叔节点18”设为黑色。将“祖父节点20”设为“红色”。如果祖父节点为根节点，则将根节点再次变成黑色。

其父节点为红色，叔叔节点也是红色。

其父节点为黑色，则不需要做任何操作。

其父节点为红色，叔叔节点也是红色。将“父节点16”设为黑色，将“叔叔节点19”设为黑色，将“祖父节点18”设为“红色”。如果祖父节点为根节点，则将根节点再次变成黑色。

将“父节点16”设为黑色，将“叔叔节点19”设为黑色，将“祖父节点18”设为“红色”。如果祖父节点为根节点，则将根节点再次变成黑色。

将“父节点15”设为“黑色”，“祖父节点16”设为“红色”，以祖父节点为支点进行旋转，其父节点为红色，叔叔节点也是黑色。

红黑树增删改查的性能都很好，但红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的。

规则如下：

每一个节点或是红色的，或者是黑色的，根节点必须是黑色

如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的;

如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)

对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。