红黑树

一种自平衡的BST，具有如下性质——

1. 每个节点不是红色就是黑色
2. 根节点必须是黑色。
3. 叶子节点（NIL 节点）被视为黑色。
4. 如果一个节点是红色，则它的两个子节点都是黑色。
5. 从任一节点到其所有后代 NIL 节点的简单路径都包含相同数目的黑色节点。

在插入的时候，如果插入节点为黑色，必然违反性质5，所以只能是红色——但是如果它的父节点是红的，就违反性质4。

为了维护它的性质，需要引入修改颜色和左旋、右旋的操作—— 在脑子中可以想象为一个长度为4的链绕中间的节点旋转了一下（左右旋就是方向不同而已）

改色就是把黑色节点改成红色节点；红色节点改成黑色节点，问题不大。

论左右旋 ——

左旋

将节点的右子节点上提为局部根，原根下移为左子

下面假设对x处进行左旋

   x                    y
  / \                  / \
 α   y      左旋       x   γ
    / \   -------->  / \
   β   γ            α   β

（把 $\beta$ 看作支点，其余四个节点形成的链往左倾倒了一下）

右旋

     x                  y
    / \                / \
   y   γ     右旋      α   x
  / \     --------->     / \
 α   β                   β   γ

（把 $\beta$ 看作支点，其余四个节点形成的链往右倾倒了一下）