Asymptotic running time insertion and searching in AVL

Question

I am learning about AVL trees. AVL trees are Binary Search Trees that balance themselves through rotations. Because they are balanced, the query time is O(log n). But the order in which the entries are added is also important to avoid the worst-case O(log n) rotations per insertion.

What is the asymptotic running time of:

(a) adding n entries with consecutive keys in an AVL tree (the time to insert all, not each of them)

b) searching for a key that is not in the tree.

What I understand is this height is O(log N), so insertion into an AVL tree has a worst case O(log N). Searching an AVL tree is completely unchanged from BST's, and so also takes time proportional to the height of the tree, making O(log N).

Is it correct?

Answer 1

Insertion in an AVL requires at most one rotation not O(log n) rotations( two if you count the double rotations individually). Asymptotically the order of insertion does not matter since a rotation takes constant time.

a) with n insertion the cost = n*(cost of finding the proper place to insert+actual creation and insertion of node +rotation if needed)=n*( O(log n)+O(1)+O(1))=O(n log n)

b) searching for an element is O(log n) since the tree is balanced

c) deleting a single element requires at most O(log n) rotations so the complexity of deletion is also O(log n)