AVL vs Heaps

Question 1

What is the height of a binary heap?

Answer 1

Theta(log(n))

Question 2

How does Insertion work for a heap?

Answer 2

Insert at the next available leaf

Fix up until Heap Order property is upheld

Question 3

What is the complexity of Heap Insertion?

Answer 3

O(log(n))

Question 4

How does deleteMax for for a Heap?

Answer 4

Replace the root by the last leaf

FixDown

Question 5

What is the complexity of deleteMax

Answer 5

O(log(n))

Question 6

What is the height of a AVL tree?

Answer 6

Theta(log(n))

Question 7

What is the complexity of AVL Insert?

Answer 7

BSTInsert -> Theta(log(n))
Update heights above => Theta(log(n))
Rotate if needed => constant

Question 8

What is the complexity of AVLDelete

Answer 8

BSTDelete => Theta(log(n))
Updates heights above => Theta(log(n))
Rotate if needed => constant