BPC-ALD - Skripta_rev2019_2

Druhý případ nevyvážení ukazuje následující obrázek. Nevyvážený uzel je v něm označen C. 

− 68 − 

Tento  typ  transformace  platí  ještě  pro  variantu  uvedeného  případu,  kdy  místo  podstromu  2 
dojde k prodloužení podstromu 3 a rovněž pro zrcadlové případy. 

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

přidáme prvek 10. 

Budeme-li  nyní  procházet  uzly  od  uzlu  s prvkem  8  směrem  nahoru,  zjistíme,  že  nevyvážený 
uzel je až kořen. Jde o případ nevyvážení, který jsme právě uvedli, a použijeme transformaci u 
tohoto případu uvedenou. 

− 69 − 

Postup odebrání prvku 

Operace odebrání prvku z AVL stromu zahrnuje jeho odstranění, případné přesuny k zaplnění 
nelistových volných uzlů až po dosažení volného listu, který zrušíme a následně ověříme, zda 
nedošlo k narušení vyvážení stromu, a pokud ano, strom znovu vyvážíme. 

1.  Odebrání prvku 

Označme  odebíraný  prvek  x.  Provedeme  jeho  vyhledání  ve  stromu.  Použijeme  k tomu  běžný 
algoritmus pro vyhledání. Ten může skončit třemi způsoby: 

a)  Prvek x nebyl ve stromu nalezen - není co odebrat, protože prvek x ve stromu není. 

b)  Prvek x byl nalezen v listovém uzlu. V tom případě list s tímto prvkem zrušíme. 

c)  Prvek x byl nalezen v uzlu u, který není listem. Prvek x z uzlu u odstraníme a na volné 

místo  v uzlu  přesuneme  buďto  největší  (a  zároveň  nejpravější)  prvek  z jeho  levého 
podstromu  anebo  nejmenší  (nejlevější)  prvek  z jeho  pravého  podstromu.  Pokud  uzel, 
z kterého  jsme  prvek  přesunuli,  je  list,  tak  tento  list  zrušíme,  jinak  na  tento  uzel 
aplikujeme stejný postup. Opakováním tohoto postupu na nelistové uzly se dříve nebo 
později dostaneme k listu, který následně zrušíme.