红黑树

红黑树五大特性

• 节点是红/黑
• 根结点是黑
• 空叶子是黑色的（叶子结点和度为一的结点：度为0和度为1）
• 红色结点的孩子肯定是黑色的（从根到空叶子的简单路径不存在连续红色结点）
• 从根出发到所有空叶子结点的简单路径当中黑色结点数量相同

因此，全黑的一条路径最短，并且 最长< 2*最短

建树

• 1 初始插入时红色的，先用二叉搜索树的朴素插入构建红黑树
• 2 插完之后染色并旋转

建树不同情况 （插入为红）

• 1 加入插入的是根，直接染黑
• 2 插入是子，如果父亲是黑色，不需要做任何调整
• 3 插入是子，父亲是红色（一定有爷爷结点，且是黑色，因为父亲是红色)，也一定有叔叔结点（空叶子也算），叔叔如果是红色，父亲和叔叔染黑, 爷爷染红->染红会出现问题，因此把爷爷看作新插入的结点，循环向上插入
• 4 插入是子，父亲是红色（一定有爷爷结点)，也一定有叔叔结点（空叶子也算），叔叔如果是黑色，
  如果父亲P的大小在新插入的N和爷爷G之间（插入的位置和父亲一样，比如父亲是左子树，插入的也是左子树；父亲是右子树，插入的也是右子树），则对G旋转，左边重(插入子左子树)，就右旋，右边重（插入在右子树），就左旋 （裙子形），并互换颜色，G和P颜色互换

  右旋：把爷爷作为父亲的右孩子结点
  左旋：把爷爷作为父亲的左孩子结点

• 5 插入有子，父亲是红色（一定有爷爷结点)，也一定有叔叔结点（空叶子也算），叔叔如果是黑色，但是新插入的N和父亲的位置相反。旋转P，之前是旋转G。如果父亲是左子树，则左旋P；如果父亲是右子树，则右旋P，现在回到情况4，使用情况4的方法就行；父亲在右边，N在左边，以父节点进行右旋，这是父亲和N都在右边，在进行上述情况4同右操作即可

总结

• 插入节点为根节点，变为黑色
• 父节点为黑色，直接插入
• 父节点和叔叔节点均为红色，父节点和叔叔节点均变为黑色，祖父节点变红，把祖父节点当作要插入节点，递归执行。
• 父节点和插入节点在同一边，父节点变黑，祖父节点变红，同左右旋，同右左旋。这里是对祖父结点进行的
• 父节点为红色，叔叔节点为黑色，如果不在同一边，转换为同一边（N在右边以父节点左旋；N在左边，以父节点右旋），然后执行步骤四。