Week 5: AVL Trees Flashcards
1
Q
What ais the time complexity of the following methods for Binary Search Trees?
A
2
Q
What is an AVL tree?
A
3
Q
What is the maximum height of an AVL tree?
A
4
Q
To rebalance an AVL tree, we always…
A
5
Q
What are the following rotations?
RR
LL
RL
LR
What does the fix for each look like?
A
6
Q
If an AVL tree becomes unbalances due to an INSERTION…
A
7
Q
What is the algorithm for
putAVL(r, k, data)
A
8
Q
Example of rebalancing a tree
A
9
Q
When both a single and double rotation can be applied to an unbalanced subtree…
A
10
Q
If the tree becomes unbalanced due to a
removal…
A
11
Q
What is the algorithm for
removeAVL(r, k)
A
12
Q
For AVL trees:
The data structure takes how much space?
A single rotation takes how much time?
get() takes how much time?
put() takes how much time?
remove() takes how much time?
A
13
Q
Another example of
putAVL()
A
