算法-avl平衡二叉树的删除节点算法

WP主题讨论 WP主题讨论 主题:1013 回复:2239

算法-avl平衡二叉树的删除节点算法

虐人心 发布于 2017-04-30 字数 166 浏览 1137 回复 1

请描述avl平衡二叉树的删除节点的完整算法的详细步骤。
在网上搜了一些算法,发现对删除描述的都不太完整,有一些还有明显的漏洞。
求一个完整严谨高效的算法。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(1

清晨说ぺ晚安 2017-10-12 1 楼

删除平衡二叉树节点一般都遵循删除二叉查找树节点的方法,只不过多了一个rebalance的步骤。
1.假设待删除节点为assume节点,首先找到要删除的节点,称为real节点。若assume至多只有一个孩子,则real节点就为assume节点本身,否则real为assume的前驱或后继节点。
2.删除real节点,记录此时real节点是其父节点的左孩子还是右孩子,保存在balance中。假设real节点的父节点为P,此时P的平衡因子肯定会变化,需要根据情况来做不同处理,代码大致如下:

//移除的是根节点
if(P == NULL) {
//...
}
else {
do {
//如果删除的是子树高度较高的一边,则父节点恢复平衡
if(P->m_nBalance == nBalance) {
P->m_nBalance = 0;
//如果为根节点则退出
if(P == m_pRoot)
break;
}
//如果父节点原本是完全平衡的,则调整父节点平衡因子
else if(P->m_nBalance == 0) {
P->m_nBalance = -nBalance;
break;
}
//如果删除的是子树高度较矮的一边,则父节点失去平衡,需要Rebalance
else {
//须分情况处理
if(RebalanceNode(P))
break;

    P = P->m_pParent;
    }
    //迭代处理当前节点的父节点,直到根节点
if(P->m_pParent == NULL)
        break;

nBalance = 1;
    if(P->IsLeftChild())
    nBalance = -1;

P = P->m_pParent;
} while(true);

}

3.rebalance的过程。称平衡因子被破坏的节点为toRebalance,其子树高度较高一则的孩子节点为pivot。此时有三种可能的情况:
toRebalance的平衡因子与pivot相同,
t(++)
/
p(+)
/
h (h+1)
toRebalance的平衡因子与pivot相反,
t(++)
/
p(-)
/
(h+1) h
pivot平衡因子为0,
t(++)
/
p(0)
/
(h) (h)

此时只需要根据树的一般旋转规则来处理就可以了,同时记录好每个节点平衡因子。这里有一个需要注意的地方是,前两种情况删除节点并调整后父节点的高度会变化,所以需要迭代处理其父节点。后一种情况删除并调整后,父节点的高度并没有变化,可以看做调整完成,这也是上面代码中Rebalance返回bool值的原因。
4.比较assume和real节点,若不同则将real的值拷贝到assume中。
完整的代码就不列出来了,上述的描述如有错误或不清楚的地方麻烦指正,谢谢。