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

238 // Replace the element in current by the element in rightMost
239 current.element = rightMost.element;
240
241 // Eliminate rightmost node
242 if (parentOfRightMost.right == rightMost)
243 parentOfRightMost.right = rightMost.left;
244 else
245 // Special case: parentOfRightMost is current
246 parentOfRightMost.left = rightMost.left;
247
248 // Balance the tree if necessary
249 balancePath(parentOfRightMost.element);
250 }
251
252 size—-;
253

balance nodes

return true ; // Element inserted

254 }
255
256 /** AVLTreeNode is TreeNode plus height */

257 protected static class AVLTreeNode<E extends Comparable<E>> inner AVLTreeNode class

258 extends BST.TreeNode<E> {

259 protected int height = 0 ; // New data field node height

260
261 public AVLTreeNode(E e) {

262 super (e);

263 }
264 }
265 }

The AVLTree class extends BST . Like the BST class, the AVLTree class has a no-arg
constructor that constructs an empty AVLTree (lines 3-4) and a constructor that creates an
initial AVLTree from an array of elements (lines 7-9).
The createNewNode() method defined in the BST class creates a TreeNode . This
method is overridden to return an AVLTreeNode (lines 12-14).
The insert method in AVLTree is overridden in lines 17-26. The method first invokes
the insert method in BST , then invokes balancePath(e) (line 22) to ensure that the tree
is balanced.
The balancePath method first gets the nodes on the path from the node that contains
element e to the root (line 46). For each node in the path, update its height (line 49), check its
balance factor (line 53), and perform appropriate rotations if necessary (lines 53-69).
Four methods for performing rotations are defined in lines 85-182. Each method is invoked
with two TreeNode arguments— A and parentOfA —to perform an appropriate rotation at
node A . How each rotation is performed is illustrated in Figures 26.2-26.5. After the rotation,
the heights of nodes A , B , and C are updated (lines 102, 129, 152, 179).
The delete method in AVLTree is overridden in lines 187-264. The method is the same
as the one implemented in the BST class, except that you have to rebalance the nodes after
deletion in two cases (lines 224, 249).

constructors

insert

balancePath

rotations

delete

26.15 Why is the createNewNode method defined protected?
26.16 When is the updateHeight method invoked? When is the balanceFactor method
invoked? When is the balancePath method invoked?
26.17 What are data fields in the AVLTree class?
26.18 In the insert and delete methods, once you have performed a rotation to balance
a node in the tree, is it possible that there are still unbalanced nodes?

✓ ✓

Check

Point