User:TWiStErRob/Alga
A Wikipédiából, a szabad lexikonból.
- 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.
- "Én, mint a pub-ban található anyag szerzője, egyébként hozzájárulok az ilyen felhasználáshoz."
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
[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:
- 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
-
- a gyökér nem fia egyetlen pontnak sem:

- minden, gyökértől különböző pont fia valamely pontnak:

- minden pontnak legfeljebb egy apja lehet:

- minden pont elérhető a gyökérből:

- a gyökér nem fia egyetlen pontnak sem:
[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
- M az absztrakt memóriahelyek, cellák halmaza.
- R = {r1, ..., rk} a cellák közötti szerkezeti kapcsolatok, ri : M → (M ∪ {ø})*
- 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)
- A gráf csak egy szerkezeti kapcsolatot ad meg.
- Gráf esetén a szomszédok halmaza nem rendezett.
- 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

, 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
. - 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
, tehát a megoldásban szereplő pénzérmék egy sorrendje
- egy megoldása a feladatnak. Ekkor
- megoldása lesz annak a feladatnak, amelynek bemenete a felváltandó
érték, és a felváltáshoz legfeljebb a első ik - 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
.- p és q távolsága, p-ből q-ba vezető legrövidebb út hossza

[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
- Végrehajt egy mélységi keresés az f elhagyási időkkel
- amikor egy pont vizsgálatát befejezzük, akkor egy lánc elejére beszúrjuk
- 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
- Számítsuk ki a Mélykeresés algoritmussal az f(u) elhagyási értékeket.
- 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.
- 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
- F bináris fa,
- Adat : M → ElemTípus és ElemTípus-on értelmezett egy ≤ lineáris rendezési reláció,
- (∀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
- kicseréljük az értékét
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
- n3.pdf: 3.3 PriSor.SorBol() művelet végeredménye nem Pre(S) ∪ {x}, hanem Pre(S) \ {x}
- ...



