16｜平衡二叉树（AVL）：节点删除后的平衡性调整
王健伟
你好，我是王健伟。
上节课我们了解了什么是平衡二叉树，也详细讲解了插入一个新的节点后如何保持该树仍旧是一颗平衡二叉树。本节课我将继续与你分享在删除一个平衡二叉树中的节点后如何保持平衡的话题。
平衡二叉树删除某个节点的操作与二叉查找树删除某个节点的操作非常类似，但删除操作同样会使平衡二叉树失去平衡性。一旦因为删除某个节点导致平衡二叉树失衡，那么也要通过旋转使其恢复为平衡二叉树。删除操作的平衡性调整的实现代码有一定的复杂性，请你认真学习。我们先从删除过程的操作步骤开始说起。
删除过程的三个步骤
具体的删除过程可以分为三个主要步骤。
步骤一，在平衡二叉树中查找要删除的节点。
步骤二，针对所要删除的节点的子节点个数不同，分别处理几类情况。
要删除的节点是叶子节点，则直接把该节点删除并将指向该被删除节点的父节点的相应孩子指针设置为空。
要删除的节点有左子树或右子树（单分支节点），则把该节点删除并更新指向该被删除节点的父节点的相应孩子指针，让该指针指向要删除节点的非空的子节点（节点替换）。
要删除的节点左子树和右子树都不为空，则这里存在三种情况：找到这个要删除节点的左子树的最右下节点，也可以找这个要删除节点右子树的最左下节点；将该节点的值替换到要删除的节点上；把刚刚找到的那个最右下节点删除。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文详细介绍了平衡二叉树（AVL）删除节点后的平衡性调整过程。首先讲解了删除节点的三个主要步骤，包括查找要删除的节点、处理不同情况下的节点删除操作以及平衡性调整。在平衡性调整部分，文章详细讲解了不同情况下的旋转操作，并通过示意图展示了平衡性调整后的结果。此外，文章还提供了一个复杂的节点删除范例，展示了需要两次平衡性调整才能使二叉树恢复平衡的情况。文章内容详实，适合对平衡二叉树操作感兴趣的读者阅读学习。文章还提供了实现代码和课后思考问题，帮助读者更好地理解和应用所学知识。整体而言，本文内容丰富，涵盖了平衡二叉树删除节点后的平衡性调整的方方面面，对读者进行了全面而深入的讲解。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(1)
- 最新
- 精选
Tiger
老师您好，在处理被删除节点既有左子树又有右子树的情况时，您的代码的第67至第73行的ifelse语句是不是应该改为 if(parent != nullptr) { if(parent->leftChild == ptmp) { q = ptmp->leftChild; parent->leftChild = q; } else { q = ptmp->leftChild; parent->rightChild = q; } }2023-07-23归属地：北京
收起评论