Proving AVL Tree Height using -2 to 2 Balance Factor

[ducks]

Homework Statement

An avl tree typically balances with a balance factor of -1, 1, 0.

What if the tree allows -2,-1,,0,1, 2 as a balance factor. Prove or disprove that the height of the tree is logarithmic to the number of nodes O(logn)

Homework Equations

Normal balanced AVL tree everyone uses is h=O(logn)

The Attempt at a Solution

I constructed several diagrams. Little hard to draw but i have root + 2 nodes going down a left path.

log(3) = 1.584963 Actual height: 2

Another 3 nodes down left path, 1 down right path, 1 root

log(5) = 2.32 Actual height: 3

Adding one more node down left side then balancing to a 2 balance factor:

log(8) = 4 Actual height: 4The O(logn) is failing to get over the real height. Could I use this as an argument to disprove this? Where big O notation being the upper bound, should at least be above the real height?

I carried it out a few more trees and it seems to be about 22-35% off the real height. Am I still running in O(logn) time? I can't come up with another run time to say : No, its not Logn, its ____

Any suggestions?

 

[KataKoniK]

Hello,

Thank you for your post. I would like to offer my perspective on this topic. First of all, let's clarify the definition of O(logn) time complexity. This means that the time it takes for an algorithm to run increases logarithmically with the size of the input (in this case, the number of nodes in the AVL tree).

In the case of AVL trees, the normal balance factor range of -1, 1, 0 guarantees that the height of the tree remains O(logn). This is because the rotations and rebalancing operations that are performed when a node is inserted or deleted maintain the balance of the tree. However, when we allow a wider range of balance factors, such as -2, -1, 0, 1, 2, the height of the tree may not remain O(logn).

As you have demonstrated in your examples, the height of the tree actually increases when we allow a wider range of balance factors. This means that the time it takes for operations on the tree, such as searching and insertion, will also increase. Therefore, we cannot say that the time complexity for these operations is O(logn) anymore.

In conclusion, I would say that you have successfully disproved the statement that the height of the tree is logarithmic to the number of nodes when a wider range of balance factors is allowed. This means that we need to use a different time complexity to analyze the performance of operations on these types of AVL trees. I would suggest further research and experimentation to determine the exact time complexity for these operations.

I hope this helps. Keep up the good work!



Scientist