红黑树的旋转、变色

什么是旋转？

旋转是以一个父节点作为参照物的。旋转分为左旋转与右旋转，其对应的结果就是将左子节点（后称左节点）或右子节点（后称右节点）替换原来的父节点，具体操作如下。

右旋转：

1. 使左节点成为新的父节点。
2. 原来的父节点，成为新的右节点。
3. 先前左节点的右子树，变成新右节点的左子树。

左旋转则是一个相反的过程：

1. 使右节点成为新的父节点。
2. 原来的父节点，成为新的左节点。
3. 先前右节点的左子树，变成新左节点的右子树。

?

---

旋转改变了什么？

通过上图不难看出，无论是左旋还是右旋，始终都没有改变二叉搜索树的大小排序：α < X < β < Y < γ。变化的，仅仅是将一颗子树上的一个节点，移动到了另一棵子树上。

?

---

什么时候旋转？

当左子树树高超过右子树树高两倍的时候，进行右旋。简记：左太高，右旋。

进行右旋的场景:

当插入10时，100的左子树过高，于是将50节点进行右旋转，从而降低左子树的高度。

?

当右子树树高超过左子树树高两倍的时候，进行左旋。简记：右太高，左旋。

进行左旋的场景:

当插入180时，100的右子树过高，于是将150节点进行左旋转，从而降低右子树的高度。

?

---

什么时候变色？

当满足以下条件时：

1. 当前节点是红色。
2. 父节点与叔节点都是红色。

进行变色：

1. 爷节点变成红色（如果是根节点，最终会变回成黑色）。
2. 父节点、叔节点变成黑色。

如图，插入节点50后，导致100、400都变了色。