红黑树

特征

• 每个节点要么是黑色，要么是红色
• 根节点是黑色
• 每个叶子节点 (NIL) 是黑色
• 每个红色节点的两个子节点一定是黑色
• 任意一节点到每个叶子节点的路径都包含相同数量的黑节点
  • 如果一个节点存在黑子节点，那么该节点肯定有两个子节点

红黑树自平衡

• 左旋
  • 以某个节点作为旋转节点，其右子节点旋转为父节点，右子节点的左子节点旋转变为旋转节点的右子节点，左子节点保持不变。
• 右旋
  • 以某个节点作为旋转节点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
• 变色
  • 红变黑、或黑变红。