(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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)

2. Relevant equations

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

3. 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: 4

The 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: AVL tree using 2 balance

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**