User:TWiStErRob/Alga

A Wikipédiából, a szabad lexikonból.

Algoritmusok és adatszerkezetek I. IB304, vizsgakérdések
Az oldalt bárki szerkesztheti. Nem kell hozzá regisztráció. Kérlek te is segíts kitölteni a tételeket. Ha valami hibát veszel észre, azt javítsd ki, vagy ha nem tudod, akkor jelezd a végén levő Hibák-nál.
Az itt közölt anyagok nagyrészt a /pub-ban levő jegyzetekből vannak. Az algoritmusok vagy a Java kódok átíratai, vagy a WikiPedia-n és egyéb helyeket fellelt [pszeudó]kódok-ból lettek kialakítva. Kommentekkel próbáltam érthetőbbé tenni az anyagot, több-kevesebb sikerrel. Az ø minden esetben - ahol nincs más írva - a "nincs értelmezve"-t (fordított T) jelenti.
Semmilyen felelősséget nem vállok az oldalon található hibákból származó hátrányok miatt.
Papp Róbert
"Én, mint a pub-ban található anyag szerzője, egyébként hozzájárulok az ilyen felhasználáshoz."
Horváth Gyula

Gyorstalpaló a szerkesztéshez:


=1. szintű címsor=
==2. szintű címsor==
''dőlt betű''
'''vastag betű'''
'''''vastag dőlt betű'''''
;definíció
:bekezdés
::még beljebb kezdés
<pre>
kód
kód
<{per}pre>
#számos felsorolás
*jeles felsorolás

Tartalomjegyzék

[szerkesztés] Az O, Ω, Θ, o, ω jelölések definíciója √

[szerkesztés] Definíciók és magyarázatok

O(g(n))
{f(n) : (∃c, n0 ≥ 0)(∀n ≥ n0)(0 ≤ f(n) ≤ c*g(n))}
Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c*g(n) alatt van.
Ω(g(n))
{f(n) : (∃c, n0 ≥ 0)(∀n ≥ n0)(0 ≤ c*g(n) ≤ f(n))}
Azon f(n)függvények halmaza, amelyekhez létezik olyan c konstans és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c*g(n) felett van.
Θ(g(n))
{f(n) : (∃c1, c2, n0 ≥ 0)(∀n ≥ n0)(0 ≤ c1*g(n) ≤ f (n) ≤ c2*g(n))}
O és Ω együtt teljesül
Azon f(n) függvények halmaza, amelyekhez léteznek olyan c1, c2 konstansok és n0 kezdőindex, nemnegatív számok, hogy minden n-re, ami n0-nál nagyobb-egyenlő, az f(n) függvény c1*g(n) és c2*g(n) között fut.
o(g(n))
{f(n) : (∀c > 0)(∃n0 > 0)(∀n ≥ n0)(0 ≤ f(n) < c*g(n))}
O szigorítása
Azon f(n) függvények halmaza, amelyekre teljesül, hogy minden pozitív c konstanshoz létezik pozitív n0 kezdőindex, hogy minden n-re teljesül hogy a függvény szigorúan c * g(n) alatt van.
ω(g(n))
{f(n) : (∀c > 0)(∃n0 > 0)(∀n ≥ n0)(0 ≤ c*g(n) < f(n))}
Ω szigorítása
Azon f(n) függvények halmaza, amelyekre teljesül, hogy minden pozitív c konstanshoz létezik pozitív n0 kezdőindex, hogy minden n-re teljesül hogy a függvény szigorúan c * g(n) felett van.

[szerkesztés] Kiegészítés

O, Ω, Θ, o, ω tranzitív
f(n) = *(g(n)) ∧ g(n) = *(h(n)) ⇒ f(n) = *(h(n))
mégpedig a nagyobb n0-tól kezdődően
O, Ω, Θ reflexív
f(n) = *(f(n))
önmagában relációban áll, mivel az egyenlőség is megengedett
Θ szimmetrikus
f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n))
O, Ω, o, ω antiszimmetrikus
ha f(n) = *(g(n)) ∧ g(n) = *(f(n)) ⇒ f(n) = g(n)
tehát egyszerre, csak az egyik lehet kisebb, vagy nagyobb mint a másik (f és g közül)
f(n) = o*(g(n)) ⇔ g(n) = ω*(f(n))
a fenti képlet kifejezi, hogy az ordó és a theta jelölések egymás ellentettjei

[szerkesztés] A partíciószám kiszámításának rekurzív algoritmusa √

int Partíció(int n) {
        return Partíció2(n, n);
}
int Partíció2(int n, int k) {
        // 1-et csak egyféleképp lehet felbontani, és bármilyen számot 1-esekből csak 1 féleképp lehet felépíteni
        if (n == 1 || k == 1)
                return 1;
        // n-nél nagyobb partíciója nem lehet n-nek:
        // a n-nél kisebb számokat tartalmazó partíciók, és a csak n-et tartalmazó partíció
        if (k >= n)
                return Partíció2(n, n - 1) + 1;
        return
                // azon partíciók, amelybe nem vesszük bele a k-t
                Partíció2(n, k - 1) 
                // és azon partíciók, amelybe belevesszük a k-t
                + Partíció2(n - k, k);
}

[szerkesztés] VeremBol, VeremBe, SorBol, SorBa és a Prioritási sor adattípus SorBol, SorBa műveletek specifikációja √

Előtte Művelet Utána
{V = <a1, ..., an>} VeremBe(V, x) {V = <a1, ..., an, x>}
{0 < n ∧ V = <a1, ..., an>} VeremBől(V, x) {V = <a1, ..., an - 1> ∧ x = an}
{S = <a1, ..., an>} SorBa(S, x) {S = <a1, ..., an, x>}
{0 < n ∧ S = <a1, ..., an>} SorBól(S, x) {x = a1 ∧ S = <a2, ..., an>}
{P = {a1, ..., an}} PriSorBa(P, x) {P = Pre(P) ∪ {x}}
{P ≠ ø} PriSorBól(P, x) {x = min(Pre(P)) ∧ P = Pre(P) \ {x}}

[szerkesztés] A Halmaz adattípus specifikációja √

Nem biztos, hogy ez az!, Az ø itt üres halmazt jelent!

Értékhalmaz
Halmaz = { H : H ⊆ E}
Műveletek
H: Halmaz, x: E, I: Iterator
Előtte Művelet Utána
{Igaz} Létesít(H) {H = ø}
{H = H} Megszüntet(H) {Igaz}
{H = H} Üresít(H) {H = ø}
{H = {a1, ..., an}} Elemszám(H) {Elemszám = n}
{H = H} Eleme(H, x) {Eleme = x ∈ Pre(H)}
{H = H} Bővít(H, x) {H = Pre(H) ∪ {x}}
{H = H} Töröl(H, x) {H = Pre(H) \ {x}}
{H = H} IterKezd(H, I) {}
{I = I} IterAd(I, x) {}
{I = I} IterVege(I) {}

