BPC-ALD - Skripta_rev2019_2

Potřebný čas: 2 hodiny 

v

− 63 − 

Binární  vyhledávání  popsané  v předchozí  části  má  velmi  příznivou  časovou  složitost.  Pokud 
bychom  měli  množinu  prvků,  v níž  velmi  často  a  intenzívně  hledáme,  pak  by  se  zřejmě 
vyplatilo je na začátku setřídit. Problém ovšem nastane, když tato množina se v průběhu času 
mění,  tj.  jsou  k ní  přidávány  nové  prvky  nebo  z  ní  naopak  některé  prvky  jsou  odebírány.  Už 
jsme  uvedli,  že  vkládání  prvků  doprostřed  pole  nebo  jejich  odebírání  zprostředka  pole  je 
poměrně  neefektivní  operace,  neboť  je  spojena  s přesuny  poměrné  značné  části  prvků  v poli. 
Pro  takovéto  případy  je  výhodnější  použít  vyhledávací  stromy.  Nejjednodušší  z nich  jsou 
binární vyhledávací stromy. 

Binární vyhledávací strom má každém uzlu jeden prvek (na obrázku je tento prvek označen c). 
Dále  platí,  že  prvek  v jeho  levém  následníku  a  rovněž  i  všechny  prvky  v  celém  levém 
podstromu (na obrázku podstrom A), který tímto následníkem začíná, jsou menší než prvek c. A 
naopak všechny prvky v pravém podstromu (na obrázku B) jsou větší než prvek c. 

Postup vyhledávání 

1.  Počáteční krok 

Uzel,  který  je  v daném  okamžiku  vyhledávání  aktuální,  budeme  označovat  u.  Na  začátku  jím 
bude kořen stromu. 

Hledaná hodnota nechť je x. 

2.  Průběžný krok 

Vezmeme  prvek  obsažený  v aktuálním  uzlu  u,  označme  ho  c,  a  provedeme  jeho  srovnání  
s hledanou hodnotou x: