AVL-strom
Z Wikipedie, otevřené encyklopedie
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 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)
Tento článek o počítačích je pahýl. Můžete pomoci Wikipedii tím, že jej vhodně rozšíříte. |