Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

5.2. Bináris kereső fák

5.2. Bináris kereső fák

5.10. Definíció. A bináris kereső fa

A bináris kereső fa egy bináris fa, amely rendelkezik az alábbi bináris kereső fa tulajdonsággal:

Legyen a bináris kereső fa tetszőleges csúcsa.

Ha az baloldali részfájában van, akkor .

Ha az jobboldali részfájában van, akkor .

A jellemző műveletek bináris kereső fában:

KERES, MINIMUM, MAXIMUM, ELŐZŐ, KÖVETKEZŐ,BESZÚR, TÖRÖL.

A műveletek általában a fa magasságával függenek össze, amely lehet , de lehet is (ahol a kulcsok száma a fában).