题33
题目
【2021 统考真题】给定平衡二叉树如下图所示, 插入关键字 23 后, 根中的关键字是 ( )
A. 16
B. 20
C. 23
D. 25
分析
题24中有说明平衡二叉树的旋转操作
解
D
关键字 23 的插入位置为 25 的左孩子, 此时破坏了平衡的性质, 需要对平衡二叉树进行调整。
最小不平衡子树就是该树本身, 插入位置在根结点的右子树的左子树上, 因此需要进行 RL 旋转, RL 旋转过程如下图所示, 旋转完成后根结点的关键字为 25 , 所以选 D。