红黑树的特性

  1. 节点为红色或者黑色
  2. 根节点必须是黑的
  3. 红色节点的左右子节点必须为黑色
  4. 一个节点到叶子节点的每条路径必须包含相同数目的黑色节点

颜色变换和两种选择

添加新节点后，因为新节点总是红色的，那么会有几种情况出现：

  1. 新节点是根节点，也就是说树是空的，根据规则二，把新节点设为黑色即可
  2. 新节点的父节点是黑色，或者父节点是根，满足规则
  3. 父节点是红色，违反规则三，需要进行 平衡 操作

平衡操作主要是根据情况组合使用下面三种转换（方块表示一棵满足红黑树规则的子树）：

op_1.png

op_2.png

op_3.png

为什么要进行旋转？

由于 P（父节点 和 X（新节点）都为红色，违反规则三

为什么新节点总是红色？

因为添加新节点前的树结构是构建好的，一但我们添加黑色节点，无论添加在哪里都会破坏原有路径上的黑色节点的数量平等关系，所以插入红色节点是正确的选择