一、性质

1.根节点是黑色。

2.节点不是黑色就是红色。

3.叶子节点都是黑色。（会产生很多黑色空节点）

4.红色节点的子节点都是黑色。

5.所有节点到叶子节点的各条路径中，黑色节点数量一样。

红黑树等价于四阶B树，四阶B树每个超级节点中的节点个数为1-3个。

添加、删除时需保证同时满足上述五条性质。所以在添加节点时，需要添加红色节点，这样就满足了1、2、3、5这几条性质，此时只需要考虑性质4是否满足。

二、添加（添加的节点都在叶子节点）

1.添加时的父节点是黑色，则直接添加，不需要做任何修复处理。

2.如果添加节点叔父节点是红色，则造成上溢。需要将原先节点上溢到上一层节点，将此节点染红，当做新添加的子节点进行处理，将此节点的两个子节点都染黑成为子节点。

3.如果添加的节点叔父节点是黑色，则有四种情况，根据相应情况进行旋转。如果是ll或rr，将父节点染成黑色，将祖父节点染成红色，ll对祖父节点进行右旋，rr对祖父节点进行左旋。如果是lr或rl情况，将自己染成黑色，将祖父节点染成红色，lr对父节点进行左旋，对祖父节点进行右旋，rl对父节点进行右旋，对祖父节点进行左旋。

三、删除（要删除的节点都在叶子节点）

1.如果要删除的节点是红色，则直接删除，不需做任何修复处理。

2.如果要删除的节点是黑色，并且此黑色节点有两个红色子节点。不需要做任何处理。此时真正要删除的元素是黑色节点的前驱和后继节点。

3.要删除的黑色节点有一个红色子节点，将用以替代的子节点染黑即可。

如下情况都以被删除节点是父节点的右子节点为例(被删除节点是父节点左节点与此情况相反)：

4.要删除的黑色节点无红色子节点：

4.1：如果此节点的兄弟节点是黑色：

4.1.1：兄弟节点有红色子节点:可以向兄弟节点借节点。如果红色子节点是兄弟节点的右边，则将兄弟节点进行左旋操作，再对要删除节点的父节点进行右旋操作。如果红色字节点是兄弟节点左边或左右两边都有，则直接对要删除节点的父节点进行右旋操作。旋转后，将中心节点继承原父节点颜色，旋转之后的左右节点染黑。

4.1.2：兄弟节点无红色子节点:如果要删除节点的父节点是红色，则将父节点染黑，兄弟节点染红即可。如果要删除节点的父节点是黑色，则导致父节点也会下溢，则把父节点当做被删除的节点处理即可。

4.2：如果此节点兄弟节点是红色：

则将兄弟节点染黑，父节点染红后，进行旋转，于是回到兄弟节点是黑色的情况。

四、总结

黑红树是一种弱平衡，黑高度平衡。

平均时间复杂度：

搜索：O（logn）

添加：O（logn），O(1)的旋转操作

删除：O（logn），O(1)的旋转操作

五、对比AVL树

平衡标准：

AVL树的平衡标准比较严格：每个左右子树的高度差不超过1。

红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍。

最大高度：

AVL树的最大高度相比红黑树小。

搜索、添加、删除

AVL数：搜索、添加、删除都是O(logn)级别，其中添加仅需O(1)级别旋转调整，删除最多需要O(logn)次操作。

红黑树：搜索、添加、删除都是O(logn)级别，其中添加、删除都仅需O(1)级别旋转调整。

应用：

如果搜索次数大大大于添加和删除，选择AVL数；搜索、插入、删除次数几乎差不多，选择红黑树。

相对于AVL树，红黑树牺牲了部分平衡以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树。