Introduction To AVL Trees
  
Trinity University

 ---------- 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