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

K EY T ERMS

AVL tree 966
balance factor

right-heavy 966

966 RL rotation 967

left-heavy 966
LL rotation 967
LR rotation 967
perfectly balanced tree

rotation 966
RR rotation 967
well-balanced tree

966

966

C HAPTER S UMMARY
1.

An AVL tree is a well-balanced binary tree. In an AVL tree, the difference between the
heights of two subtrees for every node is 0 or 1 .

2.

The process for inserting or deleting an element in an AVL tree is the same as in a regu-
lar binary search tree. The difference is that you may have to rebalance the tree after an
insertion or deletion operation.

3.

Imbalances in the tree caused by insertions and deletions are rebalanced through subtree
rotations at the node of the imbalance.

4.

The process of rebalancing a node is called a rotation . There are four possible rotations:
LL rotation , LR rotation , RR rotation , and RL rotation .

5.

The height of an AVL tree is O (log n ). Therefore, the time complexities for the search ,
insert , and delete methods are O (log n ).

Q UIZ

Answer the quiz for this chapter online at www.cs.armstrong.edu/liang/intro10e/quiz.html .

P ROGRAMMING E XERCISES
*26.1

( Display AVL tree graphically ) Write a program that displays an AVL tree along
with its balance factor for each node.

26.2

( Compare performance ) Write a test program that randomly generates 500,000
numbers and inserts them into a BST , reshuffles the 500,000 numbers and per-
forms a search, and reshuffles the numbers again before deleting them from
the tree. Write another test program that does the same thing for an AVLTree .
Compare the execution times of these two programs.

***26.3

( AVL tree animation ) Write a program that animates the AVL tree insert ,
delete , and search methods, as shown in Figure 26.1.

**26.4

( Parent reference for BST ) Suppose that the TreeNode class defined in BST con-
tains a reference to the node's parent, as shown in Programming Exercise 25.15.
Implement the AVLTree class to support this change. Write a test program that
adds numbers 1 , 2 , . . . , 100 to the tree and displays the paths for all leaf nodes.

**26.5

( The k th smallest element ) You can find the k th smallest element in a BST in
O ( n ) time from an inorder iterator. For an AVL tree, you can find it in O (log n )
time. To achieve this, add a new data field named size in AVLTreeNode to
store the number of nodes in the subtree rooted at this node. Note that the size of