Vyvážené stromy
Podle přednášky z
Programování II 19. 3. 2007:
Dokonale vyvážené stromy
Počet vrcholů v levém a pravém podstromu každého vrcholu se liší nejvýše o 1.
Adelson-Velskij, Landis / AVL-stromy
Výška levého a pravého podstromu každého vrcholu se liší nejvýše o 1.
- Nejhorší AVL-strom (chce to trochu představivosti, v závorkách je vždy levý a pak pravý syn, nebo tečky, pokud synové chybí):
- (..)
- (().)
- ( (.()) () )
- ( 2. 3. )
- ( 3. 4. )
...
- Tomu se říká Fibonacciho stromy.
- Z toho: výška AVL-stromu ≤ ~ 1.45 * výška dokonale vyváženého stromu
- Proto se v praxi používají místo dokonale vyvážených.
- Vyvažování: pomocí rotací
- najde se vrchol, kde je porušená vyváženost
- provede se rotace nebo dvojrotace (dvojrotaci lze složit ze dvou rotací)
- (na přednášce byly příklady, ale asi nemá cenu je překreslovat a popisovat)
- Přidávání vrcholů
- jako normálně do binárního vyhledávacího stromu a pak se musí vyvažovat
- fígl:
- do vrcholu se přidá balance factor = výška pravého – výška levého z {-1, 0, 1}
- rekurzivní funkce pro přidání vrcholu vrací změnu výšky stromu, do nějž byl vrchol přidán
- podle toho se aktualizuje balance factor, a pokud je mimo {-1, 0, 1}, musíme vyvažovat
- Mazání vrcholů
- je třeba rotovat nejvýše jednou (opět se propaguje odspoda, dokud nenarazíme na problém)
http://neil.brown.name/blog/AVL