1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: AVL tree using 2 balance

  1. Oct 24, 2011 #1
    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?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted