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

4 }
5
6

/** Create an AVL tree from an array of objects */

7 public AVLTree(E[] objects) {

constructor

8 super (objects);

9 }
10
11 @Override /** Override createNewNode to create an AVLTreeNode */
12 protected AVLTreeNode<E> createNewNode(E e) { create AVL tree node

13 return new AVLTreeNode<E>(e);

14 }
15
16 @Override /** Insert an element and rebalance if necessary */
17 public boolean insert(E e) {
18 boolean successful = super .insert(e);
19 if (!successful)
20 return false ; // e is already in the tree
21 else {
22 balancePath(e); // Balance from e to the root if necessary
23 }
24
25

override insert

balance tree

return true ; // e is inserted

26 }
27
28 /** Update the height of a specified node */
29 private void updateHeight(AVLTreeNode<E> node) {
30 if (node.left == null && node.right == null ) // node is a leaf
31 node.height = 0 ;
32 else if (node.left == null ) // node has no left subtree
33 node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
34 else if (node.right == null ) // node has no right subtree
35 node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
36 else
37 node.height = 1 +
38 Math.max(((AVLTreeNode<E>)(node.right)).height,
39 ((AVLTreeNode<E>)(node.left)).height);
40 }
41
42 /** Balance the nodes in the path from the specified
43 * node to the root if necessary
44 */
45 private void balancePath(E e) {
46 java.util.ArrayList<TreeNode<E>> path = path(e);
47 for ( int i = path.size() - 1 ; i >= 0 ; i—-) {
48 AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
49 updateHeight(A);
50 AVLTreeNode<E> parentOfA = (A == root) ? null :
51 (AVLTreeNode<E>)(path.get(i - 1 ));
52
53 switch (balanceFactor(A)) {
54 case -2 :
55 if (balanceFactor((AVLTreeNode<E>)A.left) <= 0 ) {
56 balanceLL(A, parentOfA); // Perform LL rotation
57 }
58 else {
59 balanceLR(A, parentOfA); // Perform LR rotation
60 }
61

update node height

balance nodes
get path

consider a node
update height
get height

left-heavy

LL rotation

LR rotation

break ;

62 case +2 :

right-heavy