6.2. Keresés

A bináris fák egy speciális osztálya a bináris keresőfák. A definiáló tulajdonság a következő: legyen x és y a fa egy-egy olyan csúcsa, hogy az x az y őse. Ha y az x baloldali fájában található, akkor y.kulcs x.kulcs, míg ha a y az x jobboldali fájában található, akkor x.kulcs y.kulcs.

Egy adott elem keresése a következőképpen történik. A fa gyökérében kezdünk, és a keresett kulcsot összehasonlítjuk a gyökér kulcsával. Ha a kulcsok megegyeznek, kész vagyunk. Ha a keresett kulcs kisebb a gyökér kulcsánál, akkor a keresett elem a baloldali részfában található, ha egyáltalán szerepel a fában. Ellenkező esetben a jobboldali részfában kell keresni. A részfának is tekintjük a gyökerét, ennek kulcsát is összehasonlítjuk a keresett kulccsal, s ezt folytatjuk mindaddig, amíg rá nem találunk a kulcsra, vagy a keresett fa üres nem lesz. A Keres függvényt megírhatjuk rekurzív és iteratív formában is.

Function KERES(x,k)rekurzív változat 
Input: x a fa gyökerének címe, k a keresett csúcs 
Output: A keresett elem címe, illetve Nil 
1 if x == Nil or k == x.kulcs then 
2    return x 
3 endif
4 if k ≤ x.kulcs then 
5    Keres(x.bal,k) 
6 else 
7 Keres(x.jobb,k) 

Function KERES(x,k)iteratív változat 
Input: x a fa gyökerének címe, k a keresett csúcs 
Output: A keresett elem címe, illetve Nil 
1 while x != Nil and k != x.kulcs do 
2    if k ≤ x.kulcs then 
3       x = x.bal 
4    else 
5       x = x.jobb 
6    endif
7 endw 
8 return x 

Miután az adott csúcstól balra eső elemek kisebb kulccsal rendelkeznek, a leginkább balra található elem rendelkezik a minimális kulccsal.

Function MINIMUM(x) 
Input: x a fa gyökerének a címe 
Output: a minimális elemet tartalmazó csúcs címe 
1 while x.bal != Nil do 
2    x = x.bal 
3 endw
4 return x 

A keresés, a minimális, maximimális kulcs megkeresésének bonyolultsága a keresett elem magasságával arányos, ami a legrosszabb esetben O(n). Néha szükség van az előző és következő elem meghatározására. A fabejárásokkal lineáris bonyolultsággal megoldható a probléma, de létezik egyszerűbb megoldás is. Ha az adott elemnek van jobboldali részfája, akkor eme részfa minden elemének kulcsa nagyobb az x kulcsánál. Ezek közül kell a minimális, tehát ennek a részfának minimális elemére vagyunk kiváncsiak. Ellenkező esetben azt a legfiatalabb őst kell megkeresni, melynek baloldali részfájában szerepel ez az elem, azaz a bal mutatója mutat felé.