CODEWITHSUNDEEP
time-complexityavl-tree
MFave
MFave

Reputation: 1074

How is AVL tree insertion O(log n) when you need to recalculate balance factors up the tree after every insertion?

I'm implementing an AVL tree, and I'm trying to wrap my head around the time complexity of the adding process. It's my understanding that in order to achieve O(log n) you need to keep either balance or height state in tree nodes so that you don't have to recalculate them every time you need them (which may require a lot of additional tree traversal).

To solve this, I have a protocol that recursively "walks back up" a trail of parent pointers to the root, balancing if needed and setting heights along the way. This way, the addition algorithm kind of has a "capture" and "bubble" phase down and then back up the tree - like DOM events.

My question is: is this still technically O(log n) time? Technically, you only deal with divisions of half at every level in the tree, but you also need to travel down and then back up every time. What is the exact time complexity of this operation?

Upvotes: 1

Views: 3817

Answers (2)

Matt
Matt

Reputation: 1166

"Technically, you only deal with divisions of half at every level in the tree, but you also need to travel down and then back up every time. What is the exact time complexity of this operation?"

You've stated that you have to travel down and up every time.

So, we can say that your function is upper bounded by a runtime of 2 * logn.

It's clear that this is O(logn).

More specifically, we could assign the constant 3 and a starting value of 1, such that

2 * logn <= 3 * logn for all values of n >= 1.

This reduces to 2 <= 3, which is of course true.

The idea behind big-O is to understand the basic shape of the function that upper-bounds your function's runtime as the input size moves towards infinity - thus, we can drop the constant factor of 2.

Upvotes: 0

Clarence Kuo
Clarence Kuo

Reputation: 31

Assuming the height of the tree is H and the structure stays balanced during all operation. Then, as you mentioned, inserting a node will take O(H).

However, every time a node is added to the AVL tree, you need to update the height of the parents all the way up to the root node.

Since the tree is balanced, updating height will traverse only the linked-list like structure with the newly inserted node in the tail.

The height updating can be viewed equivalent to traversing a linked-list with length equals to H. Therefore, updating height will take another O(H) and the total update time is 2 * O(H), which is still O(log N) if we get rid of the constant factor.

Hope this makes sense to you.

Upvotes: 0

Related Questions