Implementing the delete Method

Deleting an element from an AVL tree is the same as deleting it from a BST, except that the tree may need to be rebalanced. As discussed in Section, Deleting Elements from a BST, to delete an element from a binary tree, the algorithm first locates the node that contains the element. Let current point to the node that contains the element in the binary tree and parent point to the parent of the current node. The current node may be a left child or a right child of the parent node.
Two cases arise when deleting an element.

Case 1: The current node does not have a left child, as shown in Figure below (a). To delete the current node, simply connect the parent node with the right child of the current node, as shown in Figure below (b). The height of the nodes along the path from the parent node up to the root may have decreased. To ensure that the tree is balanced, invoke

balancePath(parent.element);

Case 2: The current node has a left child. Let rightMost point to the node that contains the largest element in the left subtree of the current node and parentOfRightMost point to the parent node of the rightMost node, as shown in Figure below (a). The rightMost node cannot have a right child but it may have a left child. Replace the element value in the current node with the one in the rightMost node, connect the parentOfRightMost node with the left child of the rightMost node, and delete the rightMost node, as shown in Figure below (b).

The height of the nodes along the path from parentOfRightMost up to the root may have decreased. To ensure that the tree is balanced, invoke

balancePath(parentOfRightMost);

The above is the detailed content of Implementing the delete Method. For more information, please follow other related articles on the PHP Chinese website!