红黑树
红黑树是一种自平衡二叉搜索树。因为以下的六个属性，所以能维持半平衡结构：
1.所有的节点要么红色，要么黑色。
2.根节点都是黑色
3.叶子节点不包含数据，且都是黑色
4.非叶子节点都有两个子节点
5.如果一个节点是红色，那么他的子节点都是黑色
6.任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
红黑树中每次插入的节点都预设为红色，插入后可能导致第5条不符合规定，则进行变色 上述条件保证了最深的叶子节点深度不会大于两倍的最浅叶子节点的深度，所以能维持半平衡结构。原因如下： 红黑树中最短的路径为全部都是黑色的路径，而第六条阐述了所有路径都包含相同数量的黑色节点，那么有可能的最长路径则为红黑交叉的路径，从而最深的叶子节点深度不会大于两倍的最浅叶子节点深度。其实只有树高为2的时候才有可能是两倍？？其他情况下因为本身就是平衡二叉树，所以最深和最浅的路径最大相差1.
红黑树的插入过程
红黑树插入过程中，该节点首先被设置为红色。
插入完毕后可能有3种情况
插入节点为根节点，直接涂为黑色
插入节点的父节点为黑色
无需操作，节点被插入后仍然为红黑树
插入节点的父节点为红色
与红黑树的特性冲突，而且因为根节点为黑色，那么该插入节点一定存在非空祖父节点和叔叔节点，根据叔叔节点进一步讨论
核心思路为：将红色的节点移到根节点；然后，将根节点设为黑色
叔叔节点为红色
操作步骤：
父节点设置为黑色
叔叔节点设置为黑色
祖父节点设置为红色
将祖父节点设为'当前节点'进行迭代操作
其实就是向上两代进行颜色翻转 
叔叔节点为黑色（叔叔节点其实就是叶子节点）
当前节点为父节点的右孩子
操作步骤：
以父节点为支点进行左旋
原理：当前节点为右孩子，根据核心思想(将红色的节点移到根节点；然后，将根节点设为黑色)那么就要不断的将破坏红黑树特性的红色节点上移，也就是将当前节点上移。又因为当前节点为父节点的右孩子，所以要左旋 
当前节点为父节点的左孩子
操作步骤：
父节点设置为黑色
祖父节点设置为红色
以祖父节点为支点进行右旋
原理：孩子节点和父节点都是红色，所以要把父节点变黑，然后父节点和叔叔节点都是黑色，那么就将祖父节点由黑变红再以祖父节点为支点右旋 
红黑树的删除过程
基本步骤
1.将红黑树当做一棵二叉查找树，从二叉查找树中删除该节点。
若被删除节点没有儿子，直接删除
若只有一个儿子，那么用儿子顶替该节点
如果有两个儿子，那么要找出其后继节点，然后将后继节点的内容复制到该节点，然后删除后继节点。
2.通过旋转和着色来修正该树为红黑树。
与红黑树的特性冲突，而且因为根节点为黑色，那么该插入节点一定存在非空祖父节点和叔叔节点，根据叔叔节点进一步讨论
核心思路为：将红色的节点移到根节点；然后，将根节点设为黑色
父节点设置为黑色
叔叔节点设置为黑色
祖父节点设置为红色
将祖父节点设为'当前节点'进行迭代操作
以父节点为支点进行左旋
父节点设置为黑色
祖父节点设置为红色
以祖父节点为支点进行右旋
基本步骤
1.将红黑树当做一棵二叉查找树，从二叉查找树中删除该节点。
若被删除节点没有儿子，直接删除
若只有一个儿子，那么用儿子顶替该节点
如果有两个儿子，那么要找出其后继节点，然后将后继节点的内容复制到该节点，然后删除后继节点。
2.通过旋转和着色来修正该树为红黑树。