1) In the context of binary search trees, what is the worst case running time for the remove operation?

A) O(1)

B) O(log N)

C) O(N)

D) O(N log N)

2)

Which of the following four pictures corresponds to the state of the AVL tree shown below after one single rotation towards rebalancing the tree has been completed (even if a double rotation is needed to completely rebalance the tree, what does it look like after the first single rotation in the double rotation)?

Note: Make sure the answer you select corresponds to the diagram you choose. Blackboard does not center-align the radio buttons with the images, so you may need to count from the top to make sure you have clicked the correct button.

A) (SEE BELOW)

B) (SEE BELOW)

C) (SEE BELOW)

D) (SEE BELOW)

3) In the context of binary search trees, what is the average case running time for the add operation?

A) O(1)

B) O(log N)

C) O(N)

D) O(N log N)

16 24 20