红黑树
红黑树是满足下面红黑性质的二叉搜索树：
- 每个结点或是红色的，或是黑色的。
- 根结点是黑色的。
- 每个叶结点（NIL） 是黑色的。
- 如果一个结点是红色的，则它的两个子结点都是黑色的。
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
图片例子
一棵有 n 个内部结点的红黑树的高度至多为 **2·lg(n+1)**。
proof
查询操作
由此可知：**红黑树的高度是 O(lgn)**。再结合二叉搜索树的性质，我们可知：红黑树的查询操作（SEARCH、MINMUN、MAXIMUM、SUCESSOR）均是 **O(lgn)**。
旋转操作
图片
插入操作
插入新节点：使用二叉搜索树的
TREE_INSERT方法插入新节点，并将其颜色设为红色（可能会违反性质4，还需调整）。调整树以恢复红黑性质：检查父节点颜色。
如果新节点的父节点是黑色的，则树仍然是平衡的，不需要调整。
如果父节点是红色，则需要进一步检查叔叔节点：
如果新节点的叔叔节点存在且为红色：
将父节点和叔叔节点都涂成黑色，并将祖父节点涂成红色，然后从祖父节点重新开始调整过程（递归调用）。
如果叔叔节点是黑色或为空：
根据新节点和父节点相对于祖父节点的位置，进行以下旋转之一：
- 左左情况（LL）：新节点是其父节点的左孩子，且父节点是祖父节点的左孩子。进行右旋转，然后交换祖父节点和父节点的颜色。
- 右右情况（RR）：新节点是其父节点的右孩子，且父节点是祖父节点的右孩子。进行左旋转，然后交换祖父节点和父节点的颜色。
- 左右情况（LR）：新节点是其父节点的左孩子，但父节点是祖父节点的右孩子。首先对父节点进行左旋转，将新节点变为左左情况，然后进行右旋转并交换颜色。
- 右左情况（RL）：新节点是其父节点的右孩子，但父节点是祖父节点的左孩子。首先对父节点进行右旋转，将新节点变为右右情况，然后进行左旋转并交换颜色。
根节点颜色调整：如果新节点成为根节点（即原根节点是红色），则将其颜色改为黑色，以满足根节点必须是黑色的性质。
递归结束条件：当新节点变为黑色或成为根节点时，算法结束。
旋转图片 P182