红黑树
特征
- 每个节点要么是黑色，要么是红色
- 根节点是黑色
- 每个叶子节点 (NIL) 是黑色
- 每个红色节点的两个子节点一定是黑色
- 任意一节点到每个叶子节点的路径都包含相同数量的黑节点
- 如果一个节点存在黑子节点，那么该节点肯定有两个子节点
红黑树自平衡
- 左旋
- 以某个节点作为
旋转节点，其右子节点旋转为父节点，右子节点的左子节点旋转变为旋转节点的右子节点，左子节点保持不变。
- 以某个节点作为
- 右旋
- 以某个节点作为
旋转节点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
- 以某个节点作为
- 变色
- 红变黑、或黑变红。