[szerkesztés] A Függvény adattípus Kiolvas, Modosit, Bovit és Torol műveleteinek specifikációja √

Java-ban java.util.ArrayList, C++-ban std::vector

Előtte Művelet Utána
{F = <a1, ..., ai, ..., an> ∧ 1 ≤ i ≤ n} Kiolvas(F, i, x) {x = ai ^ F = Pre(F)}
{F = <a1, ..., ai, ..., an> ∧ 1 ≤ i ≤ n} Módosít(F, i, x) {F = <a1, ..., x, ..., an>}
{F = <a1, ..., ai, ai+1, ..., an> ∧ 0 ≤ i ≤ n} Bővít(F, i, x) {F = <a1, ..., ai, x, ai+1, ..., an>}
{F = <a1, ..., ai-1, ai, ai+1, ..., an> ∧ 1 ≤ i ≤ n} Töröl(F, i) {F = <a1, ..., ai-1, ai+1, ..., an>}

[szerkesztés] A Reláció adattípus APar, KPar, ATorol, KTorol műveleteinek specifikációja √

Java-ban java.util.Map, C++-ban std::map, vagy ha több érték megengedett egy kulcshoz: java.util.Map<java.util.List>, std::multimap

Előtte Művelet Utána
{R = R} KPar(R, k) {KPar = {k : (k, a) ∈ Pre(R)} }
APar(R, a) {APar = {a : (k, a) ∈ Pre(R)} }
KTöröl(R, k) {R = Pre(R) \ {(k,a) : (k,a) ∈ Pre(R)} }
ATöröl(R, a)

[szerkesztés] Lánc és körlánc absztrakt adatszerkezetek definíciói √

[szerkesztés] Lánc

A = (M, R, Adat) lánc, ha R = {követ},
követ
M → M parciális függvény, amelyre teljesül:
(∃ fej ∈ M)(∀ x ∈ M)(∃! k ≥ 0)(x = követk(fej))
láncvég
Pontosan egy olyan c ∈ M cella van, amelyre követ(c) = ø (NULL).
Lánc hosszán az n számot értjük, mely a cellák számát adja meg.
Ha n > 0, akkor követn − 1(fej) = láncvég

[szerkesztés] Körlánc

A = (M, R, Adat) körlánc, ha R = {követ},
követ
M → M (totális) függvény, amelyre teljesül:
(∀x, y ∈ M)(∃k ≥ 0)(y = követk(x))
bármely x ∈ M-re az <x = x0, x1, ..., xn−1> sorozat, ahol xi = követ(xi−1), i = 1, ..., n − 1, az M halmaz elemeinek egy ciklikus permutációja.

[szerkesztés] A nem rendezett fa definíciói (bináris reláció, és apa függvény) √

[szerkesztés] Bináris reláció

A = (M, R, Adat) nem-rendezett fa, ha R = {r}, r ⊆ M × M bináris reláció, és van olyan g ∈ M, hogy a G = (M, r) irányított gráfban bármely x ∈ M-re pontosan egy g ~> x út vezet. g-t a fa gyökerének nevezzük.

[szerkesztés] Apa függvény

Minden nem-rendezett fa egyértelműen megadható egy olyan Apa : M → M parciális függvénnyel, amelyre teljesül a következő feltétel:
(∃ g ∈ M)((Apa(g) = ø) ∧ (∀x ∈ M)(∃!k ≥ 0)(Apak(x) = g))
Ha y = Apa(x), akkor azt mondjuk, hogy x apja y és y-nak fia x.
Az így megadott szerkezeti kapcsolat nem definiál rendezettséget adott x cella {y : Apa(y) = x} fiainak halmazán.

[szerkesztés] A rendezett fa absztrakt adatszerkezet definíciója fi függvényekkel √

Legyen A = (M, R, Adat) olyan absztrakt adatszerkezet, hogy R = {f}, f : M → (M ∪ {ø})*.
x ∈ M, f(x) = <y1, ..., yk>, yi ∈ M ∪ {ø}, i = 1, ..., k.
Minden i > 0 természetes számra definiáljuk az fi : M → M ∪ {ø} függvényt a következőképpen:
f_i(x) = \begin{cases} y_i, & \mbox{ha }f(x) = \left\langle y_1, ..., y_k\right\rangle \and i \le k; \\ \empty, & \mbox{ha }i > k; \end{cases}
Tehát fi(x) az x i-edik fiát adja. Ha fi(x) = ø, akkor hiányzik az i-edik fiú.
Az A adatszerkezetet fának nevezzük, ha van olyan g ∈ M, hogy teljesül az alábbi négy feltétel
  1. a gyökér nem fia egyetlen pontnak sem:
    (\forall x \in M)(\forall i)(g \ne f_i(x))
  2. minden, gyökértől különböző pont fia valamely pontnak:
    (\forall y \ne g \in M)(\exist x \in M)(\exist i)( f_i(x) = y)
  3. minden pontnak legfeljebb egy apja lehet:
    (\forall x, y \in M)(\forall i, j)(f_i(x) = f_j(y))(x = y \and i = j))
  4. minden pont elérhető a gyökérből:
    (\forall x \ne g \in M)(\exist i_1, ..., i_k)(x = f_{i_k} (... (f_{i_1} (g))))

[szerkesztés] Fa absztrakt adatszerkezet algebrai definíciója √

Legyen E tetszőleges adathalmaz. Az E-feletti fák Fa(E) halmaza az a legszűkebb halmaz, amelyre teljesül az alábbi három feltétel:

  • ø ∈ Fa(E), az E-feletti fák része az üres halmaz
  • (∀a ∈ E)a ∈ Fa(E), ha egy adat benne van az adathalmazban, akkor benne van az E-feletti fákban is
  • (∀a ∈ E)(t1, ..., tk ∈ Fa(E))(a(t1, ..., tk) ∈ Fa(E))

[szerkesztés] Általános absztrakt adatszerkezet definíciója √

Olyan A = (M, R, Adat) rendezett hármas, ahol
  1. M az absztrakt memóriahelyek, cellák halmaza.
  2. R = {r1, ..., rk} a cellák közötti szerkezeti kapcsolatok, ri : M → (M ∪ {ø})*
  3. Adat : M → E parciális függvény, a cellák adattartalma.
