10-12

6.11

Tips: 分情况讨论

• ansRight.status = ok/rbr

• ansRight.status = brb

  • oldTree.color = black
  • oldTree.color = red

• otherwise

  • oldTree.leftSubtree.color = red
  • oldTree.leftSubtree.color = black

6.15

略

6.16

• (1) 右旋+左旋
• (2) 左旋
• (3) r = black, 左旋
• (4) s = black, p = red, 左旋

6.17

• (a) 错误
• (b) 错误

10-15

6.18

略

6.19

言之有理即可。(a) 简单的可以认为空间多两倍