题22
题目
Q:在下图所示的红黑树中插入结点 2 且染成红色后，则下一步应进行的操作是 ( ).
A. 左旋
B. 右旋
C. 变色
D. 无须调整
分析
A:插入结点是根结点，直接变黑
插入结点的叔叔是红色叔父爷变色，爷爷变插入结点
插入结点的叔叔是黑色，LL,RR,LR,RL旋转，然后变色
解
B
插入结点 2 且将其染成红色后违反不红红原则, 并且叔结点是黑色, 应进行 LL 旋转, 将结点 3 右旋旋转到结点 5 的位置, 结点 2 和结点 5 分别成为结点 3 的左、右孩子, 然后将结点 3 染成黑色, 结点 2 和结点 5 染成红色。因此, 下一步应进行右旋操作。