红黑树

定义

红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子结点的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出二倍，因此红黑树是近似于平衡的

性质

• 每个结点或是红色，或是黑色
• 根结点是黑色的
• 每个叶结点(NULL结点)都是黑色的
• 如果一个结点是红色的，则他的两个子结点都是黑色的
• 对每一个结点，从该结点到其所有的后代叶结点的简单路径上，均包含相同数目的黑色结点

旋转

注:在旋转过程中除了应该注意每个节点的子结点连接到指定位置，同时也应注意不同结点的父指针也要有相应的改变!!!

插入

• 初始化
  将需要插入的结点z按照二叉搜索树的方式插入树中，并将其颜色定义为红色

• 结束条件
  结点的父结点颜色为黑

• 保持循环
  保持循环，即 z的父结点为红色(红红冲突)，while循环中可能出现5种情况

  1. z的叔结点是红色
     将z的父结点和叔结点，颜色都改为黑色，将爷结点改为红色，指针z在树中上移两层
     

  • z的父结点是爷结点的左孩子

    2. z的叔结点 是黑色，且 z是一个右孩子
           进行左旋操作，z为旋转图例的y点
           变为情况3，执行对应操作
    3. z的叔结点 是黑色，且 z是一个左孩子
           将z的父结点变为黑色
           将z的爷结点变为红色
           右旋，z的父结点为旋转图例的x点
       

  • z的父结点是爷结点的右孩子

    4. z的叔结点 是黑色，且 z是一个左孩子
           进行右旋操作，z为旋转图例的x点
           变为情况5，执行对应操作
    5. z的叔结点 是黑色，且 z是一个右孩子
           将z的父结点变为黑色
           将z的爷结点变为红色
           左旋，z的父结点为旋转图例的y点
       

  注:3情况和5情况执行完变色旋转后即可退出循环

• 结束操作
  在进行相应操作时，可能会出现root为红色的情况，应在结束后将root变为黑色

删除

...写不动了0.0