BPC-ALD - Skripta_rev2019_2

Počet srovnání potřebný k nalezení prvku je závislý na délce cesty od kořene k danému prvku. 
Maximální délka cesty je dána výškou stromu. V tomto ohledu je optimálním řešením vyvážený 
binární vyhledávací strom, který svou logaritmickou závislostí výšky stromu na počtu uzlů ve 
stromu  zajišťuje  i  logaritmickou  složitost  vyhledávání 

Θ(log(n)).  Nicméně  ve  vyváženém 

binárním  vyhledávacím  stromu  je  poměrně  složité  provádět  operace  přidání  nebo  odebrání 
prvku, neboť přidání prvku reprezentuje přidání uzlu na určité místo ve stromu a odebrání prvku 
reprezentuje odebrání uzlu z určitého místa ve stromu. U obou těchto operacích se musí při nich 
provést  přestavba určité části stromu tak, aby strom po nich byl opět vyvážený. A to je časově 
značně náročné. Proto se v praxi používají AVL stromy, které mají sice nižší stupeň vyvážení a 
tudíž vyžadují o něco delší čas pro vyhledávání, ale na druhé straně operace přidání a odebraní 
prvku a následné obnovení vyvážení probíhají u nich mnohem rychleji. 

4.3.1  AVL stromy 

AVL stromy jsou binární vyhledávací stromy, u nichž je zajištěna taková míra vyváženosti, že 
na  jedné  straně  poskytuje  operaci  vyhledávání  dobrou  složitost  a  na  druhé  straně  umožňuje 
poměrně rychle obnovit vyvážení stromu po přidání nebo odebrání prvku ze stromu. Je to tedy 
určitý kompromis mezi vyvážeností a obtížností operací přidání a odebrání prvku. 

Vyváženost v AVL stromu je zajištěna podmínkou, že pro každý uzel u stromu musí platit, že 
rozdíl  mezi  výškou  jeho  levého  podstromu  a  výškou  jeho  pravého  podstromu  je  nejvýše  1. 
Přitom  výškou  podstromu  zde  rozumíme  maximum  ze  vzdáleností  od  uzlu  u  k uzlům 
podstromu, tedy vzdálenost mezi uzlem u a uzly, které jsou úplně naspodu podstromu. Pokud 
uzel nemá daného následníka (levého, pravého), je výška tohoto podstromu 0.