CODEWITHSUNDEEP
avl-treespace-complexity
Stevie
Stevie

Reputation: 396

What is the space complexity of an AVL tree insert?

Wouldn't AVL inserts be O(logn) space, because you need logn stack frames to do inserts? AVL tree itself is O(n) space and time to insert is O(logn)

Upvotes: 1

Views: 2155

Answers (1)

Saqib Naseeb
Saqib Naseeb

Reputation: 741

Due to the balancing property, the insertion, deletion and search operations take O(logn) in both the average and the worst cases. Therefore, AVL trees give us an edge over Binary Search Trees which have an O(n) time complexity in the worst case scenario.

The space complexity of an AVL tree is O(n) in both the average and the worst case.

Upvotes: 1

Related Questions