如图,红黑树的左右旋转是为什么呢?

image
如图情况四为什么要先左旋P之后变成情况五,然后再进行右旋G呢?直接右旋G节点,然后变色不也能保证红黑树的性质吗?

阅读 3.2k
1 个回答

因为要保证旋转之后每条路径上的黑节点个数不变,情况四右旋之后你怎么修改节点的颜色都会破坏某条红黑树性质。如果p变黑,g变红,旋转之后n是g的左节点,也是红色的。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题