Úvod

Najčastejšou operáciou vykonávanou na binárnom prehľadávacom strome je vyhľadávanie kľúča uloženého v strome. Okrem operácie vyhľadávania Search podporujú binárne vyhľadávacie stromy aj operácie Minimum, Maximum, Successor a Predecessor. Tieto operácie sa všetky dajú vhodne implementovať tak, že čas ich behu je O(h), kde h je výška stromu.

^ TOP

Vyhľadávanie

Na vyhľadanie vrcholu s daným kľúčom sa používa procedúra Tree-Search. Ak máme kľúč k a ukazovateľ na koreň stromu, tak procedúra vráti ukazovateľ na vrchol s kľúčom k. Ak taký vrchol neexistuje, vráti nil.
Procedúra začína hľadanie v koreni a prehľadáva strom smerom dolu. Pri každom vrchole, na ktorý narazí, porovná hodnotu v tomto vrchole s hľadaným kľúčom k. Ak sa rovnajú, vrchol sa našiel a prehľadávanie skončí. Ak je k menšie ako hodnota vo vrchole, vyhľadávanie pokračuje v ľavom podstrome x. Symetricky, ak je k väčšie ako hodnota vo vrchole, pokračuje vyhľadávanie v pravom podstrome x. Uzly navštívené počas rekurzie tvoria cestu od koreňa k hľadanému vrcholu. Ten, ak existuje je v maximálnej hĺbke h a teda čas behu Tree-Search je O(h).

    Tree-Search(x,k)
    if (x = nil) or (k = key[x]) then
      return x
    if (k<key[x])
      then return Tree-Search(left[x],k)
      else return Tree-Search(right[x],k)  
      

Náhradou rekurzie za cyklus dostávame iteratívnu verziu procedúry, ktorá je na väčšine počítačov rýchlejšia. Je označená Iterative-Tree-Search.

    Iterative-Tree-Search(x,k)
    while (x = nil) and (k != key[x]) do
      if (k key[x])
      then x:=left[x]
      else x:=right[x]
    return x
      

^ TOP

Minimum a maximum

Prvok s najmenšou hodnotou kľúča sa z definície nachádza v liste „najviac vľavo“. Teda sa dá nájsť sledovaním ukazovateľov na ľavých synov, až kým nenarazíme na nil. Vlastnosť binárnych prehľadávacích stromov priamo zaručuje korektnosť algoritmu. Ak uzol x nemá ľavý podstrom, potom minimum podstromu s koreňom x je key[x]. Ak však má podstrom, najmenší prvok je možné nájsť v podstrome s koreňom v uzle left[x]. Nájdenie maxima v strome je analogické k nájdeniu minima. Obe procedúry majú časovú zložitosť O(h), kde h je výška daného stromu.

    Tree-Minimum(x)
    while (left[x] != nil) do
      x:=left[x]
    return x
      

^ TOP

Nasledovník a predchodca

Niekedy je potrebné nájsť pre daný uzol binárneho prehľadávacieho stromu jeho nasledovníka alebo predchodcu. Štruktúra binárnych prehľadávacích stromov toto umožňuje bez nutnosti porovnávať kľúče. Procedúra Tree-Successor vráti nasledovníka uzla x v strome, ak taký neexistuje, vráti hodnotu nil.
Kód procedúry je rozdelený na dva prípady. Ak je pravý podstrom uzla x neprázdny, potom je nasledovník uzla x vrchol s najmenšou hodnotou kľúča v tomto (pravom) podstrome. Tento zistíme použitím procedúry Tree-Minimum(right[x]). Ak je však pravý podstrom x prázdny (a x má nasledovníka y), potom je y najnižší predok x, ktorého ľavý syn je tiež predok x. Zjednodušene povedané, od x ideme hore, kým nenarazíme na vrchol, ktorý je ľavým synom svojho otca.
Na vizualizácii je zobrazený práve tento prípad.

    Tree-Successor(x)
    if (right[x] != nil) then
      return Tree-Minimum(right[x])
    y:=p[x]
    while (y != nil) and (x = right[y]) do
      x:=y
      y:=p[y]
    return y
      

^ TOP