544.左旋
对 x 进行左旋,意味着,将“x 的右孩子”设为“x 的父亲节点”;即,将 x 变成了一个左节点(x成了为 z 的左孩子)!。 因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”。
LEFT-ROTATE(T, x)
y ← right[x] // 前提:这里假设 x 的右孩子为 y。下面开始正式操作
right[x] ← left[y] // 将 “y 的左孩子” 设为 “x 的右孩子”,即 将β设为 x 的右孩子
p[left[y]] ← x // 将 “x” 设为 “y 的左孩子的父亲”,即 将β的父亲设为 x
p[y] ← p[x] // 将 “x 的父亲” 设为 “y 的父亲”
if p[x] = nil[T]
then root[T] ← y // 情况 1:如果 “x 的父亲” 是空节点,则将 y 设为根节点
else if x = left[p[x]]
then left[p[x]] ← y // 情况 2:如果 x 是它父节点的左孩子,则将 y 设为“x 的父节点
的左孩子”
else right[p[x]] ← y // 情况 3:(x 是它父节点的右孩子) 将 y 设为“x 的父节点的右孩
子”
left[y] ← x // 将 “x” 设为 “y 的左孩子”
p[x] ← y // 将 “x 的父节点” 设为 “y”