1.红黑树描述：它或是一颗空树，或是具有下面属性的二叉搜索树：

　　1）节点非红即黑；
　　2）根节点是黑色；
　　3）所有NULL结点称为叶子节点，且认为颜色为黑 ；
　　4）所有红节点的子节点都为黑色；
　　5）从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。

　　插入和删除操作时间可以保持为 O(log n) 次，图1（本文图来自维基百科）是一个具体的红黑树：

图1：红黑树

　　2.红黑树插入：假设插入节点为红，根据邻近结点的颜色进行具体调整：

　　1）为空树，直接插入，把颜色变换为黑；

　　2）插入结点的父结点为黑，直接插入，不做调整；

　　3）插入结点父结点和叔父结点都为红，则把他们两个重设置为黑，设置其祖父结点为红，设置过程如图2。以递归的方式检验整个树。

图2：父叔结点都为红的处理过程

　　4）父节点是红色而叔父节点是黑色或缺少，新节点是其父节点的左子节点，而父节点又是祖父节点的左子节点。进行针对祖父节点的一次右旋转，在旋转产生的树中，以前的父节点现在是新节点和以前的祖父节点的父节点，如图3所示。

图3：父红叔为黑或缺少，父为祖父左子树处理

　　5）父节点是红色而叔父节点是黑色或缺少，新节点是其父节点的右子节点而父节点又是祖父节点的左子节点。进行一次左旋转调换新节点和其父节点的角色，然后按照4）进行处理。

图4：父红叔为黑或缺少，父为祖父左子树处理

　　3.红黑树删除：

　　1）删除是新的根，直接操作。

　　2）S是红色，在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。

图5：S是红的处理

　　3）N的父亲、S和S的儿子都是黑色的。在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。

图6:N的父亲、S和S的儿子都是黑色的处理

　　4）S和S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换N的兄弟和父亲的颜色。

图7：S和S的儿子都是黑色，N的父亲是红色处理

　　5）S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。

图8：S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子处理

　　6）S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。

图9：S是黑色，S的右儿子是红色，而N是它父亲的左儿子

二叉树学习四：红黑树（参考维基百科）