---------- Exam/Review Questions ----------

1] Who are the two Russians who developed AVL trees? __________________________________________

2] In what year did Adekson-Velskii & Landis discover AVL tress? __________________________________

3] AVL Search is of order ____________________ {N / Log N / N Log N} time.

4] AVL Insertion is of order ____________________ {N / Log N / N Log N} time

5] AVL Deletion is of order ____________________ {N / Log N / N Log N} time

6] _______ {T/F} AVL Trees are balanced.

7]
_______ {T/F} AVL Trees are logarithmically balanced.

8] An AVL Tree is a binary tree with the additional balance property that, for
any node in the tree, the

height of the left and right subtrees can differ by at most _____

9] _______ {T/F} An empty tree is not height balanced.

10 ] In AVL Trees, _______ shall denote the left subtree and _______shall denote the right subtree.

11] A non empty binary tree is HEIGHT BALANCED if and only if [List Two Conditions]

____________________________________________________________

____________________________________________________________

12]
The BALANCE FACTOR of a node T in a
binary tree` bf(T) = h-L - ____`

13] The BALANCE FACTOR of a node T in a
binary tree` bf(T) = ___________`

`14]
Although the four rotations have various names, the four names used for these
rotations in our class are:`

`_____________________________________
_______________________________________`

`_____________________________________
_______________________________________`

15] _______ {T/F} AVL trees must be completely constructed with these four rotations in order to work!

16] _______ {T/F} As long as the starting tree is bananced, the AVL four rotations may be used to maintain balance.

17] _______ {T/F} AVL Trees work well for both unique and non-unique keys.

18] When A = ________ or A = ________, it is time to rotate the AVL Tree.

19] When A = ________ and B = _______, it is time to do a Rotate - Right.

20]
On a separate sheet of paper, place an "A" in the top right corner.
Create/sketch an AVL Tree with the following unique primary keys:

Redraw the tree after each insertion. Label A, B, N?C. Write the balance factors
for all.

Data 60, 55, 50,
45, 40, 35, 30, 25, 20, 15, 10, 5

Label A, B, and N/C as is appropriate. Write in the balance
factors. Your Output must be in the following
format!

`
________` `
|__40__| 0 <-- N` ` `

`
________` `
|__40__| +1 ` `
.` `
________` `
|__20__| 0 <-- ` `N`

`
________` `
|__40__| +2 <--
A` `
.` `
________` `
|__20__| +1 <--
B` `
.` `
________` `
|__10__| +0 <--
N `

** Rotate-Right
Required! A = 2. B = 1.**

`
________` `
|__20__| +0 <--
B` `
.
.` `
________
________` `
|__10__| +0 <--
B-L
|__40__| +0 <--A`