x ∈ M, r ∈ R és r(x) = <y1, ..., yi, ..., yk> esetén az x cella r kapcsolat szerinti szomszédai {y1, ..., yk}, yi pedig az x cella i-edik szomszédja.
Ha yi = ø, akkor azt mondjuk, hogy x-nek hiányzik az r szerinti i-edik szomszédja.

[szerkesztés] Különbségek a gráf és általános absztrakt adatszerkezetek között (nem anyag)

  1. A gráf csak egy szerkezeti kapcsolatot ad meg.
  2. Gráf esetén a szomszédok halmaza nem rendezett.
  3. Gráfban nem tudunk hiányzó kapcsolatot megadni.

[szerkesztés] Fa adatszerkezet kapcsolati tömb, kapcsolati lánc ábrázolásai √

[szerkesztés] Kapcsolati tömb

[szerkesztés] Statikus
struct FaPont {
        ElemTípus elem;
        FaPont* fiuk[MAXHOSSZ];
        int hossz;
}
Memóriaigény
n * (sizeof(ElemTipus) + MAXHOSSZ * sizeof(FaPont*) + sizeof(int))
Feltéve, hogy sizeof(FaPont*) = 4 és ElemTípus = int32: 4 * n * (MAXHOSSZ + 2)
Az ábrázolás előnye
Minden pont i-edik fia közvetlenül (konstans időben) elérhető.
Az ábrázolás hátránya
Statikus, azaz nem lehet konstans időben bővíteni és törölni.

[szerkesztés] Dinamikus (nem anyag)

Ha előre tudjuk a bizonyos pontok gyerekeinek számát, akkor dinamikus foglalással:

struct FaPont {
        ElemTípus elem;
        FaPont** fiuk;
        int hossz;
}
Memóriaigény
n * (\operatorname{sizeof}(ElemTipus) + \operatorname{sizeof}(int) + \operatorname{sizeof}(FaPont**)) + \operatorname{sizeof}(FaPont*) * \sum_{i = 1}^n {\operatorname{FiukSzama}(i)}
\sum_{i = 1}^n {\operatorname{FiukSzama}(i)} = n - 1, mivel minden gyereknek legfeljebb egy apja van (gyökérnek nincs).
Feltéve, hogy sizeof(T*) = 4 és ElemTípus = int32: 16 * n - 4
Az ábrázolás előnye
Minden pont i-edik fia közvetlenül (konstans időben) elérhető.
Az ábrázolás hátránya
Statikus, azaz nem lehet konstans időben bővíteni és törölni.

[szerkesztés] Kapcsolati lánc

struct FaPont {
        int n;
        struct kapcsolo {
                FaPont* gyerek;
                kapcsolo* kovetkezo;
        };
        kapcsolo* kapocs;
};
Memóriaigény
n * (sizeof(ElemTípus) + sizeof(kapcsolo*)) + (n - 1) * (sizeof(FaPont*) + sizeof(kapcsolo*))
Feltéve, hogy sizeof(T*) = 4 és ElemTípus = int32: 16 * n - 8

[szerkesztés] Fa adatszerkezet elsőfiú-testvér, elsőfiú-testvér-apa ábrázolásai √

[szerkesztés] Elsőfiú-testvér

struct Fa {
        ElemTípus adat;
        Fa* elsőfiú;
        Fa* testvér;
};
Memóriaigény
n * (sizeof(ElemTípus) + 2 * sizeof(Fa*))
Feltéve, hogy sizeof(Fa*) = 4 és ElemTípus = int32: 12 * n

[szerkesztés] Elsőfiú-testvér-apa

struct Fa {
        ElemTípus adat;
        Fa* elsőfiú;
        Fa* testvér;
        Fa* apa;
};
Memóriaigény
n * (sizeof(ElemTípus) + 3 * sizeof(Fa*))
Feltéve, hogy sizeof(Fa*) = 4 és ElemTípus = int32: 16 * n

[szerkesztés] Preorder rekurzív fabejáró algoritmus √

PreOrder(Fa fa, Művelet M) {
        M(fa);
        for(gyerek : fa.gyerekek)
                PreOrder(gyerek, M);
}

C++-os megvalósítás, elsőfiú-testvér ábrázolással:

struct FaPont {
        int adat;
        FaPont* elsőfiú;
        FaPont* testvér;
};
void PreOrder(FaPont* p, void(Művelet*)(FaPont*)) {
        if (p == NULL) return;
        Művelet(p);
        if (p->elsőfiú != NULL) // az if elhagyható, úgyis visszatér ha NULL-t kap
                PreOrder(p->elsőfiú, M);
        if (p->testvér != NULL) // az if elhagyható, úgyis visszatér ha NULL-t kap
                PreOrder(p->testvér, M);
}

[szerkesztés] Szintszerinti fabejáró algoritmus √

void SzintSzerint(Fa fa, Művelet M) {
        Sor<Fa> S;
        S.push(fa);
        while(!S.empty()) {
                Fa f = S.pop();
                M(f);
                for(gyerek : f.gyerekek)
                        S.push(gyerek);
        } 
}

[szerkesztés] Partíció probléma megoldása rekurziómemorizálással √

long Particio[][];
long Partíció(int n) {
        Particio = new long[n][n];
        return Partíció2(n,n);
}

long Partíció2(int n, int k){
        if (Particio[n][k] != 0) // Partíció2(n, k)-t már kiszámítottuk
                return Particio[n][k];
        long P_nk;
        if (k == 1 || n == 1)
                P_nk = 1;
        else if (k >= n)
                P_nk = P2(n, n - 1) + 1;
        else
                P_nk = P2(n, k - 1) + P2(n - k, k);
        Particio[n][k] = P_nk; //memorizálás
        return P_nk;
}

Algoritmust kommentezve lásd: Partíciószám rekurzív algoritmusa

[szerkesztés] Partíció probléma dinamikus programozási megoldása (táblázat-kitöltéssel) √

Az indexelés [oszlop, sor] szerint van. Csak a mátrix felső háromszögét tölti ki, a főátlót és fölötte.

long P(int N) {
        long tabla[1..N, 1..N];
        for (int i = 1; i <= N; i++) // első sor
                tabla[i, 1] = 1;
        for (int k = 2; k <= N; ki++) { // a k. sor kitöltése
                tabla[k, k] = tabla[k, k - 1] + 1; // P2(n, n) = P2(n, n - 1) + 1
                // P2(n, k) = T2[n, k] számítása
                for (int n = k + 1; n <= N; n++) {
                        // P2(n, k) = P2(n, n), ha k > n
                        int n1 = (n - k < k)? n - k : k; 
                        // P2(n, k) = P2(n, k - 1) + P2(n - k, k)
                        tabla[n, k] = tabla[n, k - 1] + tabla[n - k, n1]; 
                }
        }
        return T2[n][n];
}

