每个节点要么是红色要么是黑色
根节点为黑色，叶节点（NIL）为黑色
每个节点到其任一子孙节点的每一条简单路径黑色节点的数量相同
红色节点的孩子节点均为黑色
二、红黑树的操作（插入、删除）
旋转操作不会改变节点的颜色。同时旋转操作同AVL树，不再赘述。
插入和删除操作都可能使得红黑树的性质遭到破坏，所以需要进行相应的改变（颜色的变化或是节点的旋转）
1. 插入
将插入节点的颜色定义为红色。如此，如果待插入节点的父节点为黑色，那么直接进行插入操作即可。需要讨论的是当待插入节点的父节点为红色的情况，仅以左孩子为例。
（1）插入到左孩子，此时
插入时第一种情况
（2）插入到右孩子
插入时第二种情况
只需要对待插入节点的父节点进行一次左旋操作，即可转化为（1）
下面进行实战分析
假定有一组数【12，15，19，25，27，35，37】，需要插入16，红黑树如下图所示
插入举例1
此时考虑情况（1）的第一种形式
插入举例2
接下来考虑情况（2）
插入举例3
最后考虑情况（1）的第二种形式，得到最后的结果如下图所示
插入举例4
2. 删除
（1）只有一个子节点
（2）左右孩子均存在，若待删除节点的后继节点（右子树最左侧的节点）为红色，则无论待删除节点为什么颜色，直接将后继节点的value赋值给当前节点，然后删除后继节点即可。
（3）后继节点为黑色
后继节点为其父节点的左节点
后继节点的兄弟节点为红色，将其兄弟节点与父节点颜色互换，对父节点左旋，将其父节点与其父节点的右节点颜色互换。
后继节点的兄弟节点为红色
后继节点的兄弟节点为黑色，其兄弟节点右节点存在，将其兄弟节点与父节点的颜色互换，令其兄弟节点的右节点为黑色，对其父节点进行左旋即可。
后继节点的兄弟节点为黑色，其兄弟节点右节点不存在，将其兄弟节点与兄弟节点的左节点颜色互换，对其兄弟节点右旋，转化为b
后继节点为其父节点的右节点
后继节点的兄弟节点为红色，转换同I-a
后继节点的兄弟节点为黑色，左节点存在，转换同I-b
后继节点的兄弟节点为黑色，左节点不存在，转换同I-c
后继节点的兄弟节点为黑色，无孩子节点，待删除节点为红色
会改变深度的情况
待删除节点为黑色，其子节点均为黑色
分类: 数据结构https://www.cnblogs.com/fanzhongjie/p/10141502.html
