Question

关于算法导论红黑树旋转的问题。

左旋转第三行 p[left[y]] = x什么意思

Answer 1

这句的意思是把 y节点 的 左节点 的 父节点 设为 x节点.
建议看着下面那副图13-3理解,第一步是把y设为x的右儿子,第二步是把x的右儿子设为y的左儿子,这样完成了x节点的旋转,然后接下来处理y.首先判断y的左儿子是否存在,如果存在,由于y的左儿子的父节点已经改变了(第二步改变的),所以要改变y的左儿子的父指针,设为x.