红黑树 ​

红黑树（Red-Black-Tree）

特点 ​

1. 根节点必须是黑色的
2. 每个叶子节点都是黑色的空节点
3. 红色节点不能相邻
4. 从该节点到可达节点的路径上的黑色节点数量相等

实现 ​

左旋、右旋（四种情况）

1. 三个节点呈右节点形式 right right 着色

1
  2
    3

1
  2
    3

2. 三个节点呈左节点形式 left left 着色

    3
  2
1

    3
  2
1

3. 三个节点呈右左节点分布 right left/right right 着色

1
  3
2

1
  3
2

4. 三个节点呈左右节点分布 left right/left left 着色

  3
1
  2

  3
1
  2