AVL TREES - Introduction to Java Programming: Comprehensive Version - page 972

26.6 Implementing the delete Method
Deleting an element from an AVL tree is the same as deleing it from a BST, except that
the tree may need to be rebalanced.

Key
Point

As discussed in Section 25.3, 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 25.10a. To delete
the current node, simply connect the parent node with the right child of the current
node, as shown in Figure 25.10b.
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); // Defined in Listing 26.1

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 25.12a. 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 25.12b.
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); // Defined in Listing 26.1

26.11

✓ ✓

For the AVL tree in Figure 26.6a, show the new AVL tree after deleting element
107 . What rotation do you perform in order to rebalance the tree? Which node was
unbalanced?

Check

Point

26.12

For the AVL tree in Figure 26.6a, show the new AVL tree after deleting element
60 . What rotation do you perform in order to rebalance the tree? Which node was
unbalanced?

26.13

For the AVL tree in Figure 26.6a, show the new AVL tree after deleting element 55 . What
rotation did you perform in order to rebalance the tree? Which node was unbalanced?

26.14

For the AVL tree in Figure 26.6b, show the new AVL tree after deleting elements 67
and 87 . What rotation did you perform in order to rebalance the tree? Which node
was unbalanced?

26.7 The AVLTree Class
The AVLTree class extends the BST class to override the insert and delete
methods to rebalance the tree if necessary.

Key
Point

Listing 26.3 gives the complete source code for the AVLTree class.

L ISTING 26.3

AVLTree.java
1 public class AVLTree<E extends Comparable<E>> extends BST<E> {
2

/** Create an empty AVL tree */

3 public AVLTree() {

no-arg constructor