AVL Tree Lab

Tags:

• Generics

Categories:

• Lab

  less than a minute  

Introduction

Problem 1

Label the following BST with AVL balance factors. Is this a properly balanced AVL tree?

Problem 2

Show how the AVL tree below changes when the following operations are applied (in order).

• insert(B)
• insert(A)
• insert(F)
• insert(E)`

Start with this tree:

Problem 3

Imagine that 1,000,000 ($\approx{2^{20}}$ ) keys are added to an initially empty AVL tree. Which of the following could be the height of the resulting tree? (Recall that, for any binary tree, $h(n) \ge \lfloor log_2 n \rfloor$, and for an AVL tree: $h(n) \lt 1.44 log_2 (n+2) - .328$ )

• 10
• 15
• 20
• 25
• 50
• 100
• 1000
• 1000000

Problem 4

Consider the following sorting algorithm:

TreeSort(array)
    -- Insert all items from the provided array into an initially 
       empty AVL tree.
    -- Perform an in-order traversal of the tree, copying all items
       back into the provided array.

• What is the worst-case big-$\Theta$ running time of this algorithm?

• Is it in-place?

• Is it stable?

Lab Submission

If you are in class, please submit a copy of your sheet to canvas (just take a picture). If you are not in class, you must submit a scanned sheet with the answers to the questions by the due date.