- #1
ducks
- 8
- 0
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?