545.右旋

对 x 进行右旋，意味着，将“x 的左孩子”设为“x 的父亲节点”；即，将 x 变成了一个右节点(x成了为 y 的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

 RIGHT-ROTATE(T, y) 
x ← left[y] // 前提：这里假设 y 的左孩子为 x。下面开始正式操作
left[y] ← right[x] // 将 “x 的右孩子” 设为 “y 的左孩子”，即 将β设为 y 的左孩子
p[right[x]] ← y // 将 “y” 设为 “x 的右孩子的父亲”，即 将β的父亲设为 y
p[x] ← p[y] // 将 “y 的父亲” 设为 “x 的父亲”
if p[y] = nil[T] 
then root[T] ← x // 情况 1：如果 “y 的父亲” 是空节点，则将 x 设为根节点
else if y = right[p[y]] 
 then right[p[y]] ← x // 情况 2：如果 y 是它父节点的右孩子，则将 x 设为“y 的父节
点的左孩子”
 else left[p[y]] ← x // 情况 3：(y 是它父节点的左孩子) 将 x 设为“y 的父节点的左孩
子”
right[x] ← y // 将 “y” 设为 “x 的右孩子”
p[y] ← x // 将 “y 的父节点” 设为 “x”