BPC-ALD - Skripta_rev2019_2

c)  Vyhledávání  skončilo  v uzlu  u  s  prvkem  c,  přičemž  x>c  a  přitom  uzel  u  už  nemá 

pravého  následníka.  V tom  případě  přidáme  ke  stromu  pravého  následníka  uzlu u,  do 
kterého nový prvek x vložíme. 

Do AVL stromu 
lze snadno přidat 
nový prvek. 

− 66 − 

Příklad. Do následujícího AVL stromu 

máme vložit prvek 1. Následující obrázek ukazuje postup. 

Prvek 1 bude přidán jako nový levý následník uzlu s prvkem 4. 

2.  Obnovení vyvážení uzlu 

Po přidání může dojít k porušení vyvážení AVL stromu. V těchto případech je nutné vhodnou 
transformací  strom  znovu  vyvážit.  Jako  první  je  nutné  najít  uzel,  u  něhož  došlo  porušení 
podmínky, že výška jeho podstromů se může lišit nejvýše o 1. Proces hledání začneme u uzlu, 
do  kterého  jsme  přidali  následníka,  a  pokračujeme  směrem  nahoru  až  buďto  najdeme 
nevyvážený uzel anebo skončíme v kořenu a tím zjistíme, že strom i po přidání zůstal vyvážený. 

U  nevyváženého  uzlu  mohou  nastat  dva  základní  případy.  První  z nich  ukazuje  následující 
obrázek. Nevyvážený uzel je v něm označen B. 

Transformace  uvedená  na  předchozím  obrázku  se  používá  rovněž  i  pro  zrcadlový  případ 
(otočený kolem svislé osy). 

Příklad. Do následujícího AVL stromu 

Vyvážení AVL 
stromu obnovíme 
lokálními 
transformace 
tvaru stromu. 

− 67 − 

přidáme prvek 20. 

Po  přidání  začneme  směrem  nahoru  procházet  uzly  počínaje  uzlem  18,  do  kterého  byl  přidán 
následník s novým prvkem. Uzel 18 je vyvážený, uzel 15 je vyvážený, uzel 9 ale není vyvážený, 
neboť  jeho  levý  podstrom  má  výšku  1,  zatímco  pravý  podstrom  má  výšku  3.  Viditelně  jde  o 
zrcadlový případ již popsaného typu nevyvážení a k jeho odstranění použijeme transformaci u 
tohoto nevyvážení uvedenou.