红黑树

红黑树是一个自平衡的二叉查找树，除了具有二叉树查找树的特性，还具有附加的特性
红黑树特性：

  1. 根节点是黑色
  2. 结点是红色或黑色
  3. 每个叶子结点都是黑色的空节点
  4. 每个红色结点的两个子节点都是黑色（每个从叶子结点到根节点的所有路径上不能有两个连续的红色结点）
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些规则保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。
当插入一个元素破坏了红黑树的规则时，此时需要一些调整方法来调整红黑树，比如：左旋、右旋、变色操作。