从 AVL 树中删除元素与从 BST 中删除元素相同，只是树可能需要重新平衡。正如从 BST 中删除元素一节中讨论的，要从二叉树中删除元素，算法首先找到包含该元素的节点。让cur%ign%ignore_a_1%re_a_1%nt指向二叉树中包含该元素的节点，parent指向current节点的父节点。 当前节点可能是父节点的左子节点或右子节点。
删除元素时会出现两种情况。
情况1：current节点没有左子节点，如下图(a)所示。要删除 current 节点，只需将 parent 节点与 current 节点的右子节点连接起来即可，如下图 (b) 所示。从 parent 节点到 root 的路径上的节点高度可能会减小。为了确保树是平衡的，调用
balancePath(parent.element);
情况 2：当前节点有左子节点。令rightMost指向current节点左子树中包含最大元素的节点，parentOfRightMost指向rightMost节点的父节点，如下图（a）所示。 rightMost 节点不能有右子节点，但可以有左子节点。将current节点中的元素值替换为rightMost节点中的元素值，将parentOfRightMost节点与rightMost节点的左子节点连接，并删除rightMost节点，如下图所示(b).
6种实现进度条的方法
6种实现进度条的方法
23 查看详情
从parentOfRightMost到根的路径上的节点高度可能会减小。为了确保树是平衡的，调用
balancePath(parentOfRightMost);
以上就是实现删除方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/828242.html
微信扫一扫 
支付宝扫一扫 
