红黑树，一种特殊的二叉查找树，他的的五个性质：
每个结点要么是红的，要么是黑的。
根结点是黑的。
每个叶结点，即空结点（NIL）是黑的。
如果一个结点是红的，那么它的俩个儿子都是黑的。
对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
定理：一棵含有n个节点的红黑树的高度至多为2log(n+1)
红黑树插入：
第一步: 将红黑树当作一颗二叉查找树，将节点插入
第二步：将插入的节点着色为"红色"
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树
几种情况：
父节点是黑色：不破坏性质，不影响
当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色：
将“父节点”设为黑色。
将“叔叔节点”设为黑色。
将“祖父节点”设为“红色”。
将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子：
将“父节点”作为“新的当前节点”。
以“新的当前节点”为支点进行左旋。
当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子：
将“父节点”设为“黑色”
将“祖父节点”设为“红色”
以“祖父节点”为支点进行右旋
红黑树删除：
第一步：将红黑树当作一颗二叉查找树，将节点删除。
第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
几种情况：
x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
将x的兄弟节点设为“黑色”。
将x的父节点设为“红色”。
对x的父节点进行左旋。
左旋后，重新设置x的兄弟节点。
x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
将x的兄弟节点设为“红色”。
设置“x的父节点”为“新的x节点”。
x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
将x兄弟节点的左孩子设为“黑色”。
将x兄弟节点设为“红色”。
对x的兄弟节点进行右旋。
右旋后，重新设置x的兄弟节点。
x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色
将x父节点颜色 赋值给 x的兄弟节点。
将x父节点设为“黑色”。
将x兄弟节点的右子节设为“黑色”。
对x的父节点进行左旋。
设置“x”为“根节点”。