问答题
设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。【吉林大学1996四、2(7分)】
【正确答案】正确答案：树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡因子为零，说明根的左右子树等高(不一定是满二叉树)。沿左(或右)子树向下查找时，查找路径上所有结点的平衡因子皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。
【答案解析】