Algoritmust kommentezve lásd: Partíciószám rekurzív algoritmusa

[szerkesztés] Pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések √

Probléma
Pénzváltás
Bemenet
P = {p1, ..., pn} pozitív egészek halmaza, és E pozitív egész szám.
Tehát P = pénzérmék, és E hogy mennyit szeretnénk kirakni P-ből
Kimenet
Olyan S ⊆ P, hogy \sum_{p \in S} = E.
Tehát azon érmék halmaza, melyek összege kiadja E-t
Megjegyzés
A pénzek tetszőleges címletek lehetnek, nem csak a szokásos 1, 2, 5 10, 20, stb., és minden pénz csak egyszer használható a felváltásban.
Először azt határozzuk meg, hogy van-e megoldás.
Tegyük fel, hogy
E = p_{i_1} + ... + p_{i_k}, i_1 < ... < i_k, tehát a megoldásban szereplő pénzérmék egy sorrendje
egy megoldása a feladatnak. Ekkor
E - p_{i_k} = p_{i_1} + ... + p_{i_{k - 1}}
megoldása lesz annak a feladatnak, amelynek bemenete a felváltandó E - p_{i_k} érték, és a felváltáshoz legfeljebb a első ik - 1
(p_{i_1} + ... + p_{i_{k - 1}}) pénzeket használhatjuk.
Részproblémákra bontás
Bontsuk részproblémákra a kiindulási problémát:
Minden (X, i)(1 ≤ X ≤ E, 1 ≤ i ≤ N) számpárra vegyük azt a részproblémát, hogy az X érték felváltható-e legfeljebb az első p1, ..., pi pénzzel. Jelölje V(X, i) az (X, i) részprobléma megoldását, ami logikai érték:
V(X, i) = IGAZ, ha az X összeg előállítható legfeljebb az első i pénzzel, egyébként HAMIS.
Összefüggések a részproblémák és megoldásaik között
  • V(X, i) = (X == pi), ha i = 1
egyetlen érménk van
  • ha megegyezik a kirakandó értékkel, akkor IGAZ
  • egyébként HAMIS
  • V(X, i) = V(X, i - 1) ∨ (X > pi) ∧ V(X - pi, i - 1) ha i > 1
több érménél
  • kirakható 1-gyel kevesebb érméből
  • vagy az érték nagyobb, mint az utolsó érme
  • és a vele csökkentett érték kirakható a maradék érmékből

[szerkesztés] Pénzváltási probléma egy megoldásának előállítása táblázat-kitöltéssel

int[] PénzVáltás(int E, int P[n]){
        boolean kirakhato[0..E][0..n];
        for (x = 1..E) // ???
                kirakhato[x, 0] = false;
        kirakhato[0, 0] = true; // semmit, érmék nélkül ki lehet rakni
        kirakhato[P[0], 0] = true; // ???
        for (i = 1..n-1)
                for (x = 1..E)
                        kirakhato[x, i] =
                // az aktuális érme kiadja az értéket:
                                P[i] == x 
                // vagy e nélkül az érme nélkül is ki lehet rakni:
                        ||      kirakhato[x, i - 1] 
                // vagy belevehető az P[i] érme, és belevéve kiarkható:
                        ||      x > P[i] && kirakhato[x - P[i], i - 1]; 
        int db = 0; x = E; i = n - 1;
        if (!kirakhato[E, n - 1]) return NULL;
        //megoldás visszafejtése érmék tömbbe
        int érmék[0..n] = 0;
        do {
                while (i >= 0 && kirakhato[x, i])
                        i--;
                érmék[db++] = ++i;
                x -= P[i]; // csökkenti a kirakandó értéket
        } while(x > 0); // amíg van mit kirakni
        return érmék; // 0..db-1 -ig lesz a megoldás, utána 0-k
}

[szerkesztés] Optimális pénzváltási probléma definíciója, részproblémák definíciója, a közöttük levő összefüggések

[szerkesztés] Optimális pénzváltási probléma megoldása táblázat-kitöltéssel (egy megoldást is előállítani)

[szerkesztés] Mátrixszorzás probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések

[szerkesztés] Hátizsák probléma definíciója, részproblémák definiálása, a közöttük levő összefüggések

[szerkesztés] Optimális bináris keresőfa definíciója, részproblémák definíciója, a közöttük levő összefüggések

[szerkesztés] Optimális bináris keresőfa megoldása táblázat-kitöltéssel (egy optimális bináris keresőfa előállítása)

[szerkesztés] Eseménykiválasztási probléma definíciója, megoldó algoritmus

[szerkesztés] Optimális prefix kód probléma definícója, Huffman-kód szerkesztő algoritmus

[szerkesztés] A Graf adattípus specifikációja √

Irányítatlan gráf
G = (V, E), E rendezetlen {a, b}, a, b ∈ V párok halmaza.
Irányított gráf
G = (V, E), E rendezett (a, b) párok halmaza; E ⊆ V × V.
Multigráf
G = (V, E, Ind, Érk), Ind, Érk : E → V; Ind(e) az e él induló, Érk(e) az érkező pontja.
Ki(G, p) = {q ∈ V : (p, q) ∈ E}
Be(G, p) = {q ∈ V : (q, p) ∈ E}
Értékhalmaz
Gráf = {G = (V, E) : V ⊆ PontTípus, E ⊆ V × V}
Műveletek
G : Gráf; p, p1, p2 : PontTípus; I : Iterator; irányított: boolean
Előtte Művelet Utána
{Igaz} Létesít(G, irányított?) {G = (ø, ø)}
{G = G} Megszüntet(G) {Igaz}
Üresít(G) {G = (ø, ø)}
Irányított(G) {¬Irányított(G) ⇒ (p, q) ∈ E ⇒ (q, p) ∈ E)}
PontokSzáma(G) {= |V|}
ÉlekSzáma(G) {= |E|}
KiFok(G, p) {= |Ki(G, p)|}
BeFok(G, p) {= |Be(G, p)|}
{G = (V, E)} PontBővít(G, p) {V = Pre(V) ∪ {p} ∧ E = Pre(E)}
{G = (V, E) ∧ p ∈ V} PontTöröl(G, p) {V = Pre(V) \ {p} ∧ E = Pre(E) \ ( {(p,q) : q ∈ Ki(G, p)} ∪ {(q, p) : q ∈ Be(G, p)} ) }
{G = (V, E), p1, p2 ∈ V} ÉlBővít(G, p1, p2) {E = Pre(E) ∪ {(p1, p2)} ∧ V = Pre(V)}
ÉlTöröl(G, p1, p2) {E = Pre(E) \ {(p1, p2)} ∧ V = Pre(V)}
VanÉl(G, p1, p2) {= (p1, p2) ∈ E ∧ E = Pre(E) ∧ V = Pre(V)}
{G = G} KiÉl(G, p) {= {q : VanÉl(p,q)}}
PIterator(G, I) {}
KiIterator(G, p)
ÉlIterator(G, I)

