红黑树学习系列笔记 (一)

定义和性质

1. 节点不是红色的就是黑色的
2. 根节点是黑色的;
3. 叶子节点是黑色的(NIL)空节点
4. 红色的节点不能相邻,红色节点的子节点必须是黑色的
5. 任意一节点到每个叶子节点的路径都包含数量相同的黑节点。

三种操作：左旋、右旋和变色。

1. 左旋：以某个节点作为支点 (旋转节点)，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。
2. 右旋：以某个节点作为支点 (旋转节点)，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子结点，右子节点保持不变。右旋只影响旋转节点和其左子树的结构，把左子树的节点往右子树挪了。
3. 变色：结点的颜色由红变黑或由黑变红。

• 左旋只影响旋转节点和其右子树的结构，把右子树的节点往左子树挪了。
• 右旋只影响旋转节点和其左子树的结构，把左子树的节点往右子树挪了。

插入操作

情景 1 ：关注节点的父节点为黑节点

由于插入的节点是红色的，当插入节点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

情景 2：关注节点结点的父结点为红节点

此时的祖父节点一定是黑色的，

2.1 关注节点的叔叔节点存在并且为红节点

操作

• 将父节点和叔叔节点的颜色对换，
  
• 此时的关注节点为祖父节点 C

情景 2.2 叔叔节点是黑色，关注节点是其父节点的右子节点，

操作

• 关注节点变成节点 a 的父节点 b；
  
• 围绕新的关注节点 b 左旋；
  
• 跳到 CASE 2.3

情景 2.3：关注节点的叔叔节点不存在或为黑结点，并且关注节点的父亲结点是祖父结点的左子结点

操作

• 围绕关注节点的祖父节点右旋
• 将旋转后的关注节点的父节点、兄弟节点的颜色互换。