AVL-strom

Z Wikipedie, otevřené encyklopedie

Ukázka ne-AVL stromu
Ukázka ne-AVL stromu

AVL strom je datová struktura pro uchovávání údajů a jejich vyhledávání. Pracuje v logaritmicky omezeném čase. Jedná se o samovyvažující se binární vyhledávací strom.

Jméno stromu pochází z iniciál jeho objevitelů. G.M. Adelson-Velsky a E.M. Landis popsali tuto strukturu v roce 1962 v článku „An algorithm for the organization of information“.


[editovat] Vlastnosti vrcholů AVL stromu

  • Vrchol má maximálně dva následníky (je to binární strom)
  • V levém podstromu vrcholu jsou pouze vrcholy s menší hodnotou klíče (je to binární vyhledávací strom)
  • V pravém podstromu vrcholu jsou pouze vrcholy s větší hodnotou klíče (je to vyhledávací strom)
  • Délka nejdelší větve levého a pravého podstromu se liší nejvýše o 1 (vyvážení AVL stromu)


Stejný strom poté, co byl vyvážen
Stejný strom poté, co byl vyvážen


[editovat] Vlastnosti AVL stromu

Hlavní vlastností AVL stromu je, že definice nedovoluje, aby strom zdegeneroval tj, zajišťuje vyváženost stromu. Pokud označíme i výšku stromu reprezentujícího množinu o velikosti n platí následující \frac {c_1}{\sqrt {5}}(\frac {1+ \sqrt {5}}{2})^{i+2} -1 < F_{i+2} - 1 <= n < 2^{i} -1, Kde Fi je i-té Fibonačiho číslo Z čehož plyne, že výška stromu je úměrná logaritmu velikosti reprezentované množiny.