BPC-ALD - Skripta_rev2019_2

Efektivnost 
vyhledávacího 
stromu závisí na 
jeho výšce. 

Úplně vyvážit 
binární 
vyhledávací 
strom je značně 
komplikované. 
Řešením jsou 
AVL stromy. 

− 65 − 

Na následujícím obrázku jsou dva AVL stromy výšky 3. Přitom v levém stromu mají všechny 
uzly  (vyjma  listů)  podstromy  rozdílné  délky,  čímž  takový  AVL  strom  má  při  dané  výšce 
nejmenší možný počet uzlů. Tedy AVL strom výšky 3 má nejméně 7 uzlů (nejvíce jich má 15). 

Průvodce studiem  

Název AVL nemá žádný mnemonický význam. Je odvozen od jmen svých tvůrců, 

kterými jsou dva rusové Adelson-Velskii aLandis.

Postup vyhledávání 

AVL  strom  je  z pohledu  vyhledávání  jen  specifickým  případem  obecného  binárního 
vyhledávacího stromu a tudíž algoritmus vyhledávání je stejný. 

Postup přidání prvku 

Operace přidání prvku do AVL znamená na příslušném  místě přidat do AVL stromu uzel, do 
kterého  nový  prvek  vložíme,  a  následně  ověřit,  zda  nedošlo  k narušení  vyvážení  stromu,  a 
pokud ano, strom znovu vyvážíme. 

1.  Přidání prvku 

Označme  přidávaný  prvek  x.  Provedeme  jeho  vyhledání  ve  stromu.  Použijeme  k tomu  již 
popsaný algoritmus vyhledávání. Ten může skončit třemi způsoby: 

a)  Prvek  x  byl  ve  stromu  nalezen.  Tím  přidávání  končí,  neboť  prvek  x  už  je  ve  stromu 

obsažen  a  u  vyhledávacích  stromů  se  nepředpokládá  vícenásobný  výskyt  stejného 
prvku. 

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

následníka. V tom případě přidáme ke stromu nový uzel jako levého následníka uzlu u a 
do něho nový prvek x vložíme.