Főoldal > TAMOP 4.2.5 Pályázat könyvei > Könyvek > Természettudományok > Matematika

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

Beágyazás
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).

Adatstruktúrák és algoritmusok
Bevezetés
1.1. A tárgyról
1.2. Alapvető fogalmak, definíciók
1.3. Feladatok
1.4. Az absztrakt adat és adattípus
1.5. Az algoritmus fogalma
1.6. Az algoritmus megadási módja: a pszeudokód és a folyamatábra.
1.7. Az algoritmus jellemző vonásai (tulajdonságai)
1.8. Az algoritmus hatékonysági jellemzői
1.9. A növekedési rend fogalma, az ordo szimbolika
1.10. A Fibonacci számok
1.11. A rekurzív egyenletek és a mester tétel
1.12. Feladatok
Számelméleti algoritmusok
2.1. Alapfogalmak
2.2. A legnagyobb közös osztó
2.3. A bináris legnagyobb közös osztó algoritmus
2.4. Az euklideszi és a kibővített euklideszi algoritmus
2.5. A lineáris kongruencia egyenlet
2.6. Az RSA-algoritmus
2.7. Feladatok
Elemi dinamikus halmazok
3.1. A tömb adatstruktúra
3.2. A láncolt lista (mutatós és tömbös implementáció)
3.3. A verem és az objektum lefoglalás/felszabadítás
3.4. A sor
3.5. Feladatok
Keresés, rendezés egyszerű struktúrában (tömb)
4.1. Keresés
4.2. Rendezés
4.3. Feladatok
Fák
5.1. Gráfelméleti fogalmak, jelölések
5.2. Bináris kereső fák
5.3. Bináris kereső fa inorder bejárása
5.4. Bináris kereső fa műveletek
5.5. Piros-fekete fák
5.6. AVL-fák
5.7. 2-3-fák
5.8. B-fák
5.9. Feladatok
Gráfelméleti algoritmusok
6.1. A szélességi keresés
6.2. A mélységi keresés
6.3. Minimális feszítőfa
6.4. Legrövidebb utak
6.5. Adott csúcsból induló legrövidebb utak
6.6. Legrövidebb utak minden csúcspárra
6.7. Gráfok tranzitív lezártja
6.8. Feladatok
Dinamikus programozás
7.1. Feladatok
NP-teljesség
Mellékletek
9.1. Az ASCII karakterkészlet