在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A ,并已知A 的左孩子的平衡因子为0 右孩子的平衡因子为1,则应作( )型调整以使其平衡。 A、LL B、LR C、RL D、RR
平衡因子:指一个结点的左子树高度减去右子树高度的差值(平衡范围-1~1,即是绝对值下的0~1)。
当插入一个结点后若使得某个结点的平衡因子变为2或-2,那么该结点不平衡。
最低不平衡结点:指在插入或删除操作后,从新插入(或删除)的结点开始,沿着路径向上查找,第一个不满足平衡条件的结点就是最低不平衡结点。
我的理解:
题给已知条件:平衡情况下A的左子树平衡因子为0,右子树平衡因子为1,插入新节点造成不平衡情况下A是最低的不平衡结点。
一般情况下,平衡因子 = 左子树高度 - 右子树高度
根据已知条件分析可得A结点的左子树的左右子树高度相等,A结点的右子树的左子树比右子树高1。
由于新节点的插入导致A不平衡了,而A结点的右子树的左子树更高,说明新插入的结点是插入到了A结点的右子树的左子树中,即RL型。
参考答案:C 由题意可知,A的平...
用户登录可进行刷题及查看答案
参考答案:C 由题意可知,A的平衡因子为1,又由于A的右孩子的平衡因子为1,左孩子的平衡因子为0,由此可知,A的右孩子上仅有右孩子,A的左孩子上无左右孩子,在平衡二叉树中插入一个结点后造成不平衡,说明插入结点只能插在A的右孩子的左孩子上,这种情形属于在右子树的左子树上插入结点的情形,即RL型。
登录后提交答案