[szerkesztés] Kapcsolatmátrix, éllista gráf-reprezentációk, Tárigény, VanEl, Eliteráció, KiIteráció időigénye √

[szerkesztés] Kapcsolatmátrix (szomszédsági mátrix)

bool G[|V|, |V|];
(p, q) akkor és csak akkor éle a gráfnak, ha G[p, q] = true.
Címkézett (súlyozott) gráf ábrázolására: CímkeTípus G[|V|, |V|];
Címkézett gráf esetén választani kell egy nem ∈ dom(CímkeTípus) értéket, amely nem fordul elő semmilyen él címkéjeként.
(p, q) akkor és csak akkor éle a címkézett gráfnak, ha G[p, q] != nem, és a (p, q) él címkéjének értéke G[p, q].
Multi-gráf nem ábrázolható szomszédsági mátrix-al.

[szerkesztés] Éllista

[szerkesztés] Statikus
int G[|V|, |V|];
int KiFok[|V|];

[szerkesztés] Dinamikus
Lánc<int> G[|V|];

[szerkesztés] Általános
Az általános éllistás ábrázolás előnye, hogy a gráf pontjai tetszőleges (de rögzített) típusú értékek lehetnek.
Címkézett gráf esetén a ki-lánc (a vízszintes lánc) minden cellája a pont mellett egy címke értéket is tartalmaz.
template<typename PontTípus> struct GráfLánc {
        PontTípus címke;
        GráfLánc<PontTípus>* csat;
        Lánc<PontTípus> ki;
}

[szerkesztés] Igények (n = |V|, m = |E|, k = |Ki(G, p)|)

Reprezentáció Tárigény VanÉl Él-iteráció Ki-iteráció
Kapcsolati mátrix Θ(n2) Θ(1) Θ(n2) Θ(n)
Statikus éllista Tlr = O(n) Θ(m) Θ(k)
Dinamikus éllista Θ(n + m)
Általános éllista Tlr = O(n) + Θ(k)

[szerkesztés] Út, legrövidebb út definíciója súlyozott és súlyozatlan gráfokban √

Legyen G = (V,E) irányított (irányítatlan) gráf.

Út
p, q ∈ V-re egy p-ből q-ba vezető út G-ben, olyan π = <p0, p1, ..., pk> pontsorozat, ahol p = p0, q = pk és pi ≠ pj, ha i ≠ j, vagy p = q = p0, továbbá teljesül (∀i ∈ {1, ..., k})((pi-1, pi) ∈ E).
Olyan pontsorozat, melynek az eleje p, a vége q és minden eleme különböző vagy a kezdőpont megegyezik a végponttal (kör), továbbá az egymást követő éleket összekötő él benne van a gráfban.
Legrövidebb út
π = <p0, p1, ..., pk> = p ~> q út hossza
|π| = |p ~> q| = k
Ha G = (V, E, C) élei a C : E → R függvénnyel súlyozottak, akkor a p ~> q út hossza
\left|p \sim> q\right| = \sum_{i=1}^k C(p_{i - 1}, p_i).
p és q távolsága, p-ből q-ba vezető legrövidebb út hossza
\delta(p, q) = \begin{cases} \infty, & \mbox{ha nincs } p \sim> q; \\ \min(\left|\pi : p \sim> q\right|) & \forall \pi : p \sim> q;\end{cases}

[szerkesztés] Szélességi keresés algoritmusa √

szelkeres(Graf G, start) {
        Sor S;
        int apa[1..G.size()] = -1;
        int d[1..G.size()] = ∞;
        apa[start] = 0;
        d[start] = 0;
        S.push(start);
        while(!S.empty()) {
                u = S.pop();
                for(v : G[u].ki) {
                        if(apa[v] == -1) {
                                apa[v] = u;
                                d[v] = d[u] + 1;
                                S.push(v);
                        }
                }
        }
}

[szerkesztés] Mélységi keresés algoritmusa √

Gráfpontok 1-től indexelve
apa == -1
fa-gyökér
apa == 0
még nem bejárt pont
int idő;
void MélyKeres(Graf G) {
        d[1..G.size()];
        f[1..G.size()];
        apa[1..G.size()] = 0;
        idő = 0;
        for(p: G.V) if(!apa[p]) {
                apa[p] = -1;
                MélyBejár(G, p);
        }       
}
void MélyBejár(Graf G, int u) {
        d[u] = ++idő;
        for (v: G[u].ki) if(!apa[v]) {
                apa[v] = u;
                MélyBejár(G, v);
        }
        f[u] = ++idő;
}

[szerkesztés] "Színezős MélyKeresés"

int idő;
void MélyKeres(Graf G) {
        d[1..G.size()];
        f[1..G.size()];
        apa[1..G.size()] = -1;
        szín[1..G.size()] = fehér;
        idő = 0;
        for(p: G.V) if(szín[p] == fehér)
                MélyBejár(p);
}
void MélyBejár(Graf G, int u) {
        szín[p] = szürke;
        d[u] = ++idő;
        for (v: G[u].ki) if(szín[p] == fehér) {
                apa[v] = u;
                MélyBejár(v);
        }
        f[u] = ++idő;
        szín[p] = fekete;
}

[szerkesztés] Zárójelezési tétel

[szerkesztés] Élek osztályozása (faél, előre él, visszaél, keresztél definíciója) √

(u, v) ∈ V , (MFE = Mélységi Feszítő Erdő)
Faél
ha bekerül a MFE élei közé, azaz Apa(v) = u
u → v él vizsgálatakor Szín(v) = fehér
vagy másképp: ∃ u ~> v ∈ MFE út és |u ~> v| = 1
Visszaél
ha u leszármazottja v-nek a MFE-ben
u → v él vizsgálatakor Szín(v) = szürke
Előreél
ha v leszármazottja u-nak a MFE-ben és nem faél , azaz Apa(v) ≠ u;
u → v él vizsgálatakor Szín(v) = fekete és d(u) < d(v)
vagy másképp: ∃ u ~> v út és |u ~> v| > 1
Keresztél
Minden más esetben
u → v él vizsgálatakor Szín(v) = fekete és d(u) > d(v)

