对于平衡二叉树的操作应对与考试只需要模拟出过程即可,且他的过程和插入的平衡方法一样,不一样的只是对于平衡因子的计算上。接下来我将给出方法
①删除结点(方法同“二叉排序树”)
②一路向北找到最小不平衡子树,找不到就完结撒花
③找最小不平衡子树下,“个头”最高的儿子、孙子
④根据孙子的位置,调整平衡(LL/RR/LR/RL)
⑤如果不平衡向上传导,继续②
具体的讲解看接下来几个例子
平衡二叉树的删除操作具体步骤:
①删除结点(方法同“二叉排序树”)
• 若删除的结点是叶子,直接删。
• 若删除的结点只有一个子树,用子树顶替删除位置
• 若删除的结点有两棵子树,用前驱(或后继)结点
顶替,并转换为对前驱(或后继)结点的删除。
②一路向北找到最小不平衡子树,找不到就完结撒花
③找最小不平衡子树下,“个头”最高的儿子、孙子
④根据孙子的位置,调整平衡(LL/RR/LR/RL)
⑤如果不平衡向上传导,继续②
例一
这里可以看到删除9的话平很行不会被破坏,此时就只需要直接删除9就好了。
例二
①删除结点(方法同“二叉排序树”)
• 若删除的结点是叶子,直接删。
• 若删除的结点只有一个子树,用子树顶替删除位置
• 若删除的结点有两棵子树,用前驱(或后继)结点
顶替,并转换为对前驱(或后继)结点的删除。
②一路向北找到最小不平衡子树,找不到就完结撒花
③找最小不平衡子树下,“个头”最高的儿子、孙子
④根据孙子的位置,调整平衡(LL/RR/LR/RL)
⑤如果不平衡向上传导,继续②
可以看出删除55以后平衡因子被破坏掉了
找最高的儿子和孙子找出他们的相对位置,像这里就是RR
接着就采用插入对于RR的处理方法就好
例三
不平衡了
找最高的儿子和孙子
RL型的处理方法
例四
红框的位置就是例三
第一次处理过后
显然还是不平衡的
⑤如果不平衡向上传导,继续②
• 对最小不平衡子树的旋转可能导致树变矮,从而导
致上层祖先不平衡(不平衡向上传递)
例五
①删除结点(方法同“二叉排序树”)
• 若删除的结点是叶子,直接删。
• 若删除的结点只有一个子树,用子树顶替删除位置
• 若删除的结点有两棵子树,用前驱(或后继)结点
顶替,并转换为对前驱(或后继)结点的删除。
先看采取前驱的操作
例6