在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A ,并已知A 的左孩子的平衡因子为0 右孩子的平衡因子为1,则应作( )型调整以使其平衡。 A、LL B、LR C、RL D、RR
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
平衡因子:指一个结点的左子树高度减去右子树高度的差值(平衡范围-1~1,即是绝对值下的0~1)。
当插入一个结点后若使得某个结点的平衡因子变为2或-2,那么该结点不平衡。
最低不平衡结点:指在插入或删除操作后,从新插入(或删除)的结点开始,沿着路径向上查找,第一个不满足平衡条件的结点就是最低不平衡结点。
我的理解:
题给已知条件:平衡情况下A的左子树平衡因子为0,右子树平衡因子为1,插入新节点造成不平衡情况下A是最低的不平衡结点。
一般情况下,平衡因子 = 左子树高度 - 右子树高度
根据已知条件分析可得A结点的左子树的左右子树高度相等,A结点的右子树的左子树比右子树高1。
由于新节点的插入导致A不平衡了,而A结点的右子树的左子树更高,说明新插入的结点是插入到了A结点的右子树的左子树中,即RL型。
参考答案:C 由题意可知,A的平...
登录后提交答案