[szerkesztés] Topologikus rendezés definíciója, a körmentesség és a visszaélek kapcsolata

Topológikus rendezés
  • Irányított, körmentes gráf
  • Sorba kell rendezni az éleit úgy, hogy minden él előre mutasson

[szerkesztés] Topologikus rendezést megadó algoritmus

  1. Végrehajt egy mélységi keresés az f elhagyási időkkel
  2. amikor egy pont vizsgálatát befejezzük, akkor egy lánc elejére beszúrjuk
  3. A rendezés a lánc szerint Megj.: a pontok csökk. F érték szerint vannak

[szerkesztés] Erősen összefüggő komponensek, és a transzponált gráf definíciója √

u ~ v acsa, ha u ~> v és v ~> u
u akkor és csak akkor van egy komponensben v-vel, ha u-ból vezet út v-be és v-ből is vezet út u-ba
Egy u pontot tartalmazó erősen összefüggő komponens
C(u) = {v ∈ V : u ~ v}
A G = (V, E) gráf transzponáltja
GT = (V, ET), ahol ET = {(u, v) : (v, u) ∈ E}

[szerkesztés] Erősen összefüggő komponenseket előállító algoritmus √

Elvi algoritmus
  1. Számítsuk ki a Mélykeresés algoritmussal az f(u) elhagyási értékeket.
  2. A GT transzponált gráfra alkalmazzuk a Mélykeresés eljárást úgy, hogy a pontokra a Mélybejár eljárást f szerint csökkenő sorrendben hívjuk.
  3. A 2. pontban az egy mélységi feszítőfába kerülő pontok alkotnak egy erősen összefüggő komponenst.
  • bejárt: tömb, mely meghatározza, hogy egy pontban voltunk-e már
  • csökkenőF: verem, melyből csökkenő f szerint jönnek ki a pontok
Halmaz<Halmaz<int>> EÖK(Gráf G) {
        mélyKeres(G);
        return mélyKeresT(transzponál(G));
}

Gráf transzponál(Gráf G) {
        Gráf GT;
        for(él : G.élek)
                GT.bővít(él.be, él.ki);
        return GT;
}

bool bejárt[n];
Verem<int> csökkenőF;
void mélyBejár(Gráf G, int u) {
        bejárt[u] = true;
        for(v : G[u].ki)
                if(!bejárt[v]) mélyBejár(v);
        csökkenőF.push(u);
}
void mélyKeres(Gráf G) {
        ∀i bejárt[i] = false;
        for(v : G)
                if(!bejárt[v]) mélyBejár(v);
}

Halmaz<int> mélyBejárT(int p, Halmaz<int> komponens) {
        bejárt[p] = true;
        for(int i = 0; i < grafT[p].size(); ++i)
                if(!bejárt[grafT[p][i]])
                        mélyBejárT(grafT[p][i], komponens);
        komponens.insert(p);
        return komponens;
}
Halmaz<Halmaz<int>> mélyKeresT(Gráf G) {
        bejárt = false;
        Halmaz<Halmaz<int>> komponensek;
        while(!csökkenő.empty()) {
                int p = csökkenőF.pop();
                Halmaz<int> komponens;
                if(!bejárt[p]) {
                        komponens = mélyBejárT(p, komponens)
                        komponensek.insert(komponens);
                }
        }
        return komponensek;
}

[szerkesztés] A súlyozott gráf (SGraf) adattípus specifikációja √

Értékhalmaz
Gráf = {G = (V, E, C) : V ⊆ PontTípus, E ⊆ V × V, C : E → CímkeTípus}
Műveletek
Gráfműveletek +

G : Gráf; p, p1, p2 : PontTípus; c : CímkeTípus; I : ÉlIterator

Előtte Művelet Utána
{G = (V, E), p1, p2 &iasin; V} ÉlBővít(G, p1, p2, c) E = Pre(E) ∪ {(p1, p2)} ∧ C(p1, p2) = c;}
{G = (V, E), (p1, p2) ∈ E} ÉlCímke(G, p1, p2, c) {c = Pre(C)(p1, p2) ∧ E = Pre(E)}
ÉlCímkéz(G, p1, p2, c) {C(p1, p2) = c ∧ E = Pre(E)}
{G = G} KiCímkézettÉl(G, p) { = {(q, s) : VanÉl(p, q) ∧ C(p, q) = s} }
ÉlIterátor(G, I) { = {(p1, p2) : (p1, p2) ∈ E} }

[szerkesztés] Minimális feszítőfa problémája, a vágások és a biztonságos élek kapcsolatát leíró tétel

[szerkesztés] Kruskal algoritmus √

fa, unioholvan, prisorba(minden él)
kivesz egy él, ha különböző fában vannak akkor két fát összekötni
Gráf Kruskal(SúlyozottGráf G){
        Gráf feszítőFa;
        UnioHolvan H(G.size());
        
        PriSor<SúlyozottGráfÉl> S(G.size());
        for(él : G.élek) S.push(él);

        while (!S.empty()) {
                SúlyozottGráfÉl él = S.pop();
                int fa1 = H.Holvan(él.ki);
                int fa2 = H.Holvan(él.be);
                if (fa1 != fa2) {
                        H.Unio(fa1, fa2);
                        feszítőFa.ÉlBővit(él.ki, él.be);
                }
        }
        if (H.size() != 1) //G nem összefüggő!
                feszítőFa = NULL;
        return feszítőFa;
}

[szerkesztés] Prim algoritmus √

Prim(SúlyozottGráf<double> G, int start) {
        int n = G.size();
        int apa[1..n] = -1;
        double d[1..n] = ∞;
        bool fa[1..n] = false;
        ModPriSor<double> S(n);
        fa[start] = true;
        d[start] = apa[start] = 0;
        for (v : G)
                S.push( (d[v], v) );
        while (!S.empty()) {
                u = S.pop();
                // kiveszi a minimális elemet, és beveszi a fába
                fa[u.adat] = true;
                for (v : G[u.adat].ki) {
                        // még nincs a fában és jobb, mint ami van, akkor update
                        if (!fa[v.pont] && súly(u, v) < d[v.pont]) {
                                d[v.pont] = súly(u, v);
                                apa[v.pont] = u.adat;
                                S.modify(v.pont, d[v.pont]);
                        }
                }
        }
}

[szerkesztés] Dijsktra algoritmus √

