AVL Tree Lab
Categories:
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.