由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为(46)。
【正确答案】 D
【答案解析】解析:平衡二叉树(AVL树)或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。二叉树结点的平衡因子(Balance Factor, BF)定义为该结点的左子树的深度减去其右子树的深度。平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。由元素序列(27,16,75,38,51)构造平衡二叉树的过程如下图所示,将元素51加入树中之前,二叉树保持平衡,加入结点51后,结点38的平衡因子由0变为-1,75所在结点的平衡因子由1变为2,27所在结点的平衡因子由-1变为-2。因此,75所在结点是离插入结点最近且平衡因子的绝对值为2的结点。