情况一:如果 z 没有孩子结点,直接删除, z 的父结点指向 z 的指针置为NIL。如图(a)所示。
情况二:如果 z 只有一个孩子结点,将这个孩子结点提升到 z 的位置,z 的父结点指向 z 的指针改为指向这个孩子结点。如图(b)所示。
情况三:如果 z 有两个孩子结点,找出 z 的后继 y ,让 y 占据 z 的位置, z 的右子树变为 y 的右子树,z 的左子树变为 y 的左子树。由于 y 是 z 的后继,所以 y 不可能有左孩子。
如果 y 是 z 的右孩子,用 y 替换 z 。
如果 y 在 z 的右子树中且 y 不是 z 的右孩子,先用 y 的右孩子结点替换 y ,然后用 y 替换 z 。
下面具体分情况讨论。
情况一:如果 z 没有孩子结点,直接删除。再插入 z 后, T1 与 T3 可能相同也可能不相同。
如果删除 z 后仍为AVL树,不需要进行旋转调整,再插入 z 后, z 还在原来位置,此时 T3 与 T1 相同。
如果删除 z 后仍为AVL树不平衡,需要进行旋转调整,此时AVL树结构发生变化,子树根结点发生变化,重新插入 z 的路径发生变化,插入后 z 所在子树不需要进行旋转调整,推理过程如下:删除 z 前最下面叶结点的深度为 2 , z 的深度为 1 , z 的父结点深度为 0 ,删除 z 后进行调整, z 的父结点和另一侧叶结点深度相同均为 1 ,再插入 z ,此时 z 的深度为 2 ,原先最下面叶结点深度为 1 ,符合AVL树性质,不需要进行旋转调整。此时 T3 与 T1 不相同。
情况二:如果 z 只有一个孩子结点,将这个孩子结点提升到 z 的位置,z 的父结点指向 z 的指针改为指向这个孩子结点。
如果删除 z 后仍为AVL树且左右高度差为 0 ,不需要进行旋转调整,再重新插入 z 后, z 变为叶结点。T1 与 T3 一定不相同。
如果删除 z 后仍为AVL树且左右高度差为 1 且 z 的父结点位于较高的一侧,再重新插入 z 后,仍为AVL树,不需要进行旋转调整, z 变为叶结点。T1 与 T3 一定不相同。
如果删除 z 后仍为AVL树且左右高度差为 1 且 z 的父结点位于较低的一侧,再重新插入 z 后,AVL树不平衡,需要进行旋转调整,调整后 T1 与 T3 可能相同。
登录后提交答案
暂无评论,来抢沙发