实现删除方法

从 AVL 树中删除元素与从 BST 中删除元素相同，只是树可能需要重新平衡。正如从 BST 中删除元素一节中讨论的，要从二叉树中删除元素，算法首先找到包含该元素的节点。令 current 指向二叉树中包含该元素的节点，而 parent 指向 current 节点的父节点。 当前节点可能是父节点的左子节点或右子节点。
删除元素时会出现两种情况。

情况1：当前节点没有左子节点，如下图(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中文网其他相关文章！