BPC-ALD - Skripta_rev2019_2

Nejprve srovnáme, zda je x<c: 

Pokud  ano,  pak  je  nutné  v hledání  pokračovat  v levém  podstromu.  Jako  nový  aktuální  uzel  u 
položíme  levého  následníka  současného  aktuálního  uzlu  a  znovu  provedem  krok  2.  Pokud 
současný  aktuální  uzel  levého  následníka  nemá,  vyhledávání  končí  -  hledaný  prvek  není  ve 
stromu obsažen. 

Pokud není x<c, srovnáme, zda je x>c: 

Pokud  ano,  je  nutné  v hledání  pokračovat  v pravém  podstromu.  Jako  nový  aktuální  uzel  u 
položíme pravého následníka současného aktuálního uzlu a opět provedeme krok 2. Pokud uzel 
pravého následníka nemá, vyhledávání končí, hledaný prvek není ve stromu obsažen. 

Pokud není x>c, zbývá už jen případ, že platí x=c, čímž jsme u konce, neboť prvek obsažený 
v současném aktuálním uzlu u je tím hledaným prvkem. 

Příklad. Mějme binární vyhledávací strom 

Pro případy, 
kdy hodnoty 
jsou průběžně 
přidávány nebo 
rušeny, máme 
vyhledávací 
stromy. 

má v každém

intenzivně

− 64 − 

A hledáme v něm hodnotu x=7. 

Na začátku aktuální uzel je kořen u=12. Srovnáme, zda je x<u. To platí (7<12) a nový aktuální 
uzel bude levý následník u=5. A opět srovnáme, zda x<u. To nyní neplatí a proto srovnáme, zda 
je x>u. To platí (7>5) a nový aktuální uzel bude pravý následník u=8. A znovu srovnáme, zda je 
x<u.  To platí (7<8) a nový aktuální uzel bude levý následník u=7. A opět srovnáme, zda x<u. 
To  neplatí  a  proto  srovnáme,  zda  je  x>u.  Ani  to  neplatí,  čímž  je  hledaný  prvek  nalezen,  je 
v současném aktuálním uzlu. Celý postup ukazuje následující obrázek.