由元素序列（27,16,75,38,51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为 2 的结点）是（ ）。

A. 27 B. 38 C. 51 D. 75

平衡二叉树

[tag_link]

正确答案：D

按序列（27,16,75,38,51）依次插入构造平衡二叉树：

• 插入 27 和 16 后，树平衡。 >
• 插入 75 后，树仍平衡。 >
• 插入 38 后，各节点平衡因子绝对值均不超过 1，树平衡。 >
• 插入 51 后，节点 38 的平衡因子变为 -1（平衡），但节点 75 的左子树高度为 1、右子树高度为 -1（空），平衡因子计算为 1 - (-1) = 2，绝对值首次达到 2，成为不平衡节点。 > 继续向上检查，节点 27 的平衡因子也变为 -2，但节点 75 是离插入点 51 最近的不平衡节点，因此最小不平衡子树的根是 75。 >