8. gyakorlat
Szintfolytonos bejárás
A bináris fa csúcsait a mélységük szerinti sorrendben látogatjuk meg, egy szinten belül balról jobbra
Bejárás: queue használata
Műveletigény: \(\Theta \; n\) (ahol \(n\) a csúcsok száma)
Bináris keresőfák
Tetszőleges csúcs kulcsánál a bal részfájában minden csúcs kulcsa kisebb, a jobb részfájában minden csúcs kulcsa nagyobb
- Keresőfa: Csupa különböző elemet tartalmaz, nem engedi meg az egyenlőséget.
- Rendezőfa: Megengedi az egyenlőséget.
Alapműveletei
- Keresés:
search(t, k)(t: fa, k: elem) - Beszúrás:
insert(t, k)(t: fa, k: elem) - Minimum-kiválasztás:
min(t)(t: fa) - Minimum törlése:
remMin(t, minp)(t: fa, minp: minimum elem pointere) - Törlés:
del(t, k)(t: fa, k: elem)