Red-Black Tree红黑树

红黑树特点：

        1.根节点必须为黑色；

        2.每个节点到子节点经过相同数目的黑色节点；

        3.红色节点的子节点必须是黑色；

        4.空指针也作为节点

红黑树如何插入新的节点？

        1.如果是空树，插入新的黑色节点作为根节点；

        2.如果不为空，插入一个新的红色节点；

        3.如果父节点是黑色则不管；

        4.如果父节点的颜色是红色，他也是红色，那么执行重新着色，并检查新节点的父节点，如果它不是根节点，那么重新着色，父节点变黑色；

        5.如果父亲颜色是红色，父亲的兄弟节点是空或黑色，则需要旋转变色；|Height(RightTree)-Height(LeftTree)|<=1;不满足条件，所以该进行左下旋、右下旋、LR先左上旋再右下旋、RL先右上旋再左下旋

        6.父节点为红色，子节点为红色，如果不是根节点，则重新着色

红黑树与平衡二叉树使用场景：

        大量的增删操作，搜索较少可以使用红黑树；

        大量的搜索，较少的增删操作可以使用平衡二叉树；