4. [3 pts.] Please answer the following questions.

(a) What is the worst-case running time of inserting an element in an AVL tree? (Provide a tight big-Oh expression as a function of the number of elements n already in the AVL tree before the insertion.)

(b) The worst-case running time of removing an element in an AVL tree is

worse than the same as better than

that of the same operation in a splay tree.

(c) The worst-case running time of finding an element in a splay tree is

worse than the same as better than

that of the same operation in an AVL tree.