Dijkstra(SúlyozottGráf<double> G, int start/*, int end*/) {
        int n = G.size();
        int apa[1..n] = -1;
        double d[1..n] = ∞;
        bool kész[1..n] = false;
        ModPriSor<double> S(n);
        fa[start] = true;
        d[start] = apa[start] = 0;
        for (v : G)
                S.push( (d[v], v) );
        while (!S.empty()) {
                u = S.pop();
                kész[u.adat] = true;
                // if(u.adat == end) return; // elértük a keresett pontot
                for (v : G[u.adat].ki) {
                        if (!kész[v.pont]) {
                                double d_uv = d[u.adat] + v.súly;
                                if(d_uv < d[v.pont]) {
                                        d[v.pont] = d_uv;
                                        apa[v.pont] = u.adat;
                                        
                                        v.kulcs = d_uv;
                                        S.modify(v);
                                }
                        }
                }
        }
}

[szerkesztés] A legrövidebb utak felső korlát és konvergencia tulajdonságai √

Felső korlát tulajdonság
D[v] > δ(s, v) és ha egyszer D[v] = δ(s, v), akkor ezután mindig teljesül a D[v] = δ(s, v) egyenlőség.
Konvergencia tulajdonság
Ha s ~> u → v egy legrövidebb út és D[u] = δ(s, u) Közelít(u, v) végrehajtása előtt, akkor Közelít(u, v) után D[v] = δ(s, v).

[szerkesztés] Floyd-Warshall algoritmus √

void FW(SúlyozottGráf G) {
        int n = G.Pontokszáma();
        double D[1..n, 1..n] = ∞;
        int előző[1..n, 1..n] = 0;
        for (int u : G){
                D[u, u] = 0.0;
                for (v : G[u].ki) {
                        D[u, v] = G[v].súly;
                        előző[u, v] = v;
                }
        }
        for (k = 1..n)
                for (i = 1..n)
                        for (j = 1..n) {
                                double Dikj=D[i, k]+D[k, j];
                                if (Dikj < D[i, j]) {
                                        D[i, j]=Dikj;
                                        előző[i, j] = előző[i, k];
                                }
                        }
}
void ÚtKiír(int[][] előző, int u, int v) {
        if (előző[u, v] == 0) {
                kiír("Nincs " + u + "->"+ v + " út!");
                return;
        }
        do {
                kiír(u + "->");
                u = előző[u, v];
        } while (u != v);
        kiír(u);
}

[szerkesztés] Kiválasztó rendezés algoritmusa √

template<typename T> void KiválasztóRendezés(T* tömb, int n /*hossz*/) {
        for(int i = 0; i < n; ++i) {
                // minimum kiválasztás
                int minIndex = i;
                for(int j = i + 1; j < n; ++j)
                        if(tömb[j] < tömb[minIndex])
                                minIndex = j;
                // csere a minimum és az aktuális eleje
                swap(tömb[minIndex], tömb[i]);
                // így a sor aktuális elején mindig a minimális elem lesz
        }
}

[szerkesztés] Beszúró rendezés algoritmusa √

template<typename T> BeszúróRendezés(T* tömb, int n /*hossz*/) {
        for(int i = 1; i < n; ++i) {
                T temp = tömb[i];
                j = i - 1;
                while (0 <= j && temp < tömb[j])
                        tömb[j + 1] = tömb[j--];
                tömb[j + 1] = temp;
        }
}

[szerkesztés] Kupac adatszerkezet definíciója, süllyeszt algoritmus √

Kupac
Olyan (bináris) fa, amely teljesíti a kupactulajdonságot.
Kupactulajdonság
Ha B A gyereke, akkor a (maximális) kupactulajdonság: kulcs(A) ≥ kulcs(B)
template<typename T> void Sullyeszt(T* kupac, int pont, int vege){
        int apa = pont;
        int fiu;
        T temp = kupac[pont];
        while ((fiu = 2*apa+1) < vege ) {
                // ha jobb gyerek > bal gyerek, akkor átlép jobb gyerekre
                if (kupac[fiu + 1] > kupac[fiu]) fiu++;
                // ha teljesül a kupac tulajdonság, akkor megáll
                if (temp >= kupac[fiu]) break;
                // a gyereket feljebb hozza
                kupac[apa] = kupac[fiu];
                apa = fiu;
        }
        // a javítandó elemet beteszi az utolsó emelt gyerek helyére
        kupac[apa] = temp;
}

[szerkesztés] Kupacrendezés algoritmusa, a süllyeszt algoritmussal együtt √

template<typename T> void KupacRend(T* tomb, int n /*hossz*/) {
        n = n - 1; // nulla indexelés miatt
        // épít egy kupacot
        for (int i = n / 2; i >= 0; --i)
                Sullyeszt(tomb, i, n);

        // a kupac legnagyobb elemét kicseréli az utolsó elemmel
        // majd kijavítja a kupacot, ami mostmár nem a teljes, hossz, hanem csak az "utolsó" előtti elemtől számít
        for (int i = n; i >= 0; --i) {
                swap(tomb[0], tomb[i]); 
                Sullyeszt(tomb, 0, i - 1);
        }
}

[szerkesztés] Gyorsrendezés algoritmusa, a feloszt algoritmussal együtt, egy tömbben megvalósítva √

template<typename T> int Feloszt(T* tömb, int bal, int jobb) {
        T osztó = tömb[bal];
        int b = bal;
        // H = tömb[bal..jobb]
        for (int j = bal + 1; j <= jobb; j++) {
                // invariáns: H_bal = tömb[bal..j] < osztó ≤ H_jobb = tömb[j + 1..jobb]
                if (a[j] < osztó) {
                        a[b] = a[j];
                        a[j] = a[++b];
                }
        }
        a[b] = osztó;
        return b;
}
template<typename T> void GyorsRendezés(T* tömb, int bal, int jobb) {
        int felosztás = Feloszt(tömb, bal, jobb);
        if (bal < felosztás)
                GyorsRendezés(tömb, bal, felosztás - 1);
        if (felosztás + 1 < jobb)
                GyorsRendezés(tömb, felosztás + 1, jobb);
}
template<typename T> void GyorsRendezés(T* tömb, int hossz) {
        GyorsRendezés(tömb, 0, hossz - 1);
}

[szerkesztés] Számláló rendezés (input specifikációval) √

