红黑树的特征
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
- 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
- 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点
红黑树样例:
红黑树的应用
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
红黑树的基本操作
红黑树的左右旋
与普通二叉查找树的左右旋相同
左旋
右旋
红黑树的插入
1.将红黑树当做一棵普通二叉树进行插入
2.将插入节点染为红色
3.以插入节点为目标进行插入修复
以插入节点为目标进行插入修复
执行以下操作直到当前节点非根且父亲非红
若当前节点为父节点的左孩子：则进行以下处理，否则进行以下处理的对称操作
情况1：若当前节点的叔叔节点节点也是红色，交换父辈两节点和祖辈的颜色，然后继续循环对祖父节点进行处理（将祖父节点设为当前节点）
情况2：当前节点的叔叔节点为黑色
预处理：先判断当前节点是不是其父节点的右孩子，如果不是，直接进行第二步
如果是，先对将当前节点指向其父节点，然后对新的当前节点进行左旋。
预处理完毕：经过上一步处理，当前节点是父节点的右孩子。把当前节点的父节点变黑，祖父节点变红，然后把祖父节点右旋
红黑树的删除
情况1 : 被删除节点有两个子节点，寻找后续节点（以右子节点为根的最左边的叶子结点），后续节点存放在被删除节点中，保留源被删节点，实际删除后续节点，转化为其他情况处理（最左边叶子结点的左子节点肯定为空，没有两个子节点）。
对一下情况统一处理：若左子节点存在，用左子节点接替被删除节点，否则无论右子节点是否存在都用右子节点接替。
情况2：若被删除的节点被其存在的子节点替代，且被删除节点为黑色，则对替代节点进行修复
情况3：若整棵树只有被删除节点一个节点，则直接删除
情况4：若被删除节点为叶子结点，在删除前先判断是否为黑色，若为黑先针对被删除节点修复再删除。
以入参的节点为目标进行修复
以下操作循环处理，直到当前节点是根节点或当前节点是红色才停止
若当前节点是其父节点的左孩子，则进行以下操作，否则进行以下操作的对称操作。
预处理：先判断兄弟节点是否为红色，若是，则交换兄弟节点与父节点的颜色（父节点原来肯定是黑的）
然后以父节点为目标左旋,更新兄弟节点的指针，指向新兄弟节点。
情况1：兄弟节点的两个孩子都为黑色（nil也是黑）
将兄弟节点染红，当前节点指向父节点，循环继续。
以上四张图被删除节点属于无孩子的节点，在删除操作中是先修复后删除的，所以修复完成之后还不是红黑树。
情况2：兄弟节点有孩子是红的
预处理：如果兄弟节点的左孩子是红色，右孩子是黑色，兄弟节点的左孩子变黑，兄弟节点变红，对兄弟节点右旋转，把红色节点转移到右分支，更新兄弟节点的指针，指向新兄弟节点
预处理完毕： 经过上一步判断处理，兄弟节点是黑色，兄弟节点的左孩子是黑色，兄弟节点的右孩子是红色，把兄弟节点变成父节点的颜色，兄弟节点的右孩子变成黑色（不破坏右分支的规则），父节点变成黑色，对父亲节点左旋转，主要就在x节点的上面增加了一个黑色的父节点
将当前节点设为根节点，到循环判断时结束循环。