• Support PF! Buy your school textbooks, materials and every day products via PF Here!

AVL tree using 2 balance

  • Thread starter ducks
  • Start date
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?
 

Want to reply to this thread?

"AVL tree using 2 balance" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top