红黑树

1. 一种平衡树，时间复杂度O（logN）
2. 插入删除等操作红黑树性能优于AVL树
3. 红黑树一些特性

• 节点是红色或黑色
• 根节点是黑色
• 每个叶子节点都是黑色的空节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）
• 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点

4. 红黑树的约束

• 从根节点到任意节点的路径不可能是最短路径的二倍

5. 插入变化规则

• 新节点位于树的根上，没有父节点

//直接添加，节点变色，变成黑色,加nil

• 新节点的父节点是黑色

//直接添加，不变色，加nil

• P为红色，U也为红色（父红叔红祖黑）

//变成父黑叔黑祖红，再按规则二添加
//如果祖节点的父节点也是红色，再递归处理

• 父红叔黑祖黑N左

//1.祖节点G进行右旋转
//2.交换以前的父节点和祖节点的颜色（P变黑，G变红）
//3.B向右移成为G的左子节点

• 父红叔黑祖黑N右

//1. 以P为祖节点进行左旋转，回到情况四
//2. 以G为祖节点进行右旋转
//3. N、G交换颜色