CODEWITHSUNDEEP
data-structurestreeavl-tree
Zephyr
Zephyr

Reputation: 1621

AVL tree worst case number of rotations during insertion and deletion

In an AVL tree, what is the worst case number of rotations during insertion and deletion of n elements ?

I think for insertion it should be O(n) and for deletion it should be O(nlogn). However, I am not that much sure about deletion .

Am I correct?

Upvotes: 2

Views: 6911

Answers (1)

karastojko
karastojko

Reputation: 1181

For both operations - inserting or deleting of a node x, there are cases that require rotations to be made on all nodes from x up to the root. Since height of a tree with n nodes is O(log n), the worst case for both operations take O(log n) rotations. For n insert/delete operations that gives O(n log n).

Upvotes: 2

Related Questions