红黑树

红黑树

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
红黑树具有以下性质:

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

旋转和变色

由于插入或者旋转会打破红黑树的性质，所以需要变色和旋转来维持红黑树的性质和平衡。
变色只需将黑色结点变为红色或将红色结点变为黑色。旋转操作分为左旋和右旋。

插入

1. 插入结点是根节点（插入前是一棵空树）：直接把插入结点涂为黑色。

2. 插入结点的父结点是黑色的：直接插入。

3. 插入结点的父结点是红色的：

   1）插入结点Z的叔结点是红色：将父结点和叔结点设为黑色，祖父结点设为红色。将祖父结点设为当前红色结点继续操作。
   2）插入结点Z的叔结点是黑色且当前结点是父亲结点的右孩子：将父亲结点作为新的当前结点并以新的当前结点为支点进行左旋，将插入结点Z原来的父亲结点和祖父结点变色。
   3)插入结点Z的叔结点是黑色且当前结点是父亲结点的左孩子：以插入结点Z的父节点为支点向右旋转，会得到情况2)，再进行2)的操作即可。

删除

红黑树的删除基于二叉搜索树的性质。

1. 删除的是红色结点：不会破坏红黑树的性质，直接删除。

2. 删除的是黑色结点：
   1）待删除结点(X)的兄弟结点是黑色，且其(W)子结点都是黑色：将待删除结点的兄弟结点变为红色，再以待删除结点的父结点开始作为迭代对象继续进行修复操作，直到迭代对象成为根节点或为红色时为止，最后再把迭代对象变为黑色来保证不会出现相邻的红色结点。
   2）待删除结点(X)的兄弟结点是黑色，其(W)右子结点是红色：将待删除结点的兄弟结点变色为和待删除结点的父结点同色，再将待删除结点的兄弟结点的父结点和右子结点变为黑色，最后把待删除结点的父结点进行左旋。

3）待删除结点(X)的兄弟结点是黑色，其(W)子结点左红右黑：先交换待删除结点的兄弟结点和其左子结点的颜色，再以待删除结点的兄弟结点为支点进行右旋，这时会变成情况2）。
4）待删除结点(X)的兄弟结点是红色：交换待删除结点的兄弟结点和待删除结点的父结点的颜色，再以待删除结点的父结点为支点进行左旋，这样就转化为以上三种情况之一。