calculating the time complexity of an AVL tree algorithm

Question

I'm looking to calulate the time complexity of the following algorithm. I have an AVL tree and a pair of two numbers (x,y) such that x<y. The algorithm's purpose is to print all numbers in the tree between x and y. x and y are definitly not in the tree.

My goal is to make an algorithm whose runtime is O(logn + k) such that k is the number of nodes between x and y and n is the total number of nodes in the tree.

my algorithm is this:

A function that receives x and y, starts from the root of the tree and goes like this:

if the current node is between x and y - print it and recursively call the left node with (x,current node value) and the right node with (current node value,y).

if the current node is smaller than x - call the right node recursivley with (x,y)

if the current node is bigger than y - call the left node recursivley with (x,y) The function stops when it reaches a leaf(node who has no other nodes attached to it). Does my function meet the runtime requirement?

What is the "current node" initially? Is it the root of the tree? — Curtis Fenner
– Curtis Fenner, Commented May 5, 2018 at 15:07
I am not an expert in theoretical runtime calculations. But your algo seems OK, I would do it the same way. What else could you do instead? — Heri
– Heri, Commented May 5, 2018 at 15:42
my other solution was to add a successor and predcessor(by inorder) fields to each node. then add x as node to the tree. find x's successor and prints all the successors from it all the way to y. then delete x from the tree. thing is it's more complex(each insertion to the tree is 3*logn instead of just logn) and the algo itself is 3*logn+k. This is one is easy to calculate so i know it works(and constants don't matter so it's fine) but if this solution meets the runtime reuqirements it's way more elegant and i'd rather use it — Nadav Matityahu
– Nadav Matityahu, Commented May 5, 2018 at 15:55

Gene · Accepted Answer · 2018-05-06 00:49:04Z

Yes it does. You can prove it by noting that your algorithm does nothing but visit nodes, and every node visit requires O(1) time. Each visit that discovers a value in the range can be "charged" to the O(k) part of the time bound.

But there are some visits - those that find nodes less than or greater than the range - that don't discover a value. These must be "charged" to the O(log n) part of the time bound.

The rest of the proof is to show that there are indeed no more than O(log n) such visits. The key is to show there can be at most a constant number c of them at each depth from the root. This requires some reasoning about the structure of BSTs. I'll let you have the fun of working out the details. There are O(log n) depths, so the number of these visits is O(c log n) = O(log n). qed

Additional note

Your algorithm needlessly shuffles the values. It's easy to tweak so that values are discovered in sorted order. Again I'll let you work out the details.

Collectives™ on Stack Overflow

calculating the time complexity of an AVL tree algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related