Tegyük fel, hogy a rendezendő A = {a1, ..., an} halmaz elemei (kulcs, adat) pár és a halmazt a kulcs szerint kell rendezni. Legyen min a legkisebb, max pedig a legnagyobb kulcsérték, m = max - min. Ekkor a rendezés elvégezhető O(m + n) időben.
Teljes megvalósítás
pair<KulcsTípus, AdatTípus>[] szamlalo(pair<KulcsTípus, AdatTípus> A[n]) {
        KulcsTípus min, max;
        for(int i = 0; i < n; ++i) {
                if(A[i].kulcs > max) max = A[i].kulcs;
                if(A[i].kulcs < min) min = A[i].kulcs;
        }
        int m = max - min + 1;
        KulcsTípus C[m] = 0;

        for(int i = 0; i < n; ++i) C[ A[i].kulcs - min ]++;
        for(int i = 1; i < m; ++i) C[i] += C[i - 1];
        pair<KulcsTípus, AdatTípus> B[n];
        for(int i = 0; i < n; ++i) B[ --C[ A[i].kulcs - min ] ] = A[i];
        return B;
}
Rövidített megvalósítás
Tegyük fel hogy a rendezés kap egy tömböt, melyben a számok 0 ≤ A[i] ≤ max, ∀ 0 ≤ i < n-re, ahol n a tömb hossza.
int[] szamlalo(int A[n], int max) {
        int C[max] = {0};
        // megszámolja hogy adott elemből mennyi van
        for(int i = 0; i < n; ++i) C[ A[i] ]++;
        // összeszámolja, hogy adott elemnél kisebb-egyenlő mennyi van
        for(int i = 1; i < max; ++i) C[i] += C[i - 1];

        int B[n];
        // feltölti az új - leendő rendezett - tömböt C-nek megfelelően
        for(int i = 0; i < n; ++i) B[ --C[ A[i] ] ] = A[i];
        return B;
}

[szerkesztés] Radix rendezés (input specifikációval)

[szerkesztés] Vödrös rendezés (input specifikációval)

Tegyük fel, hogy a rendezendő H = {a1, ..., an} halmaz elemeinek kulcsai a [0,1) intervallumba eső valós számok (float vagy double).

Pszeudo kód wiki-ről: Vödrös rendezés, de szerintem ez kevés:

lista VödrösRendezés(tömb[n], vödrökSzáma) {
        lista vödrök[vödrökSzáma];
        for(i = 0..n-1)
                vödrök[(int)(tömb[i] * vödrökSzáma)].beszúr(tömb[i]);
        for(i = 0..n-1)
                next-sort(vödrök[i]);
        return vödrök[0] + ... + vödrök[n-1];
}

[szerkesztés] Kibővített euklideszi algoritmus √

Visszatér a és b legnagyobb közös osztójával és p, q kimeneti paraméterekben megadja p * a0 + q * b0 = lnko(a, b) paramétereit

int euclid(int a, int b, int& p, int& q) {
        // We maintain the invariant:
        // p * a0 + q * b0 = a
        // r * a0 + s * b0 = b.
        if(a < b) swap(a, b);
        int s = p = 1, r = q = 0;
        while (b != 0) {
                int rem = a % b, quot = a / b;
                a = b; b = rem;
                int new_r = p - quot * r;
                int new_s = q - quot * s;
                p = r; q = s;
                r = new_r; s = new_s;
        }
        return a;
}

[szerkesztés] Bináris keresőfa definíciója , Keres algoritmus √

Az F fát bináris fának nevezzük, ha (∀p ∈ F)(Fok(p) ≤ 2).

Ábrázolás
struct Fa {
        ElemTípus adat;
        Fa* bal;
        Fa* jobb;
//      Fa* apa;
};
A F = (M, R, Adat) absztrakt adatszerkezetet bináris keresőfának nevezzük, ha
  1. F bináris fa,
  2. Adat : M → ElemTípus és ElemTípus-on értelmezett egy ≤ lineáris rendezési reláció,
  3. (∀x ∈ M)(∀p ∈ Fbal(x))(∀q ∈ Fjobb(x))(Adat(p) ≤ Adat(x) ≤ Adat(q))
Fa* Keres(Fa* fa, ElemTípus adat){
        while (fa != NULL) && (adat != fa->adat)
                if (adat < fa->adat)
                        fa = fa->bal;
                else
                        fa = fa->jobb;
        return fa;
}

[szerkesztés] Rákövetkező elem megtalálása bináris keresőfában √

Fa* Következő(Fa* fa) {
        // ha van jobb részfája
        if(fa->jobb != NULL) {
                fa = fa->jobb;
                // megkeresi annak minimális elemét
                while (fa->bal != NULL)
                        fa = fa->bal;
                return fa;
        } else {
                Fa* fiu = fa;
                Fa* apa = fiu->apa;
                // felmegy a fában amíg a fiú nem lesz bal fiú
                while (apa != NULL && fiu != apa->bal) {
                        fiu = apa;
                        apa = fiu->apa;
                }
                return apa;
        }
}

[szerkesztés] Beszúrás bináris keresőfába √

struct Fa {
        int adat;
        Fa* bal, jobb;
        Fa(int n): adat(n) {}
};
void beszur(Fa* gyoker, int n) {
        Fa* jelen = NULL;
        Fa* kov = gyoker;
        // megkeresi a beszúrás helyét, jelen-ben a beszúrandó elem apja lesz
        while(kov) {
                jelen = kov;
                if(n < kov->adat)
                        kov = kov->bal;
                else
                        kov = kov->jobb;
        }
        // létrehozza az új pontot
        kov = new Fa(n);
        if(jelen == NULL) // üres fa
                gyoker = kov;
        else // normál fa, beszúrja a megfelelő helyre
                if(n < jelen->adat)
                        jelen->bal = kov;
                else
                        jelen->jobb = kov;
}

[szerkesztés] Törlés bináris keresőfában √

  • levél
egyszerű törlés
  • egy gyerek
csere a másik gyerekre, majd törlés
  • két gyerek
  • kicseréljük az értékét
    • vagy inorder következővel (jobb részfa min)
    • vagy inorder előzővel (bal részfa max)
  • majd törlés
struct Pont {
        Pont* bal;
        Pont* jobb;
        int érték;
};
void Töröl(Pont* pont) {
        Pont* temp = pont;
        // egy gyerek: jobb, (és levél, ha pont = pont->jobb NULL)
        if (pont->bal == NULL) {
                *pont = *pont->jobb; // copy constructor
                delete temp;
        // egy gyerek: bal
        } else if (pont->jobb == NULL) {
                *pont = *pont->bal; // copy constructor
                delete temp;
        // két gyerek
        } else {
                temp = pont->jobb;
                while (temp->bal != NULL)
                        temp = temp->bal;
                // csere helyett, elég lementeni a következő elemet, mivel a jelenlegit úgyis töröljük
                pont->érték = temp->érték;
                Töröl(temp); // lehet hogy van neki 1 gyereke
        }
}

[szerkesztés] Hibák, észrevételek

  1. n3.pdf: 3.3 PriSor.SorBol() művelet végeredménye nem Pre(S) ∪ {x}, hanem Pre(S) \ {x}
  2. ...