This content originally appeared on DEV Community and was authored by Paul Ngugi
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);
This content originally appeared on DEV Community and was authored by Paul Ngugi
Paul Ngugi | Sciencx (2024-07-24T20:09:30+00:00) Implementing the delete Method. Retrieved from https://www.scien.cx/2024/07/24/implementing-the-delete-method/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.