BPC-ALD - Skripta_rev2019_2

2.  Obnovení vyvážení uzlu 

Po odstranění listu může dojít k porušení vyvážení AVL stromu. Opět projdeme uzly směrem 
nahoru  počínaje  předchůdcem  odstraněného  listu  a  budeme  ověřovat,  zda  u  některého  z nich 
není  porušena  podmínka  vyváženosti  AVL  stromu.  Pokud  ano,  obnovíme  vyvážení  některou 
z již uvedených transformací. 

Příklad. V následujícím AVL stromu 

V AVL stromu lze 
poměrně snadno i 
odstranit prvek.

− 70 − 

máme zrušit  prvek 23. Po jeho odebrání jsou následující dvě možnosti, jak prázdný uzel nyní 
zaplnit.  Buďto  prvkem  18,  který  je  největším  prvkem  v levém  podstromu,  anebo  prvkem  25, 
který je nejmenším prvek v pravém podstromu. 

Zvolíme  třeba  zaplnění  prvkem  18.  Po  přesunutí  prvku  18  máme  nyní  prázdný  jeho  původní 
uzel.  U  tohoto  uzlu  je  jen  jedna  možnost,  jak  ho  nyní  zaplnit,  a  to  prvkem  17  z jeho  levého 
podstromu. 

Po přesunutí prvku 17 máme nyní prázdný jeho původní uzel. Tento uzel je list, což znamená, 
že  ho  zrušíme.  Jak  je  zřejmé,  strom  zůstane  po  zrušení  uvedeného  listu  vyvážený  a  není 
zapotřebí žádná jeho transformace. 

Složitost operací 

Vezměme operaci vyhledávání. Pro uzel, ve kterém hledaný prvek není, potřebujeme jednu až 
dvě operace srovnání. První se zjistí, zda pokračovat v hledání v levém podstromu. Pokud ne, 
druhou se zjistí, zda pokračovat v hledání v pravém podstromu anebo zda prvek už je nalezen. 
Pro  vyhledání  prvku  potřebujeme  maximálně