从 AVL 树中删除元素与从 BST 中删除元素相同,只是树可能需要重新平衡。正如从 BST 中删除元素一节中讨论的,要从二叉树中删除元素,算法首先找到包含该元素的节点。让current指向二叉树中包含该元素的节点,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).
从parentOfRightMost到根的路径上的节点高度可能会减小。为了确保树是平衡的,调用
balancePath(parentOfRightMost);
以上就是实现删除方法的详细内容,更多请关注php中文网其它相关文章!
91资源网站长-冰晨2024-08-27 17:15
发表在:【账号直充】爱奇艺黄金VIP会员『1个月』官方直充丨立即到账丨24小时全天秒单!不错不错,价格比官方便宜
91资源网站长-冰晨2024-08-27 16:15
发表在:2022零基础Java入门视频课程不错,学习一下