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