Algoritmusok és adatszerkezetek I. el®adásjegyzet
Ásványi Tibor
[email protected] 2017. január 22.
1.
Bevezetés
Az itt következ® el®adásjegyzetekben a láncolt listákról, a rendezésekr®l és a programok aszimptotikus m¶veletigényér®l szóló fejezetek még nem teljesek; egyenl®re csak a bináris és általános fákkal kapcsolatos részeket dolgoztam ki részletesen, illetve a B+ fák témakörben angol nyelv¶ egyetemi tananyag fordítását bocsátom rendelkezésükre.
Az el®adásokon tárgyalt programok
struktogramjait igyekeztem minden esetben megadni, a másolási hibák kiküszöbölése érdekében. Ebben a tananyagban sajnos még egyáltalán nincsenek a megértést segít® ábrák. Ezek b®ségesen megtalálhatók az ajánlott segédanyagokban. A vizsgára való készülésben els®sorban az el®adásokon és a gyakorlatokon készített jegyzeteikre támaszkodhatnak. További ajánlott források:
Hivatkozások [1] Ásványi
Tibor,
Algoritmusok és adatszerkezetek I. el®adásjegyzet
(2016) http://aszt.inf.elte.hu/∼asvanyi/ad/ad1jegyzet.pdf [2] Ásványi Tibor, AVL tree balancing rules (2016) http://aszt.inf.elte.hu/∼asvanyi/ad/AVL-tree_balancing.pdf [3] Ásványi Tibor, Algoritmusok I. gyakorló feladatok (2015) http://aszt.inf.elte.hu/∼asvanyi/ad/ad1feladatok.pdf [4] Fekete István, Algoritmusok jegyzet http://people.inf.elte.hu/fekete/algoritmusok_jegyzet/
1
[5] Fekete István, Algoritmusok jegyzet (régi) http://aszt.inf.elte.hu/∼asvanyi/ad/FeketeIstvan/ [6] Carl Burch, Ásványi Tibor, B+ fák http://aszt.inf.elte.hu/∼asvanyi/ad/B+ fa.pdf [7] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.,
magyarul:
Új Algortimusok,
Scolar Kiadó, Budapest, 2003.
ISBN: 963 9193 90 9
angolul: Introduction to Algorithms (Third Edititon), The MIT Press, 2009. [8] Wirth, N., Algorithms and Data Structures,
Prentice-Hall Inc., 1976, 1985, 2004. magyarul: Algoritmusok + Adatstruktúrák = Könyvkiadó, Budapest, 1982. ISBN 963 10 3858 0
[9] Weiss,
Mark
Allen,
Data
Structures
and
Addison-Wesley, 1995, 1997, 2007, 2012, 2013.
Programok,
Algorithm
M¶szaki Analysis,
Saját jegyzeteiken kívül els®sorban az ebben a jegyzetben ([1] a [2] kiegészítéssel), illetve az itt hivatkozott helyeken [4, 5, 6, 7] leírtakra támaszkodhatnak.
Wirth [8] és Weiss [9] klasszikus munkáinak megfelel® fejezetei pedig
értékes segítséget nyújthatnak a mélyebb megértéshez. Ennek a jegyzetnek a *-gal jelölt alfejezetei szintén a mélyebb megértést szolgálják, azaz nem részei a vizsga anyagának. A vizsgákon az elméleti kérdések egy-egy tétel bizonyos részleteire vonatkoznak.
Lesznek még megoldandó feladatok, amiket [3] alapján állítok
össze.
2
2.
Tematika
Minden tételhez:
Egy algoritmus, program, m¶velet bemutatásának min-
dig része a m¶veletigény elemzése. Hivatkozások: például a [4] 1, 14, 18 jelentése: a [4] sorszámú szakirodalom adott fejezetei. 1.
Függvények aszimptotikus viselkedése (O, o, Ω, ω, Θ) .
veletigénye (futási id® nagyságrendje:
Programok m¶-
T (n), mT (n), AT (n), M T (n)), példák:
beszúró rendezés (insertion sort) és összefésül® (összefuttató) rendezés (merge sort) ([1]; [4] 1, 14, 18; [5]; [7] 1-3.) 2. Elemi, lineáris adatszerkezetek: tömbök, láncolt listák, láncolt listák típusai, listakezelés. ([1]; [4] 3, 6; [7] 10; [8] 4.1 - 4.3) 3. Elemi adattípusok: vermek, sorok ([1]; [4] 3-4; [7] 10.1), megvalósításuk tömbös és láncolt reprezentációk esetén (láncolt listás megvalósítás a gyakorlatokon). Vermek felhasználása: kifejezések lengyel formára hozása, lengyel forma kiértékelése (ld. gyakorlat). 4. Els®bbségi (prioritásos) sorok megvalósítása rendezetlen illetve rendezett tömbbel [1], rendezetlen, illetve rendezett listával (HF), továbbá kupaccal ([1]; [4] 8; [7] 6.5). A reprezentációk és az implementációk összehasonlítása a m¶veletek hatékonysága szempontjából. 5. Fák, bináris fák, bejárások, láncolt reprezentáció, példák ([1]; [4] 7, 11.2.3; [7] 10.4, 12.1). 6. Speciális bináris fák, aritmetikai ábrázolás, kupac, kupac m¶veletei, kupacrendezés (heapsort) ([1]; [4] 8.3-8.5, 16; [7] 6). 7. Véletlen építés¶ bináris keres®fák és m¶veleteik ([1]; [4] 11; [7] 12; [8] 4.4). 8. AVL fák és m¶veleteik: kiegyensúlyozási sémák, programok. Az AVL fa magassága ([1, 2], [4] 12; [5]; [8] 4.5). 9. Általános fák, bináris láncolt reprezentáció, bejárások ([1]; [8] 4.7 bevezetése). Egyéb reprezentációk? (HF) 10. B+ fák és m¶veleteik [6]. 11. Gyorsrendezés (quicksort) ([1]; [7] 7; [5]; [4] 17). 12.
A beszúró, összefésül®, kupac és gyors rendezés összehasonlítása.
összehasonlító rendezések alsókorlát-elemzése ([4] 19; [7] 8.1).
3
Az
3.
Jelölések
N = {0; 1; 2; 3; . . .} a természetes számok halmaza. Z = {. . . − 3; −2, −1; 0; 1; 2; 3; . . .} az egész számok R a valós számok halmaza. P a pozitív valós számok halmaza. log2 n ha n > 0 lg n = 0 ha n=0 n f ele(n) = b 2 c, ahol n ∈ N
alapértelmezésben (tehát ha a környe-
A képletekben és a struktogramokban zetb®l nem következik más) az
halmaza.
i, j, k, l, m, n, I, J, K, M, N bet¶k egész számop, q, r, s, t, F, L bet¶k pointereket
kat (illetve ilyen típusú változókat), míg a
(azaz mutatókat, memóriacímeket, illetve ilyen típusú változókat) jelölnek. A
T alapértelmezésben
olyan ismert (de közelebbr®l meg nem nevezett)
típust jelöl, amelyen teljes rendezés (az és értékadás (pl. Az
x := y )
=, 6=, <, >, ≤, ≥ összehasonlításokkal)
van értelmezve.
x, y, z alapértelmezésben T
típusú változókat jelölnek.
A[1..n], B[i..j], C[k..m]:T . Az alapértelmezett elemtípus a T , amit az A és a B tömbnél nem adtunk meg, míg a C tömbnél A tömböket pl. így jelöljük: megadtuk. A struktogramokban néha szerepelnek szögletes zárójelek közé írt utasítások.
Ez azt jelenti, hogy a bezárójelezett utasítás bizonyos programozási
környezetekben szükséges lehet. Ha tehát a program megbízhatósága és módosíthatósága a legfontosabb szempont, ezek az utasítások is szükségesek. Ha a végletekig kívánunk optimalizálni, akkor bizonyos esetekben elhagyhatók.
3.1.
A struktogramok paraméterlistái, érték és referencia módú paraméterek
A struktogramokhoz mindig tartozik egy eljárásnév és általában egy paraméterlista is (ami esetleg üres, de a () zárójelpárt ott is, és a megfelel®
Ha egy struktogramhoz csak név tartozik, akkor az úgy értend®, mintha a benne található kód a hívás helyén lenne. eljáráshívásban is kiírjuk).
Ha egy paraméterlistával ellátott struktogramban olyan változónév szerepel, ami a paraméterlistán nem szerepel, akkor ez alapértelmezésben a struktogrammal leírt eljárás lokális változója.
4
A skalár típusú
1
paramétereket
alapértelmezésben érték szerint vesszük át.2
A skalár típusú paraméterek referencia módú paraméterek is lehetnek, de akkor ezt a formális paraméter listán a paraméter neve el®tt egy
3
jelölni kell (pl. swap(&x, &y )).
&
jellel
A formális paraméter listán a felesleges
&-
pre xek hibának tekintend®k, mert a referencia módú skalár paraméterek kezelése az eljárás futása során a legtöbb implementációban lassúbb, mint az érték módú paramétereké. Az aktuális paraméter listán nem jelöljük külön a referencia módú pa-
4
ramétereket , mert egyrészt a formális paraméter listáról kiderül, hogy egy tetsz®leges paraméter érték vagy referencia módú-e, másrészt az
&-pre x
az
aktuális paraméternél teljesen mást jelent (tudniillik, hogy a jelölt adatra mutató pointert szeretnénk a hívott eljárásnak az ott jelölt paramétermód szerint átadni). Ha az eljárásokra szövegben hivatkozunk, a paraméterek módját néhány kivételes esett®l eltekintve szintén nem jelöljük. (Pl.: A swap(x, y ) eljárás megcseréli az A nem-skalár
x 5
és az
y
paraméterek értékét.)
típusú paraméterek csak referencia módú paraméterek lehet-
nek. (Pl. a tömböket, rekordokat nem szeretnénk a paraméterátvételkor lemásolni.) A nem-skalár típusok esetén ezért egyáltalán nem jelöljük a paramétermódot, hiszen az egyértelm¶.
3.2.
Tömb típusú paraméterek a struktogramokban
Ha pl. az
A[1..n] kifejezés egy struktogram formális paraméter listáján,
vagy
egy eljáráshívás aktuális paraméter listáján szerepel, akkor az egy progra-
1 A skalár típusok az egyszer¶ típusok: a szám, a pointer és a felsorolás (pl. a logikai és a karakter) típusok.
2 Az érték módú paraméterek esetén, az eljáráshíváskor az aktuális paraméter értékül
adódik a formális paraméternek, ami a továbbiakban úgy viselkedik, mint egy lokális változó, és ha értéket kap, ennek nincs hatása az aktuális paraméterre.
3 A referencia módú paraméterek esetén, az eljáráshíváskor az aktuális paraméter össze-
kapcsolódik a megfelel® formális paraméterrel, egészen a hívott eljárás futásának végéig, ami azt jelenti, hogy bármelyik megváltozik, vele összhangban változik a másik is. Amikor tehát a formális paraméter értéket kap, az aktuális paraméter is ennek megfelel®en változik.
Ha például a fenti swap(&x, &y ) eljárás törzse {z :=x;
swap(a, b) eljáráshívás hatására az
a
és
b
x:=y ; y :=z ;},
akkor a
változók értéke megcserél®dik. Ha az eljárásfej
swap(x, &y ) lenne, az eljáráshívás hatása b
:= a
lenne, ha pedig az eljárásfej swap(x, y )
lenne, az eljáráshívás logikailag ekvivalens lenne a SKIP utasítással.
4 Pl. a swap(&x, &y ) eljárás egy lehetséges meghívása: swap(A[i], A[j]).
5 A nem-skalár típusok az összetett típusok. Pl. a tömb, sztring, rekord, fájl, halmaz, zsák, sorozat, fa és gráf típusok, valamint a tipikusan de niált osztályok.
5
struct, illetve class kulcsszavakkal
mozási nyelven két paramétert jelentene, az információval, hogy az Ha pl. az
A[m..n]
A
egy
1-t®l n-ig
A-t
és az
n-et,
azzal a plusz
indexelt vektor.
kifejezés egy struktogram formális paraméter listáján,
vagy egy eljáráshívás aktuális paraméter listáján szerepel, akkor az egy programozási nyelven három paramétert jelentene, az azzal a plusz információval, hogy az
A
egy
A-t,
m-t®l n-ig
az
m-et
és az
n-et,
indexelt vektor.
Ha tehát egy struktogram egy formális paramétere pl. az
A[1..n],
ak-
kor a neki megfelel® eljáráshívásban a megfelel® aktuális paraméter lehet pl.
B[1..m], de nem lehet pl. C[k..m], hiszen az el®bbi kett® két, az utóbbi pedig három paramétert jelöl, és nem lehet az aktuális paraméter pl. C[k..10] sem, mert ez ugyan csak két paramétert jelöl, de pl. a k nem feleltethet® meg az n-nek, és nem adható értékül az 1-nek sem.
4.
Algoritmusok
algoritmus egy jól de niált kiszámítási eljárás, amely valamely adatok bemenet vagy input) felhasználásával újabbakat (kimenet, eredmény vagy output) állít el®. (Gondoljunk pl. két egész szám legnagyobb közös osztójára Az
(
[lnko(x, y ) függvény], a lineáris keresésre a maximum keresésre, az összegzésre stb.)
Az algoritmus bemenete adott
lnko(x, y ) függvény esetén pl.
x
és
y
el®feltételnek
kell eleget tegyen.
(Az
egész számok, és nem mindkett® nulla.)
Ha az el®feltétel teljesül, a kimenet adott
utófeltételnek kell eleget tegyen.
Az
utófeltétel az algoritmus bemenete és a kimenete közt elvárt kapcsolatot írja le. Maga az algoritmus számítási lépésekb®l áll, amiket általában szekvenciák, elágazások, ciklusok, eljárás- és függvényhívások segítségével, valamely pszeudo-kódot (pl. struktogramokat) felhasználva formálunk algoritmussá. Szinte minden komolyabb számítógépes alkalmazásban szükséges, els®sorban a tárolt adatok hatékony visszakeresése céljából, azok rendezése. Így témánk egyik klasszikusa a
rendezési feladat.
Most megadjuk, a rendez® algo-
ritmusok bemenetét és kimenetét milyen el®- és utófeltétel páros, ún.
speci káció írja le.
Ehhez el®ször megemlítjük, hogy
feladat
kulcs alatt olyan adatot
értünk, aminek típusán teljes rendezés de niált. (Kulcs lehet pl. egy szám vagy egy sztring.)
Bemenet: n darab kulcs ha1 , a2 , . . . , an i sorozata. Kimenet:
A bemenet egy olyan
hap1 , ap2 , . . . , apn i
permutációja, amelyre
ap 1 ≤ ap 2 ≤ . . . ≤ ap n . A fenti feladat nagyon egyszer¶, ti. könnyen érthet®, hatékony megoldására viszont ki nomult algoritmusokat (és hozzájuk kapcsolódó adatszerkezeteket) dolgoztak ki, így e tárgynak is a szakirodalomban jól bevált bevezetése lett.
6
4.1.
Az A[1..n] vektor monoton növekv® rendezése
Egy sorozatot legegyszer¶bben egy sorozat kezd® indexe
A[k..u]
vektorban tárolhatunk, ahol
u pedig az utolsó elem indexe.
k
a
Az elemtípust általában
nem adjuk meg, hangsúlyozva, hogy az algoritmus általános, bár a rendezéseknél feltesszük, hogy a vektor elemtípusára teljes rendezés de niált és az értékadó utasítás is értelmezve van. Ha mégis feltüntetjük a akkor az
A[k..u]
4.1.1.
Beszúró rendezés (Insertion sort)
vektort
A[k..u] : T
T
elemtípust,
alakban adjuk meg.
Ha valaki semmit sem tud a rendezésekr®l, és megkapja azt a feladatot, hogy rakjon 10-30 dolgozatot nevek szerint sorba, jó eséllyel ösztönösen ezt az algoritmust fogja alkalmazni: Kiválaszt egy dolgozatot, a következ®t ábécé rendben elé vagy mögé teszi, a harmadikat e kett® elé, közé, vagy mögé teszi a megfelel® helyre stb. Ha a rendezést egy számsorra kell alkalmaznunk, pl. a
h5, 4, 2, 8, 3i-ra,
el®ször felosztjuk a sorozatot egy rendezett és egy ezt követ®
rendezetlen szakaszra, úgy, hogy kezdetben csak az els® szám van a rendezett részben:
h5
|
4, 2, 8, 3i.
Ezután beszúrjuk a rendezetlen szakasz els® elemét
a rendezett részbe a megfelel® helyre, és ezt ismételgetjük, amíg a sorozat
h5 | 4, 2, 8, 3i → h4, 5 8, 3i → h2, 4, 5, 8 | 3i → h2, 3, 4, 5, 8 | i → h2, 3, 4, 5, 8i. rendezetlen vége el nem fogy:
|
2, 8, 3i → h2, 4, 5
|
A rendezett beszúrás technikája attól függ, hogyan tároljuk a sorozatot. Ha egy tömbben, akkor a beszúrást úgy végezzük el, hogy a rendezetlen
x) összehasonlítjuk a rendezett szakasz utolsó u ≤ x, akkor x a helyén van, csak a rendezett szakasz fels® határát kell eggyel növelni. Ha u > x, akkor x-et elmentjük egy temporális változóba, és u-t az x helyére csúsztatjuk. Úgy képzelhetjük, hogy u régi helyén most egy lyuk keletkezett. Az x a lyukba pontosan akkor illik bele, ha nincs bal szomszédja, vagy ez ≤ x. Addig tehát, amíg a lyuknak van bal szomszéja, és ez nagyobb, mint x, a lyuk bal szomszédját mindig a lyukba tesszük, és így a lyuk balra mozog. Ha a lyuk a helyére ér, azaz x szakasz els® elemét (legyen elemével (legyen
u).
Ha
beleillik, akkor bele is tesszük. (Ld. az alábbi struktogramot!) Tekintsük például a
h2, 4, 5, 8, 3i
tömböt, ami a
8-ig
rendezett, és már
3-at kell rendezetten beszúrni. El®ször úgy találjuk, hogy 8 > 3, így a 3-at kivesszük x-be, majd a lyukat (jelölje _) a helyére mozgatjuk, és végül beletesszük a 3-at: h2, 4, 5, 8, 3i → h2, 4, 5, 8, _i, x = 3 → h2, 4, 5, _, 8i, x = 3 → h2, 4, _, 5, 8i, x = 3 → h2, _, 4, 5, 8i, x = 3 → h2, 3, 4, 5, 8i. csak a
7
beszúró_rendezés(A[1..n])
i := 2..n A[i − 1] > A[i] A
x := A[i] A[i] := A[i − 1] j := i − 2 j > 0 ∧ A[j] > x
SKIP
A[j + 1] := A[j] j := j − 1 A[j + 1] := x
A fenti eljárás az
A[1..n]
vektort rendezi monoton növekv®en az el®bb
ismertetett egyszer¶ beszúró rendezéssel. A f® ciklus invariánsa:
2 ≤ i ≤ (n + 1) ∧ A[1..n] az input vektor egy permutáltja, ami az (i − 1) -edik eleméig monoton növekv®en rendezett. Összefoglalva a m¶ködést: Ha
n < 2,
akkor az
A[1..n]
vektor üres, vagy egy-
n ≥ 2, A[1..1] rendezett, azaz ezután mindig A[i]-t szúrja
elem¶, ezért rendezett, és a program f® ciklusa egyszer sem fut le. Ha a rendezés meghívásakor csak annyit tudhatunk, hogy
i = 2-re
fennáll az invariáns. A f® ciklus magja
be a vektor rendezett szakaszába, Mikor tehát
i
eléri az
n+1
i-t
eggyel növeli és tartja az invariánst.
értéket, már a teljes
A[1..n]
vektor rendezett, és
ekkor be is fejez®dik az eljárás.
4.1.2.
Programok hatékonysága és a beszúró rendezés
Fontos kérdés, hogy egy
S
program, például a fenti rendezés mennyire ha-
Hatékonyság alatt az eljárás er®forrás igényét, azaz futási idejét és tárigényét értjük.6 Mivel ez az egyszer¶ rendezés a rendezend® vektoron kívül tékony.
csak néhány segédváltozót igényel, extra tárigénye minimális. Így els®sorban a futási idejére lehetünk kíváncsiak. Ezzel kapcsolatos nehézség, hogy nem ismerjük a leend® programozási környezetet:
sem a programozási nyelvet,
amiben kódolni fogják, sem a fordítóprogramot vagy interpretert, sem a leend® futtatási környezetet, sem a számítógépet, amin futni fog, így nyilván a futási idejét sem tudjuk meghatározni.
6 Nem különböztetjük meg most a különféle hardver komponenseket, hiszen ezeket az algoritmus szintjén nem is ismerjük.
8
Meghatározhatjuk, vagy legalább becslés(eke)t adhatunk viszont arra,
hány eljáráshívást hajt végre + hányat iterálnak összesen kódban szerepl® különböz® ciklusok. Meghogy adott
n
S
méret¶ input esetén az
algoritmus
M TS (n), a várható vagy átlagos mTS (n) eseteket. A valódi maximális,
különböztetjük a legrosszabb vagy maximális
ATS (n)
és a legjobb vagy minimális
átlagos és minimális futási id®k általában ezekkel arányosak lesznek.
M TS (n) = mTS (n),
akkor de níció szerint
TS (n)
Ha
a minden esetre vonatkozó
m¶veletigény (tehát az eljáráshívások és a ciklusiterációk számának összege), azaz
TS (n) = M TS (n) = ATS (n) = mTS (n)
A továbbiakban, a programok futási idejével kapcsolatos számításoknál, a
m¶veletigény és
a
futási id®,
költség kifejezéseket szinonímákként eljáráshívások és a ciklusiterációk összegére
valamint a
fogjuk használni, és ezek alatt az
M TS (n), ATS (n), mTS (n) ahol n az input mérete.
vonatkozó értjük,
és ha létezik,
TS (n)
függvényeket
Tekintsük most példaként a fentebb tárgyalt beszúró rendezést (insertion sort)!
A rendezés során egyetlen eljáráshívás hajtódik végre, és ez a
beszúró_rendezés(A[1..n]) eljárás hívása. Az eljárás f® ciklusa minden esetben pontosan
(n − 1)
-szer fut le.
El®ször adjunk becslést a beszúró rendezés minimális futási idejére, amit jelöljünk
mTIS (n)-nel,
ahol
n
a rendezend® vektor mérete, általában a kér-
7
déses kód által manipulált adatszerkezet mérete.
Lehet, hogy a bels® ciklus
egyet sem iterál, pl. ha a f® ciklus mindig a jobboldali ágon fut le, mert
A[1..n]
eleve monoton növekv®en rendezett. Ezért
mTIS (n) = 1 + (n − 1) = n (n − 1) iterációja.) Most adjunk becslést (M TIS (n)) a beszúró rendezés maximális futási ide-
(Egy eljáráshívás + a küls® ciklus jére!
Világos, hogy az algoritmus ciklusai akkor iterálnak a legtöbbet, ha
mindig a küls® ciklus bal ágát hajtja végre, és a bels® ciklus
j = 0-ig fut.
(Ez
akkor áll el®, ha a vektor szigorúan monoton csökken®en rendezett.) Végrehajtódik tehát egy eljáráshívás + a küls® ciklus
(n − 1)
iterációja, amihez
i értékkel való iterációjakor a bels® ciklus maximum (i − 2) -ször iterál. Mivel az i, 2-t®l n-ig fut, a bels® ciklus összesen legfeljebb Pn i=2 (i − 2) iterációt hajt végre. Innét a küls® ciklus adott
M TIS (n) = 1 + (n − 1) +
n X
(i − 2) = n +
i=2
n−2 X
j =n+
j=0
1 1 1 M TIS (n) = n2 − n + 2 2 2 7 Az IS a rendezés angol nevének (Insertion Sort) a rövidítése. 9
(n − 1) ∗ (n − 2) 2
Látható, hogy a minimális futási id® becslése az
A[1..n]
input vektor mére-
tének lineáris függvénye, míg a maximális, ugyanennek négyzetes függvénye, ahol a polinom f® együtthatója mindkét esetben pozitív.
A továbbiakban
ezeket a következ®képpen fejezzük ki:
M TIS (n) ∈ Θ(n2 ).
mTIS (n) ∈ Θ(n), A
Θ(n) (T heta(n))
függvényosztály ugyanis tartalmazza az n összes, pozitív Θ(n2 ) pedig az n összes, pozitív együtthatós
együtthatós lineáris függvényét, másodfokú függvényét.
g(n), a program hatéΘ(g(n)) függvényosztály
(Általában egy tetsz®leges
konyságának becslésével kapcsolatos függvényre a
pontos de nícióját a 7. fejezetben fogjuk megadni.) Mint a maximális futási id®re vonatkozó példából látható, a
Θ jelölés sze-
repe, hogy elhanyagolja egy polinom jelleg¶ függvényben (1) a kisebb nagyságrend¶ tagokat, valamint (2) a f® tag pozitív együtthatóját. Az el®bbi azért jogos, mert a futási id® általában nagyméret¶ inputoknál igazán érdekes, hiszen tipikusan ilyenkor lassulhat le egy egyébként logikailag helyes program. 2 2 Elég nagy n-ekre viszont pl. az a ∗ n + b ∗ n + c polinomban a ∗ n mellett
b ∗ n és c elhanyagolható.
A f® tag pozitív együtthatóját pedig egyrészt azért
hanyagolhatjuk el, mert ez a programozási környezet, mint például a számítógép sebességének ismerete nélkül tulajdonképpen semmitmondó, másrészt pedig azért, mert ha az
a ∗ f (n)
alakú f® tag értéke
n
-et végtelenül növelve
a konstans szorzó sokkal kevésbé befolyásolja a függvény értékét, mint az f (n).
maga is a végtelenhez tart (ahogy az lenni szokott), elég nagy
n-ekre
az
Látható, hogy a beszúró rendezés a legjobb esetben nagyon gyorsan rendez: Nagyságrendileg a lineáris m¶veletigénynél gyorsabb rendezés elvileg is lehetetlen, hiszen ehhez a rendezend® sorozat minden elemét el kell érnünk. A legrosszabb esetben viszont, ahogy szik, ami, ha
n
n
n®, a futási id® négyzetesen növek-
milliós vagy még nagyobb nagyságrend¶, már nagyon hosszú
futási id®ket eredményez. Vegyünk példának egy olyan számítógépet, ami 9 másodpercenként 2 ∗ 10 elemi m¶veletet tud elvégezni. Jelölje most mT (n) az algoritmus által elvégzend® elemi m¶veletek minimális, míg ximális számát!
Vegyük gyelembe, hogy
mTIS (n) = n,
M T (n) a ma-
ami közelít®leg a
küls® ciklus iterációinak száma, és a küls® ciklus minden iterációja legalább 8 elemi m¶veletet jelent; továbbá, hogy M TIS (n) ≈ (1/2) ∗ n2 , ami közelít®leg a bels® ciklus iterációinak száma, és itt minden iteráció legalább 12 elemi mT (n) ≈ 8 ∗ n és a M T (n) ≈ 6 ∗ n2 képletekkel
m¶veletet jelent. Innét a
számolva a következ® táblázathoz jutunk:
10
n mTIS (n) in secs 1000 8000 4 ∗ 10−6 106 8 ∗ 106 0.004 7 10 8 ∗ 107 0.04 8 8 10 8 ∗ 10 0.4 9 9 10 8 ∗ 10 4
M TIS (n) 6 ∗ 106 6 ∗ 1012 6 ∗ 1014 6 ∗ 1016 6 ∗ 1018
in time
0.003 sec 50 min ≈ 3.5 days ≈ 347 days ≈ 95 years
Világos, hogy már tízmillió rekord rendezésére is gyakorlatilag használhatatlan az algoritmusunk. kívül hagytuk.)
(Az implementációs problémákat most gyelmen
Látjuk azt is, hogy hatalmas a különbség a legjobb és a
legrosszabb eset között. Felmerülhet a kérdés, hogy átlagos esetben mennyire gyors az algoritmus. Itt az a gond, hogy nem ismerjük az input sorozatok eloszlását. Ha például az inputok monoton növekv®en el®rendezettek, ami alatt azt értjük, hogy az input sorozat elemeinek a rendezés utáni helyükt®l való távolsága általában egy
n -t®l független k
konstanssal felülr®l becsülhet®, azok száma pedig,
n -t®l független s konstanssal becsülhet® felülr®l, az algoritmus m¶veletigénye lineáris, azaz Θ(n) marad, mivel a bels® ciklus legfeljebb (k + s) ∗ n -szer fut le. Ha viszont
amelyek a végs® pozíciójuktól távolabb vannak, egy szintén
a bemenet monoton csökken®en el®rendezett, az algoritmus m¶veletigénye is közel marad a legrosszabb esethez. tort a rendezés el®tt
Θ(n)
(Bár ha ezt tudjuk, érdemes a vek-
id®ben megfordítani, és így monoton növekv®en
el®rendezett vektort kapunk.) Véletlenített input sorozat esetén, egy-egy újabb elemnek a sorozat már rendezett kezd® szakaszába való beszúrásakor, átlagosan a rendezett szakaszban lév® elemek fele lesz nagyobb a beszúrandó elemnél. A rendezés várható m¶veletigénye ilyenkor tehát:
ATIS (n) ≈ 1 + (n − 1) +
n X i−2 i=2
2
n−2
1 X =n+ ∗ j= 2 j=0
1 (n − 1) ∗ (n − 2) 1 1 ∗ = n2 + n + 1 2 2 4 4 2 ATIS (n) ≈ (1/4) ∗ n . Ez körülbelül a fele
=n+ Nagy
n
-ekre tehát
a maximális
futási id®nek, ami a rendezend® adatok milliós nagyságrendje esetén már így is nagyon hosszú futási id®ket jelent. Összegezve az eredményeinket:
mTIS (n) ∈ Θ(n) ATIS (n), M TIS (n) ∈ Θ(n2 )
11
Ehhez hozzátehetjük, hogy el®rendezett inputok esetén (ami a programozási gyakorlatban egyáltalán nem ritka) a beszúró rendezés segítségével lineáris id®ben tudunk rendezni, ami azt jelenti, hogy erre a feladatosztályra nagyságrendileg, és nem túl nagy
k és s konstansok esetén valóságosan is az optimális
megoldás a beszúró rendezés.
4.1.3.
A futási id®kre vonatkozó becslések magyarázata*
Jelölje most a beszúró_rendezés(A[1..n]) eljárás nimális futási idejét sorban
M T (n)
és
tényleges
maximális és mi-
mT (n)!
Világos, hogy a rendezés akkor fut le a leggyorsabban, ha a f® ciklus minden elemet a végs® helyén talál, azaz mindig a jobboldali ágon fut le. (Ez akkor áll el®, ha a vektor már eleve monoton növekv®en rendezett.) Legyen
a
a f® ciklus jobboldali ága egyszeri végrehajtásának m¶veletigénye,
b
pedig
az eljárás meghívásával, a f® ciklus el®készítésével és befejezésével, valamint az eljárásból való visszatéréssel kapcsolatos futási id®k összege! Ekkor
b nyilván pozitív konstansok, és mT (n) = a ∗ (n − 1) + b. p = min(a, b) és P = max(a, b); ekkor 0 < p ≤ P , és p ∗ (n − 1) + p ≤ mT (n) = a ∗ (n − 1) + b ≤ P ∗ (n − 1) + P , p ∗ n ≤ mT (n) ≤ P ∗ n, azaz
a
és
Legyen most ahonnét
p ∗ mTIS (n) ≤ mT (n) ≤ P ∗ mTIS (n) Most adjunk becslést a beszúró rendezés maximális futási idejére, (M T (n))! Világos, hogy az algoritmus akkor dolgozik a legtöbbet, ha mindig a küls® ciklus bal ágát hajtja végre, és a bels® ciklus
j = 0-ig
fut.
(Ez akkor áll
el®, ha a vektor szigorúan monoton csökken®en rendezett.) Legyen most a bels® ciklus egy lefutásának a m¶veletigénye
d; c
pedig a küls® ciklus bal
ága egy lefutásához szükséges id®, eltekintve a bels® ciklus lefutásaitól, de hozzászámolva a bels® ciklusból való kilépés futási idejét (amibe beleértjük a bels® ciklus feltétele utolsó kiértékelését, azaz a
j=0
esetet), ahol
c, d > 0
állandók. Ezzel a jelöléssel:
M T (n) = b + c ∗ (n − 1) +
n X
d ∗ (i − 2) = b + c ∗ (n − 1) + d ∗
i=2
n−2 X
j=
j=0
(n − 1) ∗ (n − 2) 2 Legyen most q = min(b, c, d) és Q = max(b, c, d); ekkor 0 < q ≤ Q, és q + q ∗ (n − 1) + q ∗ (n−1)∗(n−2) ≤ M T (n) ≤ Q + Q ∗ (n − 1) + Q ∗ (n−1)∗(n−2) 2 2 = b + c ∗ (n − 1) + d ∗
12
q ∗ (n +
(n−1)∗(n−2) ) 2
≤ M T (n) ≤ Q ∗ (n +
(n−1)∗(n−2) ), azaz 2
q ∗ M TIS (n) ≤ mT (n) ≤ Q ∗ M TIS (n) Mindkét esetben azt kaptuk tehát, hogy a valódi futási id® az
és a ciklusiterációk számának összegével becsült futási id®
eljáráshívások
megfelel® pozitív
konstansszorosaival alulról és felülr®l becsülhet®, azaz, pozitív konstans szorzótól eltekintve ugyanolyan nagyságrend¶. Könny¶ meggondolni, hogy ez a megállapítás tetsz®leges program minimális, átlagos és maximális futási idejeire is általánosítható. (Ezt azonban már az Olvasóra bízzuk.)
4.1.4.
Összefésül® rendezés (mergesort)
Az összefésül® rendezés (mergesort, rövidítve
M S)
nagy elemszámú soroza-
tokat is viszonylag gyorsan rendez. Ráadásul a legjobb és a legrosszabb eset között nem mutatkozik nagy eltérés. Els® megközelítésben azt mondhatjuk, hogy a maximális és a minimális futási ideje is szokásos
Θ
n lg n
-nel arányos.
Ezt a
jelöléssel a következ®képpen fejezzük ki.
M TM S (n), mTM S (n) ∈ Θ(n lg n) Ez alatt, a
Θ
jelölés fogalmát tovább tágítva, azt értjük, hogy úgy a ma-
ximális, mint a minimális futási id® alulról és felülr®l is becsülhet® egy-egy
a ∗ n lg n + δ(n)
alakú függvénnyel, ahol a > 0 konstans, és az n -et növelve δ(n) tetsz®legesen közel kerül nullához, azaz nagy n -ekre az n lg n -hez a n lg n képest a δ(n) értéke elhanyagolható. Kicsit formálisabban fogalmazva: Tegyük fel, hogy
f, g : N → R
függvények;
(azaz valamely küszöbszámtól nemnegatív),
f aszimptotikusan nemnegatív g pedig aszimptotikusan pozitív
(azaz valamely küszöbszámtól pozitív) függvény. Ebben az esetben
f ∈ Θ(g) akkor és csak akkor teljesül8 , ha vannak és ϕ, ψ : N → R függvények, hogy ∀n ∈ N-re:
olyan
c, d > 0
konstansok
ϕ(n) ψ(n) = 0 ∧ lim =0 n→∞ g(n) n→∞ g(n)
c ∗ g(n) + ϕ(n) ≤ f (n) ≤ d ∗ g(n) + ψ(n) ∧ lim
8 Ez az állítás valójában a de níció egyik fontos következménye. Ld. b®vebben a 7. fejezetben!
13
öfRend(A[u..v], B[])
összefésül®_rendezés(A[1..n])
B[0..(b n2 c − 1)]
u
k :=
öfRend(A[(k
és
SKIP
összefésül(A[u..v], k, B[])
A[u..k]
+ 1)..v], B )
összefésül(A[u..v], k, B )
törlése, ha ez nem automatikus
//
c b u+v−1 2
öfRend(A[u..k], B )
létrehozása
öfRend(A[1..n], B )
B[]
A[(k + 1)..v]
rendezett összefésülése
A[u..v]-be
i := u..k B[i − u] := A[i] m := u i := k + 1 j := 0 vb := k − u i ≤ v ∧ j ≤ vb A[i] < B[j] A
A[m] := A[i]
A[m] := B[j] j := j + 1
i := i + 1 m := m + 1 j ≤ vb A[m] := B[j] m := m + 1 j := j + 1
El®ször az összefésül(A[u..v], k, B[]) eljárás m¶veletigényét határozzuk meg. Bevezetjük az
M Tmerge (n)
n = v−u+1
jelölést.
mTmerge (n)
az eljárás minimális,
a maximális m¶veletigénye, amiket most is az eljáráshívások +
a ciklusiterációk számával közelítünk. Most csak 1 eljáráshívás van + az 1. ciklus
bn/2c
bn/2c
elemet biztosan vissszamásoljuk az
iterációja + a 2.
Ha viszont a 2.
és a 3.
és 3.
ciklus iterációi:
A-ba,
a
B
ami legalább
vektorban lév®
bn/2c
iteráció.
ciklus mindegyik elemet átmásolja, az összesen a
n iteráció. Innét mTmerge (n) ≥ 1 + n2 + n2 ≥ n2 + n2 = n,
maximális
14
valamint
M Tmerge (n) ≤ 1 +
n 2
+n≤
n 2
+ n ≤ 2n − 1,
ahonnét
n ≤ mTmerge (n) ≤ M Tmerge (n) ≤ 2n − 1. mTmerge (n), M Tmerge (n) ∈ Θ(n)
(Innét
adódik.)
Most a rekurzív eljárás, az öfRend(A[u..v], B[]) m¶veletigényét határozzuk
mTms (n) és M Tms (n) Kezdjük az M Tms (n) fels®
meg. Jelölje sorban
a minimális és a maximális m¶-
veletigényét!
becslésével, majd folytatjuk az
mTms (n) alsó becslésével. Belátjuk, hogy nagyságrendben M Tms (n) legfeljebb n lg n -nel arányos, mTms (n) pedig legalább n lg n -nel arányos, ahonnét adódik, hogy mindkett®, és végs® soron az egész rendezés m¶veletigénye is
Θ(n lg n) M Tms (n)
nagyságrend¶. fels® becsléséhez el®ször a rekurzió legnagyobb mélységét számol-
juk ki. Világos, hogy a rekurzív hívások egy bináris fát alkotnak (ld. a 8. 0 fejezet bevezet® részét). A 0. szinten van a legküls® (1 = 2 db.) rekurzív hívás, ami a teljes, n hosszú tömbre vonatkozik. Feltéve, hogy n ≥ 2, az 1 1. szinten 2 = 2 rekurzív hívás van, amik bn/2c, illetve dn/2e hosszú töm2 bökre vonatkoznak. Feltéve, hogy n ≥ 4, a 2. szinten 4 = 2 rekurzív hívás
bbn/2c/2c, dbn/2c/2e, bdn/2e/2c, illetve ddn/2e/2e hosszú i i tömbökre vonatkoznak. Feltéve, hogy n ≥ 2 , az i-edik szinten 2 rekurzív i hívás van, és mindegyik közelít®leg n/2 hosszú tömbökre vonatkozik. A továbbiakban feltesszük, hogy n > 1 (hiszen nagy n-ekre érdekes M −1 a m¶veletigény). Az M = dlg ne jelöléssel 2 < n ≤ 2M . De niáljuk a F ele(n) = dn/2e függvényt! Ekkor ∀i ∈ 0..M -re, az i. rekurziós szini ten a leghosszabb részvektor, amire a rekurzív eljárást meghívjuk, F ele (n) M −i−1 hosszú, és 2 < F elei (n) ≤ 2M −i . Innét az M . rekurziós szinten lesz a
van, amik sorban
leghoszabb részvektor hossza 1, és legkés®bb itt minden ágon leáll a rekurzió. Most az
i
2
i.
rekurziós szinten (ahol
rekurzív öfRend hívás
gére adunk fels® becslést. hívásnak az
i.
i. Az
i ∈ 0..M )
végrehajtott, legfeljebb
szintre vonatkozó m¶veletigényeinek össze-
i.
szinten végrehajtott tetsz®leges öfRend
szintre vonatkozó m¶veletigénye alatt az eljáráshívás vég-
rehajtását értjük a benne szerepl® két rekurzív hívás nélkül, mert azokat már az
(i + 1).
rekurziós szint m¶veletigényénél vesszük gyelembe. Az
i.
j . öfRend hívásban az A vektor aktuális részvektoráli,j -vel jelölve, li,j > 1 esetén a rekurzív eljárás bal ága hajtódik végre, és M Tmerge (li,j ) ≤ 2li,j − 1, ahonnét az aktuális öfRend hívásnak az i. rekurziós szintre vonatkozó m¶veletigényére M Tms(i) (li,j ) ≤ 2li,j adódik. Ez a fels® becslés nyilván li,j = 1 esetén is igaz, hiszen ekkor az öfRend eljárás jobboldali ága hajtódik végre, és M Tms(i) (li,j ) = 1. Az szinten végrehajtott
nak hosszát
15
i.
hi (hi ≤ 2i )!
szinten végrehajtott öfRend hívások számát jelölje
Az
i. szinten végrehajtott öfRend hívást tekintve, a teljes m¶Phi Phi veletigény M Tms(i) (n) ≤ j=1 2li,j = 2 j=1 li,j ≤ 2n, hiszen az i. szinten az li,j hosszú részvektorok az eredeti A[1..n] vektor diszjunkt szakaszait képezik. Mivel 0-tól M = dlg ne -ig M = dlg ne + 1 rekurziós szint van, M Tms (n) ≤ 2n(dlg ne + 1) ≤ 2n((lg n) + 2) = 2n lg n + 4n, azaz összes, az
M Tms (n) ≤ 2n lg n + 4n Az
mTms (n)
alsó becsléshez csak a rendezett összefésülések m¶veletigényei
összegének alsó becslését vesszük gyelembe.
Ehhez meghatározzuk, hogy
a rekurzív hívásokban milyen mélységig lesz az adott rekurzív hívásban
i.
szinten minden
li,j > 1,
mert ezeken a szinteken minden rekurzív híPhi j=1 li,j = n, így az összefésülések Phi összes m¶veletigényére az i. szinten mTmerge(i) (n) ≥ j=1 li,j = n, ahonnét mTms(i) (n) ≥ mTmerge(i) (n) ≥ n adódik.
vásban meghívódik az összefésülés, és
A fenti kritikus mélység meghatározásához, az m = blg nc jelöléssel m+1 2 > n ≥ 2m . A f ele(n) = bn/2c függvénnyel kapjuk, hogy ∀i ∈ 0..m -re m+1−i 2 > f elei (n) ≥ 2m−i , ahol f elei (n) az li,j részvektor-hosszok minimuma. 2 m−1 Ebb®l 2 > f ele (n) ≥ 2; továbbá 2 > f elem (n) ≥ 1, azaz f elem (n) =
1.
Innét adódik, hogy
∀i ∈ 0..(m − 1)-re
az
i.
szinten minden rekurzív
hívásban legalább 2 hosszú a rendezend® részvektor, és így azaz
mTms (n) ≥ nm = nblg nc ≥ n((lg n) − 1) = n lg n − n.
mTms(i) (n) ≥ n, Ahonnét
mTms (n) ≥ n lg n − n. Ebb®l a teljes rendezésre, ami a rekurzív öfRend eljáráshoz képest pontosan egy többlet eljáráshívást tartalmaz, azt kapjuk, hogy
n lg n − n ≤ mTM S (n) ≤ ATM S (n) ≤ M TM S (n) ≤ 2n lg n + 4n + 1 Tekintetbe véve, hogy
−n =0 n→∞ n lg n lim
∧
4n + 1 = 0, n→∞ n lg n lim
a fenti struktogramok el®tti állítással kapjuk, hogy
mTM S (n), ATM S (n), M TM S (n) ∈ Θ(n lg n).
16
5.
Láncolt listák
5.1.
Egyirányú láncolt listák
(egyszer¶ listák (EL) és fejelemes listák (FL)) Az egyirányú láncolt listák elemeinek osztálya (az egyszer¶ség kedvéért):
Elem +kulcs : valamilyen +mut : Elem*
ismert típus
fv EL_hossza(L)
n := 0 p := L p 6=
n := n + 1 p := p → mut
fv FL_hossza(F )
return EL_hossza(F → mut)
return n
A különböz® listam¶veleteknél a listaelemekben lev® kulcsok (és az esetleges egyéb járulékos adatok) listaelemek közti mozgatását kerüljük. El®nyben részesítjük a listák megfelel® átláncolását, mivel
nem
tudjuk,
hogy egy gyakorlati alkalmazásban mennyi járulékos adatot tartalmaznak az egyes listaelemek.
mögé(p, q )
mögül(p, &q )
q := p → mut p → mut := q → mut
q → mut := p → mut p → mut := q
[q → mut := ]
17
szétvág(L, n1, &L2)
p := L n1 > 1 n1 := n1 − 1 p := p → mut
F := v := new
Elem
v := v → mut := new Elem beolvas(v → kulcs) v → mut :=
Az objektumok dinamikus létrehozására a
T
van még beolvasandó adat
L2 := p → mut p → mut := ami egy
FL_beolvasása(&F )
new T
m¶veletet fogjuk használni,
típusú objektumot hoz létre és visszadja a címét. Ezért tudunk
egy vagy több mutatóval hivatkozni a frissen létrehozott objektumra. Az objektumok dinamikus létrehozása egy speciálisan a dinamikus helyfoglalásra fenntartott memóriaszegmens szabad területének rovására történik. Fontos ezért, hogy ha már egy objektumot nem használunk, a memória neki megfelel® darabja visszakerüljön a szabad memóriához. Erre fogjuk használni a
delete p utasítást, ami a p mutató által hivatkozott objektumot törli. Maga a p mutató a p := new T utasítás végrehajtása el®tt is létezik, mert azt a mutató deklarációjának kiértékelése hozza létre. mutató a
9
Ugyanígy, a
p
delete p végrehajtása után is létezik, egészen az ®t (automatikusan)
deklaráló eljárás vagy függvény végrehajtásának befejezéséig. Mi magunk is írhatunk optimalizált, hatékony dinamikus memória helyfoglaló és felszabadító rutinokat; speciális esetekben akár úgy is, hogy a fenti m¶veletek konstans id®t igényelnek. (Erre egy példa a gyakorlatokon is elhangzik.) Általános esetben azonban a dinamikus helyfoglalásra használt szabad memória a különböz® típusú és méret¶ objektumokra vonatkozó létrehozások és törlések (itt
new és delete utasítások) hatására feldarabolódik, és vi-
szonylag bonyolult könyvelést igényel, ha a feldarabolódásnak gátat akarunk vetni.
Ezt a problémát a különböz® rendszerek különböz® hatékonysággal
kezelik. Az absztrakt programokban az objektumokat dinamikusan létrehozó
new)
(
azaz
delete)
és törl® (
Θ(1)-nek
utasítások m¶veletigényeit konstans értékeknek,
vesszük, azzal a megjegyzéssel, hogy valójában nem tudjuk,
mennyi. Ezért a lehet® legkevesebbet használjuk a
new és a delete utasítá-
sokat.
9 Az absztrakt programokban (struktogram, pszeudokód) automatikus deklarációt feltételezünk: az eljárás vagy függvény meghívásakor az összes benne használt lokális változó és formális paraméter automatikusan deklarálódik (egy változó alapértelmezésben lokális).
18
FL_beszúró_rendezése(F )
r := F → mut r 6=
A
s := r → mut s 6=
A
r → kulcs ≤ s → kulcs
r → mut := s → mut p := F ; q := F → mut
SKIP
q → kulcs ≤ s → kulcs p := q ; q := q → mut
r := s
s → mut := q ; p → mut := s s := r → mut
ELöfR(&L, n)
A EL_összefésül®_rendezése(&L)
n :=
n>1 n1 := b n2 c
szétvág(L, n1, L2)
ELöfR(L, n1)
EL_hossza(L)
ELöfR(L2, n
ELöfR(L, n)
− n1)
összefésül(L, L2)
19
SKIP
összefésül(&L, L2)
A
L → kulcs ≤ L2 → kulcs p := L2 ; L2 := L2 → mut p := L q := L q := L → mut p → mut := q ; L := p q 6= ∧ L2 6= q → kulcs ≤ L2 → kulcs A r := L2 ; L2 := L2 → mut p := q r → mut := q ; p → mut := r q := q → mut p := r
A
5.2.
L2 6=
p → mut := L2
SKIP
Kétirányú ciklikus láncolt listák (KCL)
A KCL-ek elemeinek osztálya:
Elem2 −bmut, jmut : a bal illetve a jobb szomszédra mutat vagy this +kulcs : valamilyen ismert típus + Elem2() { bmut := jmut := this } // egyelem¶ KCL-t képez + ∼ Elem2() törlés el®tt kif¶zi + kif¶z() // kif¶zi és egyelem¶ KCL-t képez bel®le + balra(q ) // átf¶zi a ∗q KCL elemt®l balra + jobbra(q ) // átf¶zi a ∗q KCL elemt®l jobbra + fv bal() { return bmut } // a bal szomszédja címe + fv jobb() { return jmut } // a jobb szomszédja címe
Elem2::∼Elem2()
bel®le
Elem2::kif¶z
bmut → jmut := jmut jmut → bmut := bmut
bmut → jmut := jmut jmut → bmut := bmut
bmut := jmut :=
bmut := jmut := this
20
Elem2::balra(q )
Elem2::jobbra(q )
kif¶z()
kif¶z()
p := q → bmut
p := q → jmut
bmut := p ; jmut := q
jmut := p ; bmut := q
p → jmut := q → bmut := this
p → bmut := q → jmut := this
5.2.1.
Fejelemes, kétirányú ciklikus láncolt listák (FKCL), mint a KCL-ek speciális esete
FKCL_beolvasása(&F )
F := new
Elem2
van még beolvasandó adat
p := new beolvas(p
p→
Elem2
→ kulcs)
balra(F )
FKCL_beszúró_rendezése(F )
r := F →
s := r →
jobb() ;
jobb()
s 6= F r → kulcs ≤ s → kulcs p := r → bal()
A
r := s
p 6= F ∧ p → kulcs > s → kulcs p := p → bal() s → jobbra(p) s := r → jobb()
6. 6.1.
Absztrakt adattípusok (ADT-k) Vermek
A vermet most statikus tömb (A[1..n]
n
a verem maximális mérete,
T
: T)
segítségével reprezentáljuk, ahol
a verem elemeinek típusa.
21
Verem A[1..n] : T // T ismert típus, n globális konstans - m : 0..n // m a verem aktuális mérete + Verem() {m := 0} // üresre inicializálja a vermet -
// destruktort itt nem kell de niálni
+ + + + +
verembe(x) // beteszi
x-et
a verembe, felülre
fv veremb®l() // kiveszi és visszaadja a verem fels® elemét fv tet®() // megnézi és visszaadja a verem fels® elemét fv tele_e(){return m = n} fv üres_e(){return m = 0}
Verem::verembe(x)
m
m := m + 1 A[m] := x
fv Verem::veremb®l() A
HIBA ("Tele van a verem.")
fv Verem::tet®()
m>0
m := m − 1 return A[m + 1]
HIBA
return A[m]
("Üres a verem.")
m>0
A
HIBA
("Üres a verem.")
Példa a verem egyszer¶ használatára a gyakorlat anyagából: Az input adatok kiírása fordított sorrendben. (A vermet az alábbi struktogramban szokások ellenére azért deklaráltuk, hogy jelezzük: üresre inicializáltuk. Az egyszer¶ség kedvéért feltesszük, hogy a verem elég nagy a teljes input befogadásához.)
megfordít()
v:
Verem
van még beolvasandó adat
v .verembe(beolvas()) ¬v .üres_e() kiír(v .veremb®l())
22
6.2.
Absztrakt adattípusok (ADT-k): sorok
A sort statikus tömb (A[0..n
− 1] : T )
globális konstans a sor zikai mérete,
segítségével reprezentáljuk, ahol az
T
n
a sor elemeinek típusa.
Sor −A[0..n − 1] : T −m : 0..n // m a sor aktuális mérete −k : 0..n − 1 // k a sor kezd® pozíciója az A tömbben + Sor(){ m:=0 ; k := 0 } // üresre inicializálja a sort + sorba(x) // beteszi x-et a sor végére + fv sorból() // kiveszi és visszaadja a sor els® elemét + fv els®() // megnézi és visszaadja a sor els® elemét + fv hossz(){return m} + fv üres_e(){return m = 0}
Sor::sorba(x)
m
A[(k + m) mod n] := x
HIBA
m := m + 1
("Tele van a sor.")
fv Sor::sorból() A
m>0 m := m − 1 i := k k := (k + 1) mod n
return A[i] 6.2.1.
fv Sor::els®()
HIBA ("Üres
A
m>0
return A[k]
a sor.")
HIBA
("Üres a sor.")
Sor reprezentálása dinamikus tömbbel* := new T [0..n − 1]) segítségével n a sor zikai mérete, T a sor elemeinek típusa. Ha nincs a new m¶velet -t ad vissza. (A konstruktor paramétere a ha kés®bb az s.sorba(x) m¶velettel a tömb betelik, kétszer
A sort dinamikusan létrehozott tömb (A reprezentáljuk, ahol elég memória, kezd®méret, s
akkorát foglalunk, és az adatokat átmásoljuk.)
23
Sor −A : T ∗ // a konstruktor létrehozza az A[0..n − 1] : T tömböt −n : 1.. // n a sor zikai mérete −m : 0..n // m a sor aktuális mérete −k : 0..n − 1 // k a sor kezd® pozíciója az A tömbben + Sor(n0) // üresre inicializálja a sort n0 zikai mérettel + ∼ Sor() {delete A} + üresSor(){m := 0 ; k := 0} // kiüríti a sort + sorba(x) // beteszi x-et a sor végére + fv sorból() // kiveszi és visszaadja a sor els® elemét + fv els®() // megnézi és visszaadja a sor els® elemét + fv hossz(){return m} + fv üres_e(){return m = 0}
Sor::Sor(n0)
A := new T [0..n0 − 1] A=
A HIBA
("Nincs elég szabad memória.")
n := n0 ; m := 0 ; k := 0
Sor::sorba(x)
m
A
B 6=
A
A[(k + m) mod n] := x
i := k ; j := 0 j<m
B[j] := A[i] i := (i + 1) mod n j := j + 1 m := m + 1
delete A ; A := B n := 2n ; k := 0 A[m] := x ; m := m + 1
24
HIBA ("Nincs elég szabad memória.")
fv Sor::sorból()
m>0 m := m − 1
A
i := k k := (k + 1) mod n
return A[i]
fv Sor::els®()
HIBA ("Üres
m>0
A
HIBA
return A[k]
a sor.")
("Üres a sor.")
HF: A vermet hasonlóan átírni.
6.3.
Absztrakt adattípusok (ADT-k): Els®bbségi (prioritásos) sorok
PrSor A[1..n] : T // T ismert típus, n globális konstans - m : 0..n // m a PrSor aktuális mérete + PrSor() {m := 0} // üresre inicializálja a PrSort -
// destruktort itt nem kell de niálni
+ + + + +
prSorba(x) // beteszi
x-et
a prSorba
fv maxKivesz() // kiveszi és visszaadja a PrSor maximális elemét fv max() // megnézi és visszaadja a PrSor maximális elemét fv tele_e(){return m = n} fv üres_e(){return m = 0}
A PrSor aktuális elemeit az
6.3.1.
A[1..m]
résztömb tartalmazza.
A[1..m] rendezetlen
TprSorba (m) ∈ Θ(1), TmaxKivesz (m) ∈ Θ(m), Tmax (m) ∈ Θ(m):
PrSor::prSorba(x)
m
m := m + 1 A[m] := x
HIBA ("Tele van a PrSor.")
25
fv PrSor::maxKivesz() A
m>0 maxi := maxiKer(A[1..m])
x := A[maxi] HIBA
A[maxi] := A[m]
("Üres a PrSor.")
m := m − 1
return x
fv PrSor::max() A
m>0 maxi := maxiKer(A[1..m]) return A[maxi]
HIBA
("Üres a PrSor.")
fv maxiKer(A[1..m])
maxi := 1 ; i := 2 i≤m A[i] > A[maxi] A
maxi := i SKIP i := i + 1
return maxi HF: Lássuk be, hogy elérhet®
TmaxKivesz (m) ∈ Θ(m)
Tmax (m) ∈ Θ(1),
míg
TprSorba (m) ∈ Θ(1)
és
marad! Módosítsuk a PrSor osztályt ennek megfele-
l®en! (Ötlet: vegyünk fel egy új, privát adattagot az osztályba, ami nemüres prioritásos sor esetén a legnagyobb elem indexe. Módosítsuk ennek megfelel®en a metódusokat!)
6.3.2.
A[1..m] monoton növekv®en rendezett
M TprSorba (m), ATprSorba (m) ∈ Θ(m); mTprSorba (m) ∈ Θ(1) TmaxKivesz (m) ∈ Θ(1), Tmax (m) ∈ Θ(1):
26
PrSor::prSorba(x)
m
i := m i > 0 ∧ A[i] > x A[i + 1] := A[i]
HIBA ("Tele van a PrSor.")
i := i − 1 A[i + 1] := x m := m + 1
m := m − 1 return A[m + 1]
fv PrSor::max()
m>0
A
fv PrSor::maxKivesz()
HIBA
m>0
A
return A[m]
("Üres a PrSor.")
HIBA
("Üres a PrSor.")
Vegyük észre, hogy -
ha A[1..m] rendezetlen,
a prSorba(x) eljárás megfelel a Verem típus
verembe(x) metódusának, míg -
ha A[1..m] rendezett, a maxKivesz() és a max() tagfüggvények az ottani
veremb®l() illetve tet®() m¶veletek hasonmásai. A "régi" m¶veletek így
Θ(1)
id®ben futnak. Az "újak" viszont lineáris m¶-
veletigény¶ek, ezért hatékonyabb megoldást keresünk.
7.
Függvények aszimptotikus viselkedése (a Θ, O, Ω, o, ω matematikája)
E fejezet célja, hogy tisztázza a programok hatékonyságának nagyságrendjeivel kapcsolatos alapvet® fogalmakat, és az ezekhez kapcsolódó függvényosztályok legfontosabb tulajdonságait.
7.1 De níció teljesül, ha
Valamely
P (n) tulajdonság elég nagy n -ekre pontosan akkor ∃N ∈ N, hogy ∀n ≥ N -re igaz P (n).
7.2 De níció ha elég nagy
Az f AN (aszimptotikusan n-ekre f (n) ≥ 0.
27
nemnegatív) függvény,
7.3 De níció ha elég nagy
Az f AP (aszimptotikusan n-ekre f (n) > 0.
pozitív) függvény,
Egy tetsz®leges helyes program futási ideje és tárigénye is nyilvánvalóan, tetsz®leges megfelel® mértékbegységben (másodperc, perc, Mbyte stb.) mérve pozitív számérték. Amikor (alsó és/vagy fels®) becsléseket végzünk a futási id®re vagy a tárigényre, legtöbbször az input adatszerkezetek méretének
10
függvényében végezzük a becsléseket. Így a becsléseket leíró függvények ter-
N → R
mészetesen
típusúak.
Megkövetelhetnénk, hogy
N → P
típusúak
legyenek, de annak érdekében, hogy képleteink minél egyszer¶bbek legyenek, általában megelégszünk azzal, hogy a becsléseket leíró függvények aszimptotikusan nemnegatívak, esetleg aszimptotikusan pozitívak legyenek.
7.4 Jelölések:
Az f, g, h latin bet¶kr®l ebben a fejezetben feltesszük, hogy N → R típusú, aszimptotikusan nemnegatív (AN) függvényeket jelölnek, míg a ϕ, ψ görög bet¶kr®l csak azt tesszük fel, hogy N → R típusú függvényeket
jelölnek.
7.5 De níció
Az
O(g)
függvényhalmaz olyan
függvényekb®l áll, amiket
f
elég nagy
n helyettesítési értékekre, megfelelel® pozitív konstans szorzóval jól becsül felülr®l a g függvény: O(g) = {f : ∃d ∈ P, hogy elég nagy n -ekre d ∗ g(n) ≥ f (n).}
7.6 De níció
Az
Ω(g)
függvényhalmaz olyan
függvényekb®l áll, amiket
f
elég nagy
n helyettesítési értékekre, megfelelel® pozitív konstans szorzóval jól g függvény: Ω(g) = {f : ∃c ∈ P, hogy elég nagy n -ekre c ∗ g(n) ≤ f (n).} becsül alulról a
7.7 De níció elég nagy
n
A
Θ(g)
függvényhalmaz olyan
f
függvényekb®l áll, amiket
helyettesítési értékekre, megfelelel® pozitív konstans szorzókkal
alulról és felülr®l is jól becsül a
Θ(g) = {f : ∃c, d ∈ P, .
g
függvény:
hogy elég nagy n -ekre c ∗ g(n) ≤ f (n) ≤ d ∗ g(n).}
7.8 Tulajdonság Θ(g) = O(g) ∩ Ω(g)
7.9 Tétel
Ha
f AN, g pedig AP függvény, akkor f ∈ O(g) ⇐⇒ ∃d ∈ P és ψ , hogy ∀n ∈ N -re d ∗ g(n) + ψ(n) ≥ f (n)
∧
ψ(n) =0 n→∞ g(n) lim
10 vektor mérete, láncolt lista hossza, fa csúcsainak száma stb.
28
7.10 Tétel
Ha f AN, g pedig AP függvény, akkor f ∈ Ω(g) ⇐⇒ ∃c ∈ P és ϕ, hogy ∀n ∈ N -re
c ∗ g(n) + ϕ(n) ≤ f (n)
∧
lim
n→∞
ϕ(n) =0 g(n)
7.11 Tétel
Ha f AN, g pedig AP függvény, akkor f ∈ Θ(g) ⇐⇒ ∃c, d ∈ P és ϕ, ψ , hogy ∀n ∈ N -re
c ∗ g(n) + ϕ(n) ≤ f (n) ≤ d ∗ g(n) + ψ(n) ∧ ϕ(n) =0 n→∞ g(n) lim
∧
ψ(n) =0 n→∞ g(n) lim
Ld. még ezzel kapcsolatban az alábbi címen az 1.3. alfejezetet! [4]
8.
Fák, bináris fák
Megállapítottuk, hogy a prioritásos sorok rendezetlen és rendezett tömbös reprezentációjával is lesz olyan m¶velet, ami lineáris m¶veletigény¶, hiszen rendezetlen tömb esetén a maxKivesz() megvalósításához maximumkeresés, rendezett tömb esetén a pedig a prSorba(x) implementációjához rendezett beszúrás szükséges. HF: (1) Igazoljuk, hogy a láncolt listás reprezentációk esetén hasonló eredményekre juthatunk! (2) Vegyük észre, hogy egy apró ötlettel a max() függvény m¶veletigényét rendezetlen tömb illetve lista esetén is
Θ(1)-re csök-
kenthetjük! (A maximum helyét folyamatosan tartsuk nyilván!) Bináris fák segítségével viszont elérhetjük, hogy a maxKivesz() és a prSorba(x) metódusok maximális futási ideje
Θ(1)
Θ(lg n), a többi m¶veleté pedig
legyen.
Az egydimenziós tömbök és a láncolt listák esetében minden adatelemnek legfeljebb egy rákövetkez®je van, azaz az adatelemek lineárisan kapcsolódnak egymáshoz a következ® séma szerint: OOOOO
bináris fák esetében minden adatelemnek vagy szokásos nevén csúcsnak legfeljebb kett® rákövetkez®je van: egy bal és/vagy egy jobb rákövetkez®je. Ezeket a csúcs gyerekeinek nevezzük. A csúcs a gyerekei szül®je, ezek pedig egymás testvérei. Ha egy csúcsnak nincs gyereke, levélnek hívjuk, ha pedig nincs szül®je, gyökér csúcsnak nevezzük. Bels® csúcs alatt nem-levél A
29
csúcsot értünk.
A fában egy csúcs leszármazottai a gyerekei és a gyerekei
leszármazottai. Hasonlóan, egy csúcs ®sei a szül®je és a szül®je ®sei. A fákat felülr®l lefelé szokás lerajzolni: fent van a gyökér, lent a levelek. Egyszer¶ bináris fák:
O Az
O / \
O
O
Ω üres fának
/
O
O \
O
O
nincs csúcsa. Egy tetsz®leges nemüres
t
fát a gyökércsúcsa
(∗t) határoz meg, mivel ennek a fa többi csúcsa a leszármazottja.
t bal/jobb részfájának nevezzük. Jelölése t → bal illetve t → jobb (szokás a bal(t) és jobb(t) jelölés is). Ha ∗t-nek nincs bal/jobb gyereke, akkor t → bal = Ω illetve t → jobb = Ω. Ha a gyerek létezik, jelölése ∗t → bal illetve ∗t → jobb. A t bináris fának (t = Ω esetén is) részfája önmaga. Ha t 6= Ω, részfái még a t → bal és a t → jobb részfái is. A t valódi részfája f , ha t részfája f , és t 6= f 6= Ω. A ∗t-ben tárolt kulcs jelölése t → kulcs (illetve kulcs(t)). A
∗t
bal/jobb gyerekéhez tartozó fát a
Megjegyezzzük, hogy a gyakorlatban ugyanúgy, mint a tömbök és a láncolt listák elemeinél a kulcs általában csak a csúcsban tárolt adat egy kis része, vagy abból egy függvény segítségével számítható ki. Mi az egyszer¶ség kedvéért úgy tekintjük, mintha a kulcs az egész adat lenne, mert az adatszerkezetek m¶veleteinek lényegét így is be tudjuk mutatni.
∗g → sz , és a szül®jéhez, mint gyökércsúcshoz tartozó fa a g → sz (illetve sz(g)). Ha ∗g a teljes fa gyökere, azaz nincs szül®je, akkor g → sz = Ω. Ha
∗g
egy fa egy csúcsa, akkor a szül®je a
A bináris fa fogalma általánosítható. Ha a fában egy tetsz®leges csúcsnak legfeljebb
r
rákövetkez®je van,
r-áris fáról beszélünk. Egy csúcs gyerekeit és 0..r − 1 szelektorokkal szokás sorszá-
a hozzájuk tartozó részfákat ilyenkor a mozni. Ha egy csúcsnak nincs részfa üres. Így tehát a bináris fa és a hogy itt a
bal ∼ 0
és a
Beszélhetünk a fa
gyereke (i
2-áris
fa lényegében ugyanazt jelenti, azzal,
jobb ∼ 1
szintjeir®l.
szint¶ csúcsok gyerekeit az
∈ 0..r − 1),
i-edik
i-edik
szelektor-megfeleltetést alkalmazzuk. A gyökér van a
(i + 1)-edik
nulladik
Így tetsz®leges nemüres
t
szinten. Az
szinten találjuk.
egyenl® a legmélyebben fekv® levelei szintszámával.
h(Ω) = −1.
akkor az
i-edik
A fa magassága
Az üres fa magassága
bináris fára:
h(t) = 1 + max(h(t → bal), h(t → jobb)) Az itt tárgyalt fákat
gyökeres fáknak
is nevezik, mert tekinthet®k olyan irá-
nyított gráfoknak, amiknek az élei a gyökércsúcstól a levelek felé vannak
30
irányítva, a gyökérb®l minden csúcs pontosan egy úton érhet® el, és valamely
r ∈ N-re
tetsz®leges csúcs kimen® élei a
maza elemeivel egyértelm¶en
11
0..r − 1
szelektorok egy részhal-
van címkézve. (Ezzel szemben a szabad fák
összefügg®, körmentes irányítatlan gráfok.)
8.1.
(Bináris) fák bejárásai
A (bináris) fákkal dolgozó programok gyakran kapcsolódnak a négy klasszikus bejárás némelyikéhez, amelyek adott sorrend szerint bejárják a fa csúcsait, és minden csúcsra ugyanazt a m¶veletet hívják meg, amivel kapcsolatban megköveteljük, hogy futási ideje m¶velet is lehet). A
∗f
Θ(1)
legyen (ami ett®l még persze összetett
f → kulcs kiíratása. Nemüres r -áris fákra
csúcs feldolgozása lehet például
Üres fára mindegyik bejárás az üres program.
- a
preorder bejárás el®ször a fa gyökerét dolgozza fel, majd sorban bejárja a
0..r − 1-edik - a
postorder
részfákat; bejárás el®bb sorban bejárja a
0..r − 1-edik
részfákat, és a fa
gyökerét csak a részfák után dolgozza fel; - az
inorder
bejárás el®ször bejárja a
dolgozza fel, majd sorban bejárja az
nulladik
részfát, ezután a fa gyökerét
1..r − 1-edik
részfákat;
- a szintfolytonos bejárás a csúcsokat a gyökért®l kezdve szintenként, minden szintet balról jobbra bejárva dolgozza fel. Az els® három bejárás tehát nagyon hasonlít egymásra.
Nevük megsúgja,
hogy a gyökércsúcsot a részfákhoz képest mikor dolgozzák fel. Bináris fákra
preorder(t)
A
preorder(t
→ bal)
inorder(t)
t 6= Ω feldolgoz(t) preorder(t
A
→ jobb)
inorder(t
:
t 6= Ω inorder(t → bal ) feldolgoz(t)
SKIP
12
SKIP
→ jobb)
11 Az egyértelm¶ség itt azt jelenti, hogy egyetlen csúcsnak sincs két azonos címkéj¶ kimen® éle.
12 A struktogramokban a ∗t csúcs feldolgozását feldolgoz(t) jelöli.
31
szintfolytonos(t)
A
s:
Sor ;
t 6= Ω s.sorba(t)
¬s.üres_e() postorder(t)
f := s.sorból()
feldolgoz(f )
t 6= Ω A
→ bal) postorder(t → jobb)
SKIP
f → bal 6= Ω
A
postorder(t
SKIP
feldolgoz(t)
s.sorba(f → bal)
SKIP
f → jobb 6= Ω s.sorba(f → jobb) SKIP
A
Állítás: Tpreorder (n), Tinorder (n), Tpostorder (n), Tszintfolytonos (n) ∈ Θ(n), ahol n a fa mérete, azaz csúcsainak száma. Igazolás: Az els® három bejárás pontosan annyiszor hívódik meg, amennyi részfája van az eredeti bináris fának (az üres részfákat is beleszámolva), és egy-egy hívás végrehajtása
Θ(1)
futási id®t igényel. Másrészt
szerinti teljes indukcióval könyen belátható, hogy tetsz®leges fának
2n + 1
n
n csúcsú bináris
részfája van. A szintfolytonos bejárás pedig mindegyik csúcsot
a ciklus egy-egy végrehajtásával dolgozza fel. A szintfolytonos bejárás helyessége azon alapszik, hogy egy fa csúcsainak szintfolytonos felsorolásában a korábbi csúcs gyerekei megel®zik a kés®bbi csúcs gyerekeit. Ez az állítás nyilvánvaló, akár egy szinten, akár különböz® szinten van a két csúcs a fában. A preorder és az inorder bejárások hatékonységa konstans szorzóval javít-
t érték módú formális [Általában nem célszer¶
ható, ha a végrekurziókat ciklussá alakítjuk. (Mivel a paraméter, az aktuális paraméter nem változik meg.
a referencia módú formális paramétereket ciklusváltozóként vagy segédváltozóként használni.] )
preorder(t)
inorder(t)
t 6= Ω
t 6= Ω inorder(t → bal )
feldolgoz(t) preorder(t
→ bal)
feldolgoz(t)
t := t → jobb
t := t → jobb
32
8.1.1.
Fabejárások alkalmazása: bináris fa magassága
Természetesen az a legegyszer¶bb, ha a de níciót kódoljuk le:
fv h(t) t 6= Ω return 1+max(h(t → bal),h(t → jobb))
A
return −1
Mint látható, ez lényegében véve egy függvényként kódolt postorder bejárás.
13
Talán els®re meglep®, de ezt a feladatot preorder bejárással is könnyen
megoldhatjuk. Mint a legtöbb rekurzív programnál, itt is lesz egy nemrekurzív keret, ami el®készíti a legküls® rekurzív hívást, s a végén is biztosítja a megfelel® interfészt. Lesz két extra paraméterünk. Az egyik (sz ) azt tárolja, milyen mélyen (azaz hányadik szinten) járunk a fában. A másik (m) pedig azt, hogy mi a legmélyebb szint, ahol eddig jártunk.
Ezután már csak a
14
bejárás és a maximumkeresés összefésülésére van szükség.
preorder_h(t, sz, &m)
t 6= Ω
fv h(t)
m := sz := −1 preorder_h(t, sz, m)
sz := sz + 1 sz > m A m := sz SKIP preorder_h(t
return m 8.2.
→ bal, sz, m)
t := t → jobb
Bináris fák reprezentációi: láncolt ábrázolás
A legtermészetesebb és az egyik leggyakrabban használt a
lás.
Az
Ω
(üres fa) reprezentációja a
láncolt ábrázo-
(NIL). A bináris fa csúcsait pl. az
alábbi osztály objektumaiként ábrázolhatjuk.
13 Azért csak lényegében véve, mert a részfák bejárásának sorrendje a max() függvény paramétereinek kiértékelési sorrendjét®l függ, és az eljárások, függvények aktuális paramétereinek kiértékelési sorrendjét általában nem ismerjük.
14 Így a végrehajtáshoz csak egy függvényhívásra,
iterációra lesz szükség, míg az el®bbi esetben
n + 1 eljáráshívásra és n ciklus2n + 1 függvényhívásra, ha a max() függvény
hívásait nem számítjuk (ami könnyen kibontható egy szekvencia + elágazássá). Mivel egy ciklus-iteráció a gyakorlatban gyorsabb, mint egy rekurzív hívás, a preoder magasság számítás a gyorsabb.
33
Csúcs + kulcs : T // T valamilyen ismert típus + bal, jobb : Csúcs* + Csúcs() { bal := jobb := } // egycsúcsú fát + Csúcs(x:T) { bal := jobb := ; kulcs := x } Néha hasznos, ha a csúcsokban van egy
sz
képez bel®le
szül® pointer is, mert a fában így
felfelé is tudunk haladni:
Csúcs3 + kulcs : T // T valamilyen ismert típus + bal, jobb, sz : Csúcs3* + Csúcs3(p:Csúcs3*) { bal := jobb := ; sz := p } // egy levelet hoz + Csúcs3(x:T, p:Csúcs3*) { bal := jobb := ; sz := p ; kulcs := x }
létre
El®fordul például olyan alkalmazás, ahol szükségünk van a bináris fában egy
p
: Csúcs3* pointer által mutatott csúcs (p
rákövetkez®jének címére. vissza. Nyilván
6= )
inorder bejárás szerinti
Ha nincs ilyen rákövetkez®, a függvény
M T (h(t)) ∈ O(h(t)),
ahol
t
a
∗p
-t
ad
csúcsot tartalmazó bináris
fa.
fv inorder_ráköv(p)
A
q → bal 6=
q := p → jobb q 6=
q := p → sz
q 6= ∧ q → bal 6= p p := q ; q := q → sz
q := q → bal
return q HF: Írjuk meg az inorder_megel(p) függvényt, ami a szerinti megel®z®jét adja vissza; ha nincs ilyen, maximális m¶veletigényt!
8.3.
-t!
∗p csúcs inorder bejárás Tartsuk meg az O(h(t))
Speciális bináris fák, kupacok
Azokat a bináris fákat, amelyekben minden bels® (azaz nem-levél) csúcsnak
szigorúan bináris fáknak nevezzük. azonos szinten van, teljes bináris fákról
két gyereke van,
Ha ez utóbbiaknak min-
den levele
beszélünk.
34
(Ilyenkor az
összes levél szükségszer¶en a fa legmélyebb szintjén található, a fels®bb szinteken lev® csúcsok pedig bels® csúcsok, így két-két gyerekük van.) Tetsz®leges h mélység¶ teljes bináris fa csúcsainak száma tehát 1+2+4+...+2h = 2h+1 −1. Ha egy teljes bináris fa levélszintjér®l nulla, egy vagy több levelet elveszünk, de nem az összeset, az eredményt
majdnem teljes bináris fának
ne-
vezzük. Tetsz®leges h mélység¶, majdnem teljes bináris fa csúcsainak száma h h+1 ezért n ∈ 2 ..2 − 1, és így h = blg nc. Az alsó szinten lev® leveleket elvéve pedig egy
h−1
mélység¶ teljes bináris fát kapunk.
HF: Egy bináris fa
méret szerint kiegyensúlyozott,
ha tetsz®leges nemüres
részfája bal és jobb részfájának mérete legfeljebb eggyel térhet el. Bizonyítsuk be, hogy a méret szerint kiegyensúlyozott bináris fák halmaza a majdnem teljes bináris fák halmazának valódi részhalmaza! Egy majdnem teljes bináris fa
balra tömörített, ha az alsó szintjén egyetlen le-
vélt®l balra sem lehet új levelet beszúrni. Ez azt jelenti, hogy egy vele azonos mélység¶ teljes bináris fával összehasonlítva csak az alsó szint jobb szélér®l hiányozhatnak csúcsok (de a bal széls® csúcs kivételével akár az összes többi csúcs is hiányozhat). Eszerint bármely balra tömörített, majdnem teljes bináris fa alsó szintje fölötti szintjének bal szélét®l egy vagy több bels® csúcsot találunk, amelyeknek a jobb széls® kivételével biztosan két-két gyereke van. Ha a jobb széls® bels® csúcsnak csak egy gyereke van, akkor ez bal gyerek. A szint jobb szélén lehetnek levelek. A magasabb szinteken minden csúcsnak két gyereke van. Egy balra tömörített, majdnem teljes bináris fát
maximum-kupacnak (heap)
nevezünk, ha minden bels® csúcs kulcsa nagyobb-egyenl®, mint a gyerekeié. Ha minden bels® csúcs kulcsa kisebb-egyenl®, mint a gyerekeié,
kupacról beszélünk.
Ebben a félévben
minimum-
kupac alatt maximum-kupacot értünk.
Vegyük észre, hogy bármely nemüres kupac maximuma a gyökércsúcsában mindig megtalálható, minimuma ugyanígy a levelei között, továbbá a kupac részfái is mindig kupacok. Egy kupac bal- és jobboldali részfájában lev® kulcsok között viszont nincs semmi nagyságrendi kapcsolat. Az els®bbségi (prioritásos) sorokat általában kupacok segítségével ábrázoljuk. Egy balra tömörített, majdnem teljes bináris fát
lyukas kupacnak
nevezünk,
ha a fa egyik csúcsa a lyuk, és minden szül®-gyerek párosban a szül® kulcsa nagyobb-egyenl®, mint a gyereke kulcsa, kivéve, ha a páros egyik tagja maga a lyuk. A lyuk kulcsa nemde niált, de ha a lyuknak van szül®je, akkor annak kulcsa
≥
mint a lyuk leszármazottainak kulcsai.
Vegyük észre, hogy egy lyukas kupacban a lyuk kulcsába mindig tudunk olyan értéket írni, hogy szabályos kupacot kapjunk!
35
A lyukas kupacok az
alapvet® kupacm¶veletek (új elem beszúrása, maximum kivétele) során alakulnak ki, amiket aztán a lyuk megfelel® mozgatásával állítunk helyre. (Ld. a "Kupacok és els®bbségi sorok" fejezetet!) Egy balra tömörített, majdnem teljes bináris fát
csonka kupacnak nevezünk,
ha minden szül®-gyerek párosban a szül® kulcsa nagyobb-egyenl®, mint a gyereke kulcsa, kivéve, ha a szül® a gyökércsúcs.
A gyökércsúcs kulcsa is
de niált, de lehet, hogy kisebb, mint a gyereke kulcsa. A csonka kupacok egy tömb kupaccá alakítása során jönnek majd létre, mint átmeneti adatszerkezetek. (Ld. a "Kupacrendezés" fejezetet!)
8.4.
Bináris fák aritmetikai ábrázolása
A balra tömörített, majdnem teljes bináris fákat, speciálisan a kupacokat, szokás szintfolytonosan, egy vektorban ábrázolni.
Ha pl. egy
A[1..n]
tömb
m elemét használjuk, akkor az i index¶ csúcs gyerekeinek indexei 2i, illetve 2i+1, feltéve, hogy a gyerekek léteznek, azaz 2i ≤ m, illetve 2i+1 ≤ m. A baloldali gyerek indexe azért 2i, mert az i-edik csúcsot a szintfolytonos ábrázolásban (i − 1) csúcs el®zi meg. Az i-edik csúcs baloldali gyerekét tehát megel®zi ennek az (i − 1) csúcsnak a (2i − 2) gyereke, plusz a gyökércsúcs, aminek nincs szül®je. Ez összesen (2i−1) csúcs, és így az i-edik csúcs baloldali gyerekének indexe 2i, a jobboldalié pedig 2i + 1. j Más részr®l, ha egy csúcs indexe j > 1, akkor a szül®jének indexe b c. 2 j Ez abból következik, hogy akár j = 2i, akár j = 2i + 1 esetén b c = i. 2 k A fentiekb®l adódik, hogy az 1..k sorszámú csúcsok szülei az 1..b c sor2 els®
számú csúcsok:
j indexére 1 ≤ j ≤ k , és van szül®je, azaz j ≥ 2, j k akkor a szül®je indexére 1 ≤ b c ≤ b c. 2 2 k - Másrészt, ha az i index¶ csúcsra 1 ≤ i ≤ b c, akkor ennek bal gyerekére 2 2 ≤ 2i ≤ 2b k2 c ≤ k , azaz van gyereke az 1..k sorszámú csúcsok között. Eszerint egy n csúcsú, balra tömörített, majdnem teljes bináris fának f ele(n) = b n2 c bels® csúcsa van. Ha ugyanis a csúcsokat sorfolytonosan az 1..n sorszámokkal indexeljük, akkor az el®bbi állítás szerint a szüleik sorszán mai 1..b c. 2 Az el®z® szakaszban belátott állítás szerint egy n csúcsú, balra tömörített, n majdnem teljes bináris fának d e levele van. 2 - egyrészt, ha egy csúcs
Jelölje a továbbiakban
nd
tetsz®leges
n
d magasságú részfáinak számát, n≥d pedig a fa legalább d ma1 ≤ d ≤ h = blg nc, azaz h az eredeti fa maEkkor n≥1 = f ele(n), hiszen a legalább egy magasságú részfák gyö-
teljes bináris fa
gasságú részfáinak számát, ahol gassága!
méret¶, balra tömörített, majdnem
36
kércsúcsai éppen a bels® csúcsok. Továbbá
n≥2 = f ele(f ele(n)) = f ele2 (n),
hiszen a legalább kett® magasságú részfák gyökércsúcsai éppen a legalább egy magasságú részfák gyökércsúcsainak szülei, és mivel az utóbbiak szin2 folytonosan 1..f ele(n) sorszámúak, azért az el®bbiek 1..f ele (n) sorszámúak. Teljes indukcióval adódik
h X
nm = n≥d = f eled (n) ≤
m=d
n 2d
A tömböt nullától indexeljük, akkor A[i] A[2i + 1] illetve A[2i + 2], a 2i + 1 < m, illetve a 2i + 2 < m j−1 c] ! feltétellel, A[j] szül®je pedig j > 0 esetén A[b 2
HF: Bizonyítsuk be, hogy ha az gyerekei
8.5.
Kupacok és els®bbségi (prioritásos) sorok
PrSor A[1..n] : T // T ismert típus, n globális konstans m : 0..n // m a PrSor aktuális mérete + PrSor() {m := 0} // üresre inicializálja a PrSort -
// destruktort itt nem kell de niálni
+ + + + + +
üresPrSor() {m prSorba(x
: T)
:= 0}
// kiüríti a PrSort
// beteszi
x-et
a prSorba
fv maxKivesz() : T // kiveszi és visszaadja a PrSor maximális elemét fv max() : T // megnézi és visszaadja a PrSor maximális elemét fv tele_e() : L {return m = n} fv üres_e() : L {return m = 0}
A[1..m] résztömb egy kupac aritmetikai ábrázolása, M TprSorba (m) ∈ Θ(lg m), mTprSorba (m) ∈ Θ(1), M TmaxKivesz (m) ∈ Θ(lg m), mTmaxKivesz (m) ∈ Θ(1), Tmax (m) ∈ Θ(1), mivel az alábbi "prSorba" és "le-
Ha az
süllyeszt" eljárások f® ciklusa maximum annyiszor fut le, amennyi a fa magassága. A prSorba(x) esetében a szintfolytonosan els® üres helyen egy lyukat (A[j]) kapcsolunk a kupachoz.
Így egy
lyukas kupacot
kapunk, aminek egyenl®re
egy levele a lyuk. Azután a lyukat addig cserélgetjük mindig az aktuális szül®jével (A[i]) amíg van szül®je, és mozog a kupacban, és gyökérbe, vagy
x
már
x>
mint a szül®. Így a lyuk felfelé
x > mint a lyuk leszármazottai. Ha a lyuk felér a ≤ mint a lyuk szül®je, akkor beletesszük x-et, és így
helyreáll a kupac.
37
PrSor::prSorba(x)
m
m := m + 1 j := m ; i := b m2 c i > 0 ∧ A[i] < x
HIBA ("Tele van a PrSor.")
A[j] := A[i] j := i ; i := b 2i c A[j] := x
M TprSorba (m) ∈ Θ(lg m); hiszen a ciklus legfeljebb annyiszor fut le, amennyi a fa magassága, azaz (m input értékéhez viszonyítva) blg(m+1)c-szer, amib®l lg m ≤ M TprSorba (m) = blg(m + 1)c + 1 ≤ lg m + 2. mTprSorba (m) ∈ Θ(1), ha ugyanis x elég kicsi, akkor a ciklus egyszer sem fut le, és innét mTprSorba (m) = 1. Tmax (m) ∈ Θ(1), mivel Tmax (m) = 1.
fv PrSor::max() A
m>0
return A[1]
HIBA("Üres a PrSor.")
fv PrSor::maxKivesz()
m>0
A
max := A[1] m := m − 1 lesüllyeszt(A[1..m], A[m + 1])
HIBA ("Üres a PrSor.")
return max A maxKivesz() metódus a kupac gyökerében,
A[1]-ben
hoz létre egy lyukat.
Ezután a szintfolytonosan utolsó elemet levágja a lyukas kupacról, majd a "lesüllyeszt" eljárás segítségével (amit mindig
k = 1-gyel
hív meg) a lyukat
(A[i]) addig süllyeszti lefelé, amíg a levágott elem (x) bele nem illik. Ennek
38
során a lyukat mindig az aktuálisan nagyobb gyerekével cseréli meg, amíg még a levélszint fölött van, és a lyuk nagyobbik gyereke a ciklus során
x <
mint a lyuk ®sei.
lyuk a levélszintre, vagy
x≥
> x.
Ilyen módon
Amikor a ciklus megáll, vagy leért a
mint a lyuk gyerekei. Ekkor
x-et
a lyukba téve
szabályos kupacot kapunk. Vegyük észre, hogy a lesüllyeszt eljárást az itt szükségesnél kicsit általánosabban írtuk meg! Akkor is m¶ködik, ha a lyuk eredetileg tetsz®leges részfa gyökerében van.
Ilyenkor az adott részfa mint lyukas kupac kupaccá
alakítására fogjuk használni. (Ld. a "Kupacrendezés" fejezetet!)
lesüllyeszt(A[k..m], x)
i := k ; j := 2k ; b := igaz j ≤m∧b A[j] a lyuk bal gyereke j < m ∧ A[j + 1] > A[j] j := j + 1 SKIP //
A //
A
A[j]
a lyuk nagyobbik gyereke
A[j] > x A[i] := A[j] b := hamis i := j ; j := 2j A[i] := x
A maxKivesz() metódus m¶veletigényének meghatározásához el®ször meg-
k gyöker¶ lyukas kupac h, akkor M Tle (h) = h + 1, ugyanis a ciklus legfeljebb h iterációt végez, és 1 ≤ mTle (h) ≤ 2, mert lehet, hogy a ciklus legfeljebb egyet iterál. Speciálisan k = 1 esetére: lg m ≤ M Tle1 (m) = h + 1 = blg mc + 1 ≤ lg m + 1.
vizsgáljuk a lesüllyeszt() (rövidítve le) eljárást. Ha a magassága
Innét Ebb®l
lg m ≤ lg(m − 1) + 1 ≤ M TmaxKivesz (m) ≤ lg(m − 1) + 2 ≤ lg m + 2. M TmaxKivesz (m) ∈ Θ(lg m).
mTmaxKivesz (m) ∈ Θ(1), hiszen 2 = 1 + 1 ≤ mTmaxKivesz (m) = 1 + mTle1 (m − 1) ≤ 1 + 2 = 3.
8.5.1.
Rendezés els®bbségi sorral
A fenti els®bbségi sor segítségével könnyen és hatékonyan rendezhetünk tömböket:
39
prSorralRendez(A[1..n])
Q : P rSor i := 1..n Q.prSorba(A[i]) i := n..1(−1) A[i] := Q.maxKivesz()
A fenti rendezésben a
Q.prSorba(A[i])
és az
A[i] := Q.maxKivesz()
utasí-
O(lg n) hatékonyságúak, hiszen az els®bbségi sort reprezentáló kupac ≤ lg n. Ezért a rendezés m¶veletigénye O(n lg n). Maximális m¶veletigénye Θ(n lg n). Ha ugyanis az input vektor szigorúan
tások
magassága
monoton növekv®, akkor az els® ciklus által megvalósított kupacépítés minden új csúcsot a fa gyökeréig mozgat fel. Amikor pedig a végs® kupac leend® leveleit szúrjuk be, már legalább blg nc − 1 mélység¶ a fa, és a leend® levelek d n2 e. Ekkor tehát csak a levelek beszúrásának futási ideje Ω(n lg n), így a teljes futási id® is. Az el®bbi O(n lg n) korláttal együtt adódik az állítás. száma
A fenti rendezés tehát, maximális m¶veletigényét tekintve, aszimptotikusan az eddig ismert legjobb rendezésünkkel, az összefuttató rendezéssel (mergesort) egyenrangú. Hátránya, hogy a rendezend® vektorral azonos méret¶ munkamemóriát igényel, a prioritásos sorban tárolt kupac számára. (Az összefuttató rendezés vektoros változata kb. feleakkorát igényel, bár így nagyságrendileg mindkét rendezésnek
Θ(n) a tárigénye, míg az összefuttató renΘ(lg n) munkatárat használ, mégpedig a
dezés láncolt listás változata csak
rekurzív hívások adminisztrálásához.) A továbbiakban megismerjük a kupacrendezést (heapsort), ami egyrészt helyben rendez, azaz csak
Θ(1)
munka-
tárat igényel, másrészt a rendezés els® fázisát, a kupacépítést optimalizálja, így a gyakorlatban a fenti rendezésnél gyorsabb, bár aszimptotikusan a kupacrendezés maximális m¶veletigénye is
8.6.
Θ(n lg n).
Kupacrendezés (Heapsort)
A kupacrendezés a fenti prSorralRendez(A[1..n]) optimalizálása. Egyrészt az algoritmust kívül csak egy
Θ(n)
Θ(1)
helyben rendez®vé
alakítjuk: az
A[1..n]
tömbön
memóriát használunk, míg a fenti eljárásnak szüksége van
méret¶ segédtömbre, amiben a prioritásos sort ábrázoló kupacot
tárolja. Másrészt a kupac felépítését optimalizáljuk, ami a fenti esetben magában véve is
O(n lg n)
m¶veletigény¶, maximális futási ideje pedig
40
Θ(n lg n).
El®ször tehát kupaccá alakítjuk a tömböt, most lineáris m¶veletigénnyel:
kupaccá_alakít(A[1..n])
k := b n2 c..1(−1) lesüllyeszt(A[k..n], A[k])
A[1..n] tömb, mint balra tömöh = blg nc. Levelei önmagukban
A fenti eljárás magyarázatához: Eredetileg az rített majdnem teljes bináris fa magassága egyelem¶ kupacok. A
(h − 1)-edik
szinten lev® bels® csúcsokhoz, mint gyö-
csonka kupacok, amikben egyedül a gyökércsúcs tartalma lehet "rossz helyen". Ezeket kerekhez tartozó bináris fák tehát (egy magasságú) úgynevezett
tehát helyreállíthatjuk a gyökér lesüllyesztésével az alatta lev® csonka kupacba. Ezután már a
(h − 2)-edik szinten lev® csúcsokhoz,
tartozó bináris fák lesznek (kett® magasságú)
mint gyökerekhez
csonka kupacok, amiket hason-
lóan állíthatunk helyre, és így tovább, szintenként visszafelé. Utolsóként az
A[1]-et süllyesztjük le az alatta lév® csonka kupacba, és ezzel az A[1..n] tömb kupaccá alakítása befejez®dött. Annak érdekében, hogy a szintekkel ne kelljen külön foglalkozni, a fenti eljárásban a lesüllyesztéseket a szintfolytonosan utolsó bels® csúccsal kezdtük, és innét haladtunk szintfolytonosan visszafelé. Ezután a teljes rendezés:
kupacrendezés(A[1..n])
kupaccá_alakít(A[1..n])
m := n m>1 x := A[m] ; A[m] := A[1] ; m := m − 1 lesüllyeszt(A[1..m], x)
A kupaccá alakítás után tehát ezt ismételjük: A kupacról levágjuk a szintfolytonosan utolsó csúcsát, a helyére tesszük a kupac maximumát, majd a levágott csúcsot (x) lesüllyesztjük az
A[1..m],
gyökerénél lyukas kupacba.
Így az el®bbinél eggyel kisebb méret¶ kupacot kapunk.
Ezt a ciklusmagot
addig ismételjük, amíg a kupac mérete nagyobb, mint egy.
Így az
A[1..n]
tömbben visszafelé megkapjuk az els®, második stb. maximumokat, és végül az
A[1]-ben
a minimumot, azaz a tömb rendezve lesz.
41
8.6.1.
A kupacrendezés m¶veletigénye
A kupaccá alakítás utáni rész futási idejét a lesüllyeszt(A[1..m], x) hívások
O(lg m) (m = n − 1, n − 2, . . . , 1), (n−1) hívás tehát összesen O(n lg n) futási ciklus (n − 1) iterációja nem befolyásolja,
határozzák meg, amiknek m¶veletigénye durva fels® becsléssel
O(lg n).
Az
idej¶, és ezt nagyságrendileg a mert ez csak
O(n) m¶veletigényt ad hozzá, ami aszimptotikusan kisebb, mint
O(n lg n). A kupaccá alakításról hasonlóan látható, hogy maga is nél nomabb becsléssel belátjuk, hogy futási id® továbbra is
O(n lg n),
Θ(n)
O(n lg n),
m¶veletigény¶.
de en-
Ett®l a teljes
hiszen a szekvenciában ebb®l a szempont-
ból az aszimptotikusan nagyobb m¶veletigény¶ programrész dominál, de a prSorralRendez(A[1..n]) eljárás kupacépít® ciklusához képest hatékonyabb kupaccá alakítással a gyakorlatban így is jelent®s futási id®t takaríthatunk meg.
kupaccá_alakít(A[1..n])
k := b n2 c..1(−1) lesüllyeszt(A[k..n], A[k])
Szemléletesen fogalmazva, a prSorralRendez(A[1..n]) eljárás kupacépít® ciklusához képest abból adódik a hatékonyság növekedése, hogy ott az elemek túlnyomó részét már a végs®höz közeli magasságú kupacba szúrjuk be, míg itt a fa leveleit, az elemek felét egyáltalán nem kell lesüllyeszteni, ezek szüleit, az elemek negyedét egy magasságú fában süllyesztjük le, nagyszüleit, az elemek nyolcadát kett® magasságú fában stb. Ahhoz, hogy a kupaccá_alakít(A[1..n]) m¶veletigénye
Θ(n), el®ször beM Tk (n) ≤ 2n + 1 teljesül. Idézzük fel ehhez, hogy a 8.4. alfejezet végén az A[1..n] vektorban tárolt balra tömörített majdnem teljes fa d magasságú részfáinak számát nd -vel, a legfeljebb d magasságú részfák számát pedig n≥d -vel jelöltük. Bevezettük n még a f ele(n) = b c függvényt, a fa magasságára pedig a h = blg nc jelölést, 2 látjuk, hogy maximális m¶veletigényére
és a
h X
nm = n≥d = f eled (n) ≤
m=d
n 2d
összefüggést kaptuk. A kupaccá alakítás M Tk (n) maximális m¶veletigényét n az eljárás meghívása, a ciklus b c iterációja és a lesüllyeszt® eljárás végre2 hajtásai adják. Tetsz®leges d magasságú részfára a lesüllyeszt® eljárás m¶veletigénye legfeljebb
d + 1.
Az összes,
42
nd
darab
d
magasságú részfákra
tehát a lesüllyesztések m¶veletigénye összesen legfeljebb
nd ∗ (d + 1).
Mi-
d ∈ 1..h,
vel a lesüllyeszt® eljárás hívásai során
a kupaccá alakítás alatt a Ph lesüllyesztések m¶veletigényének összege legfeljebb d=1 nd ∗ (d + 1). Innét
M Tk (n) ≤ 1 +
jnk 2
+
h X
nd ∗ (d + 1) = 1 +
jnk
d=1
Ph Ph Vegyük most gyelembe, hogy d=1 nd = m=1 Ph és hogy d ∗ n az alábbi alakba írható: d d=1
2
+
h X
nd +
d=1
h X
d ∗ nd
d=1
nm = n≥1 = f ele(n) =
n 2
,
n1 + n2 + n2 + n3 + n3 + n3 + ...
nh + nh + nh + . . . + nh
(h tagú összeg)
Ezt oszloponként összeadva azt kapjuk, hogy
h X
d ∗ nd =
h h X X
nm =
n≥d =
h X
f eled (n) ≤
d=1
d=1
d=1 m=d
d=1
h X
h ∞ X X n 1 ≤ n ∗ =n d d 2 2 d=1 d=1
Eredményeinket behelyettesítve kapjuk, hogy
M Tk (n) ≤ 1 +
j n k 2
Most belátjuk még, hogy
+
j n k 2
+
h X
d ∗ nd ≤ 1 + n + n = 2n + 1
d=1
mTk (n) ≥ n,
amihez elég meggondolni, hogy a ku-
paccá alakításból a lesüllyesztések bels® m¶veletigényét elhanyagolva, tehát csak a küls® eljáráshívást, a ciklusiterációkat és a lesüllyeszt-hívásokat szán n molva mTk (n) ≥ 1 + + 2 ≥ n. Innét n ≤ mTk (n) ≤ M Tk (n) ≤ 2n + 1, 2 amib®l
M Tk (n), mTk (n) ∈ Θ(n) adódik. Felvet®dhet a kérdés, hogy nomabb becsléssel nem lehetne-e a kupacrendezésben a kupaccá alakítás utáni ciklusról is belátni, hogy
Θ(n)
a m¶velet-
igénye, amib®l következne, hogy az egész kupacrendezés futási ideje is
Θ(n).
A válasz sajnos nem, mert kés®bb, az összehasonlító rendezések alaptételei segítségével be fogjuk tudni látni, hogy a kupacrendezés maximális és átlagos futási ideje
Θ(n lg n).
HF: Lássuk be, hogy a kupacrendezés minimális futási ideje
Θ(n),
dául akkor áll el®, amikor az input tömb minden eleme egyenl®!
43
ami pél-
8.7.
Bináris keres®fák
Egy bináris fát
keres®fának
nevezünk, ha minden nemüres
r
részfájára és
y kulcsra igazak az alábbi követelmények: x egy tetsz®leges csúcs kulcsa az r bal részfájából, akkor x < y . z egy tetsz®leges csúcs kulcsa az r jobb részfájából, akkor z > y .
annak a gyökerében lév® - Ha - Ha
Egy bináris fát
rendez®fának
annak a gyökerében lév® - Ha - Ha
y
nevezünk, ha minden nemüres
r
részfájára és
kulcsra igazak az alábbi követelmények:
x egy tetsz®leges csúcs kulcsa az r bal részfájából, akkor x ≤ y . z egy tetsz®leges csúcs kulcsa az r jobb részfájából, akkor z ≥ y .
A keres®fában tehát minden kulcs egyedi, míg a rendez®fában lehetnek dup-
bináris keres®fákra írjuk meg, de ezek könnyen átírhatók a bináris rendez®fák esetére. likált és többszörös kulcsok is. A továbbiakban a m¶veleteket
A bináris keres®fák tekinthet®k véges halmazok, vagy szigorúan monoton növekv® sorozatok reprezentációinak.
H(t) a t bináris keres®fa által reprezentált halmazt! Ekkor de níció szerint H(Ω) = {}, illetve H(t) = H(t → bal) ∪ {t → kulcs} ∪ H(t → jobb), amennyiben t 6= Ω. A t bináris keres®fa által reprezentált sorozatot megkaphatjuk, ha Inorder Jelölje
bejárással kiíratjuk a fa csúcsainak tartalmát:
inorderKiír(t)
t 6= Ω inorderKiír(t kiír(t
→ bal)
→ kulcs)
t := t → jobb
HF: Bizonyítsuk be, hogy a fenti program a
t bináris keres®fa
kulcsait szigo-
rúan monoton növekv® sorrendben írja ki! (Ötlet: teljes indukció vagy magassága szerint.) Bizonyítsuk be azt is, hogy ha a fenti program a
t bináris fa
szigorúan monoton növekv® sorrendben írja ki, akkor az
keres®fa!
t
mérete
kulcsait
A fenti házi feladat állításának alapvet® következménye, hogy amennyiben egy bináris fa transzformáció a fa inorder bejárását nem változtatja meg, és adott egy bináris keres®fa, akkor a fa a transzformáció végrehajtása után is
44
bináris keres®fa marad (mivel a kiindulási fa inorder bejárása szigorúan monoton növekv® kulcssorozatot ad, és ez a transzformáció után is így marad). Ezt a tulajdonságot a bináris keres®fák kiegyensúlyozásánál fogjuk kihasználni, az AVL fákról szóló fejezetben. A továbbiakban feltesszük, hogy a bináris keres®fákat láncoltan ábrázoljuk,
Csúcs típusúak, és az Ω üres fát Bináris fák reprezentációi: láncolt
szül® pointerek nélkül, azaz a fák csúcsai a
pointer reprezentálja.
ábrázolás fejezetet!) 8.8.
(Ld. a
Bináris keres®fák: keresés, beszúrás, törlés
A gyakorlati programokban egy adathalmaz tipikus m¶veletei a következ®k: adott kulcsú rekordját keressük, a rekordot a kulcsa szerint beszúrjuk, illetve adott kulcsú rekordot törlünk. Ha a keresés a megtalált rekord címét adja vissza, így az adatmez®k frissítése is megoldható, és ha nincs a keresett kulcsú rekord, azt egy
pointer visszadásával jelezhetjük.
Az alábbi programokban az egyszer¶ség kedvéért az adat és a kulcs ugyanaz, mert a bináris fák kezelésének jellegzetességeit így is be tudjuk mutatni.
Ugyanezen okból a m¶veleteket egy halmaz és egy kulcs közötti
halmazm¶veletek megvalósításának tekintjük. A m¶veletek:
fv keres(t, k) :
k ∈ H(t), akkor a k kulcsú csúcsra mutató pointerrel tér vissza, különben a hivatkozással, - beszúr(t, k ) : a H(t) := H(t) ∪ {k} absztrakt m¶velet megvalósítása, - fv min(t) : a t 6= fában a minimális kulcsú csúcsra áll, - minKivesz(t, minp) : a t 6= fából kivesszük a legkisebb kulcsot tartalmazó -
ha
csúcsot.
H(t) := H(t) \ {k} absztrakt m¶velet megvalósítása, m¶veletre M T (h) ∈ Θ(h) (ahol h = h(t)).
- töröl(t, k ) : a Mindegyik
(Ld. az alábbi struktogramokat!) A keres(t, k ) függvény a keresi a
k
kulcs helyét.
t
fában, a bináris keres®fa de níciója alapján meg-
A kulcsot akkor és csak akkor találja meg, ha ott
nemüres részfa van. A beszúr(t, k ) eljárás is megkeresi a
t
fában a
k
kulcs helyét.
Ha ott
egy üres részfát talál, akkor az üres részfa helyére tesz egy új levélcsúcsot,
k
kulccsal. A min(t) függvény a
t nemüres fa "bal alsó" csúcsára hivatkozó pointerrel
tér vissza.
45
A minKivesz(t, minp) eljárás
minp-ben a t nemüres fa "bal alsó" (a legki-
sebb kulcsot tartalmazó) csúcsára mutató pointerrel tér vissza, de még el®tte a csúcsot kif¶zi a fából, azaz a csúcshoz tartozó részfa helyére teszi a csúcs jobboldali részfáját. A töröl(t, k ) eljárás szintén megkeresi a találta a
k
t fában a k
kulcs helyét. Ha meg-
kulcsot tartalmazó csúcsot, még két eset lehet.
(1) Ha a csúcs
egyik részfája üres, akkor a csúcshoz tartozó részfa helyére teszi a csúcs másik részfáját. (2) Ha a csúcsnak két gyereke van, akkor a minKivesz eljárás segítségével
kiveszi a jobboldali részfából a minimális kulcsú csúcsot, és a k kulcsú
csúcs helyére teszi, hiszen ez a kulcs a baloldali részfa kulcsainál nagyobb, a jobboldali részfa maradék kulcsainál pedig kisebb. (Vegyük észre, hogy a (2) esetben a baloldali részfából a maximális kulcsú csúcsot is kivehetnénk!) HF: Írjuk meg a veleteket.
t 6=
fából a maximális kulcs kiolvasása / kivétele m¶-
Mekkora lesz a futási id®?
szül® pointeres csúcsok esetére!
Miért?
Írjuk át a fenti m¶veleteket
Próbáljuk meg a nemrekurzív programo-
kat rekurzívvá, a rekurzívakat nemrekurzívvá átírni, megtartva a futási id®k nagyságrendjét!
fv keres(t, k)
t 6= ∧ t → kulcs 6= k
A
k < t → kulcs t := t → bal t := t → jobb
return t
beszúr(&t, k )
t=
A
t :=
new Csúcs(k)
A
k < t → kulcs k > t → kulcs A A k = t → kulcs beszúr(t → bal, k ) beszúr(t → jobb, k ) SKIP
fv min(t) t → bal 6=
t := t → bal return t
minKivesz(&t, &minp)
A
minp := t
t → bal =
t := minp → jobb [minp → jobb := ] 46
minKivesz(t
→ bal, minp)
Mj.:
A minKivesz(t, minp) eljárásban a minp
→ jobb :=
utasítás arra
szolgál, hogy a kif¶zött csúcs ne tartalmazzon hivatkozást a fa egy részfájára. Az alábbi töröl(t, k ) eljárásból, pontosabban annak gyökeretTöröl(t) segédeljárásából való meghívás esetén azonban ez az utasítás felesleges.
töröl(&t, k )
t 6=
A A
k < t → kulcs A k > t → kulcs A k = t → kulcs töröl(t → bal, k ) töröl(t → jobb, k ) gyökeretTöröl(t)
gyökeretTöröl(&t)
At
→ bal = At → jobb = A p := t p := t
t := p → jobb delete p
Mj.:
t → bal 6= ∧ t → jobb 6= minKivesz(t → jobb, p)
t := p → bal p → bal := t → bal ; p → jobb := t → jobb delete p [ t → bal := t → jobb := ; ] delete t ; t := p → bal := t → jobb :=
A gyökeretTöröl(t) segédeljárásban a t
utasítás a
Csúcs
SKIP
osztály jelenlegi de níciója mellett felesleges. Ha azonban
kiegészítenénk az osztályt egy olyan destruktorral, ami törli a csúcs gyerekeit (és ezért végs® soron rekurzívan a csúcshoz tartozó részfát), akkor szükséges lenne, annak érdekében, hogy a delete
t
utasítás csak a
(∗t)
csúcsot
törölje. Mivel mindegyik m¶veletre
M T (h) ∈ Θ(h)
(ahol
h = h(t)),
a m¶veletek ha-
tékonysága alapvet®en a bináris keres®fa magasságától függ. Ha a fának csúcsa van, a magassága
blg nc
(majdnem teljes fa esete) és
torzult fa esete) között változik.
(n − 1)
n
(listává
Ez teljesen attól függ, hogy milyen m¶-
veleteket, milyen sorrendben és milyen kulcsokkal hajtunk végre. Ezért az eddig tárgyalt keres®fákat pontosabban
véletlen építés¶ bináris keres®fáknak
nevezik. Szerencsére az a tapasztalat, hogy ha a kulcsok sorrendje, amikkel a beszúrásokat és törléseket végezzük, véletlenszer¶, akkor a fa magassága általában
O(lg n)
(bizonyítható, hogy nagy
n-ekre
átlagosan kb.
1, 4 lg n),
és így
a beszúrás és a törlés sokkal hatékonyabb, mintha az adathalmaz tárolására
47
tömböket vagy láncolt listákat használnánk, ahol csak
O(n)
hatékonyságot
tudnánk garantálni. HF: Rendezetlen illetve rendezett tömbök esetén mely m¶veletekre tudnánk az
M T (n) ∈ Θ(n) hatékonyságot javítani?
Mennyire? Láncolt listák esetén?
HF: Igaz-e, hogy véletlen építés¶ bináris keres®fák esetén a fenti m¶veletek bármelyikére
mT (n) ∈ Θ(1)?
HF*: Írjunk olyan eljárást, ami egy szigorúan monoton növekv® vektorból majdnem teljes bináris keres®fa másolatot készít,
O(n)
futási id®vel!
Sok alkalmazás esetén azonban nem megengedhet® az a kockázat, hogy ha a keres®fa (majdnem) listává torzul, akkor a m¶veletek hatékonysága is hasonló lesz, mint a láncolt listák esetén. Az ideális megoldás az lenne, ha tudnánk garantálni, hogy a fa majdnem teljes legyen. Nem ismerünk azonban olyan
O(lg n)
futási idej¶ algoritmusokat, amelyek pl. a beszúrási és törlési m¶ve-
letek során ezt biztosítani tudnák. A vázolt probléma megoldására sokféle
kiegyensúlyozott keres®fa fogalmat
vezettek be. Ezek közös tulajdonsága, hogy a fa magassága
O(lg n),
és a ke-
resés, beszúrás, törlés m¶veleteinek futási ideje a fa magasságával arányos, azaz szintén
O(lg n).
A kiegyensúlyozott keres®fák közül a legismertebbek
AVL fák, a piros-fekete fák (ezek idáig bináris keres®fák), a B fák és a B+ fák (ezek viszont már nem bináris fák). A legrégebbi, talán a legegyaz
szer¶bb, és a központi tárban kezelt adathalmazok ábrázolására mindmáig széles körben használt konstrukció az
AVL fa.
A modern adatbáziskezel®
programok, fájlrendszerek stb., tehát azok az alapszoftverek és alkalmazások, amik háttértáron kezelnek keres®fákat, leginkább a
B+ fákat
részesítik
el®nyben. Ezért ez utóbbi két keres®fa típus tárgyalásával folytatjuk.
8.9.
AVL fák
Az AVL fák kiegyensúlyozásának szabályaival kapcsolatos ábrák [2]-ben találhatók: .
AVL fák magasság szerint kiegyensúlyozott bináris keres®fák. Egy magasság szerint kiegyensúlyozott, ha minden csúcsa kiegyensúlyozott. (Mostantól kiegyensúlyozott alatt magasság szerint kiegyensúlyozottat értünk.) Egy bináris fa egy (∗p) csúcsa kiegyensúlyozott, ha a csúcs (p → s) Az
bináris fa
egyensúlyára
|p → s| ≤ 1.
A
(∗p)
csúcs egyensúlya de níció szerint:
p → s = h(t → jobb) − h(t → bal) 48
Az AVL fákat láncoltan reprezentáljuk. A csúcsokban az
s
egyensúly attrit-
butumot expliciten tároljuk. (A másik lehet®ség a két részfa magasságainak tárolása lenne.) A Csúcs osztályt tehát a következ®képpen módosítjuk:
Csúcs + kulcs : T // T valamilyen ismert típus + s : −1..1 // a csúcs egyensúlya + bal, jobb : Csúcs* + Csúcs() { bal := jobb := ; s := 0 } // egycsúcsú fát + Csúcs(x:T) { bal := jobb := ; s := 0 ; kulcs := x }
képez bel®le
Egyenl®re részletes bizonyítás nélkül közöljük az alábbi eredményt:
Tétel:
Tetsz®leges
n
csúcsú nemüres AVL fa
blg nc ≤ h ≤ 1, 45 lg n,
A bizonyítás vázlata: súlyozott, bináris fák)
n
El®ször a
h
magasságára:
azaz h ∈ Θ(lg n)
h
magasságú, nemüres KBF-ek (kiegyenh+1 méretére adunk alsó és fels® becslést. Az n < 2
becslésb®l azonnal adódik
blg nc ≤ h.
Másrészt meghatározzuk a
h
mély-
fh számát. Erre kapjuk, hogy f0 = 1, f1 = 2, fh = 1 + fh−1 + fh−2 (h ≥ 2). Ezért az ilyen fákat Fibonacci fáknak hívjuk. Mivel tetsz®leges h magasságú KBF n méretére n ≥ fh , némi matematikai ügyességgel kaphatjuk a h ≤ 1, 45 lg n egyenl®tlenséget. ség¶, legkisebb méret¶ KBF-ek csúcsainak
Mivel az AVL fák magassága min(t) függvényeire
t
Θ(lg n),
ezért a bináris keres®fák keres(t, k ) és
AVL fa esetén automatikusan
M T (n) ∈ Θ(lg n),
ahol
n = |t|. A beszúr(t, k ), a töröl(t, k ) és a minKivesz(t, minp) eljárások azonban változtatják a fa alakját. Így elromolhat a kiegyensúlyozottság, és már nem garantált a fenti m¶veletigény. Ennek elkerülésére ezeket az eljárásokat úgy módosítjuk, hogy minden egyes rekurzív eljáráshívás után ellen®rizni fogjuk, hogyan változott a megfelel® részfa magassága, és ez hogyan befolyásolta a felette lev® csúcs kiegyensúlyozottságát, szükség esetén helyreállítva azt. Ez minden szinten legfeljebb konstans mennyiség¶ extra m¶veletet fog jelenteni, és így a kiegészített eljárások futási ideje megtartja az (ahol
n = |t|)
M T (n) ∈ Θ(lg n)
nagyságrendet.
A példákhoz a
(bal_részfa gyökér jobb_részfa)
üres részfákat elhagyjuk.
49
jelölést vezetjük be, ahol az
Például a ((2)4((6)8(10))) bináris keres®fa gyökere a 4; bal részfája a (2), ami egyetlen levélcsúcsból (és annak üres bal és jobb részfáiból) áll; jobb részfája a ((6)8(10)), aminek gyökere a 8, bal részfája a (6), jobb részfája a (10).
Az így ábrázolt fák inorder bejárása a zárójelek elhagyásával adódik. A bels® csúcsok egyensúlyait ks formában jelöljük, ahol k a csúcsot azonosító kulcs, s pedig a csúcs egyensúlya, a 0:◦, 1:+, 2:++, -1:−, -2:−− megfeleltetéssel. Mivel a levélvsúcsok egyensúlya mindig nulla, a leveleknél nem jelöljük az egyensúlyt. A fenti AVL fa például a megfelel® egyensúlyokkal a következ®: ((2)4+((6)8◦(10))) Az AVL fák m¶veletei során a kiegyensúlyozatlan részfák kiegyensúlyozásához
forgatásokat
fogunk használni.
Az alábbi forgatási sémákban görög
kisbet¶k jelölik a részfákat (amelyek minden esetben AVL fák lesznek), latin nagybet¶k pedig a csúcsok kulcsait:
Balra forgatás (Left rotation): (α T (β J γ )) → ((α T β ) J γ ) Jobbra forgatás (Right rotation): ((α B β ) T γ ) → (α B (β T γ )) Vegyük észre, hogy a fa inorder bejárását egyik forgatás sem változtatja, így a bináris keres®fa tulajdonságot is megtartják. Mint látni fogjuk, a kiegyensúlyozatlan részfák kiegyensúlyozása minden esetben egy vagy két forgatásból áll.
Ezért a bináris keres®fa tulajdonságot a kiegyensúlyozások is megtartják.
8.10.
AVL fák: beszúrás
Nézzük most el®ször a bináris keres®fák beszúr(t, k ) eljárását! Az 1 beszúrásával a ((2)4+((6)8◦(10))) AVL fából az (((1)2−)4◦((6)8◦(10))) AVL fa adódik, a 3 beszúrásával pedig a ((2+(3))4◦((6)8◦(10))) AVL fa.
A 7 be-
szúrásával azonban a ((2)4++((6+(7))8−(10))) fát kapjuk, a 9 beszúrásával pedig a ((2)4++((6)8+((9)10−))) fát.
Mindkett® bináris keres®fa, de már
nem AVL fa, mivel a 4++ csúcs nem kiegyensúlyozott. A legutolsó esetben a bináris keres®fa könnyen kiegyensúlyozható, ha meggondoljuk, hogy az a következ® sémára illeszkedik, amiben görög kisbet¶k jelölik a kiegyensúlyozott részfákat, latin nagybet¶k pedig a csúcsok kulcsait: (α T++ (β J+
γ )),
ahol T=4,
α=(2),
J=8,
β =(6)
és
γ =((9)10−).
A kiegyensúlyozáshoz szükséges transzformáció a fa (α T++ (β J+
γ )) →
((α T◦
balra forgatása [2]:
β ) J◦ γ )
A fenti példán ez a következ®t jelenti: ( (2) 4++ ((6)8+((9)10−)) )
→
( ((2)4◦(6)) 8◦ ((9)10−) )
50
h = h(α)
A transzformáció helyességének belátásához bevezetjük a
jelö-
lést. Ebb®l a kiinduló fára a T++ és J+ egyensúlyok miatt
h((β fára
γ)) = h+2, h(γ) = h+1 és h(β) = h adódik, innét pedig az eredmény h(α) = h = h(β) miatt T◦; továbbá h((α T◦ β)) = h + 1 = h(γ) miatt J
J◦ adódik. Az eredeti ( (2) 4+ ((6)8◦(10)) ) fába a 7 beszúrásával adódó ( (2) 4++ ((6+(7))8−(10)) ) kiegyensúlyozatlan bináris keres®fa kiegyensúlyozásával pedig ( ((2)4−) 6◦ ((7)8◦(10)) ) adódik, amire az (
α
T++ ((β B−◦+
séma [2] szolgál, ahol
γ ) J− δ )
α, β , γ
és
δ
)
→
((α T◦◦−
β)
B◦ (γ J+◦◦
δ ))
AVL fák, és a három jelb®l álló egyensúlyok
sorban három esetet jelentenek úgy, hogy a bal oldalon az i-edik alternatívának a jobb oldalon is az
i-edik
A fenti séma a példában T=4, (harmadik eset),
β=Ω
A transzformációt (
α
T ((β B
γ)
J
δ)
és
γ=
eset felel meg (i
α=
(2), J=8,
∈ {1; 2; 3}).
δ=
(10), B=6,
+
egyensúllyal
(7) helyettesítéssel alkalmazható.
kett®s forgatásnak is tekinthetjük:
Az
) fára el®ször a J csúcsnál alkalmaztunk egy jobbra
forgatást, aminek eredményeképpen az (
α
T (β B (γ J
kaptuk, majd az eredmény fát balra forgattuk, ami az
δ ) ) bináris keres®fát ( (α T β ) B (γ J δ ) )
AVL fát eredményezte. A kett®s forgatás helyességének ellen®rzéséhez kiszámítjuk az eredmény fa
h = h(α) jelölést. Mivel a kett®s γ) J δ)) = h + 2. Innét J− miatt
egyensúlyait. Most is bevezetjük a el®tti fában T++, azért
h((β
B
forgatás
h(((β B γ)) = h+1 és h(δ) = h . Most B lehetséges egyensúlyai szerint három
eset van. (1) B− esetén
h(β) = h és h(γ) = h − 1 ⇒ az eredmény fában T◦ és J+. (2) B◦ esetén h(β) = h és h(γ) = h ⇒ az eredmény fában T◦ és J◦. (3) B+ esetén h(β) = h − 1 és h(γ) = h ⇒ az eredmény fában T− és J◦. Mindhárom esetben h((α T β)) = h + 1 = h((γ J δ)), így B◦. Ezzel beláttuk a kett®s forgatási séma helyességét. Vegyük észre, hogy a fentiek alapján, a B csúcsnak a kett®s forgatás
s-sel, a T és a J csúcsoknak pedig a kett®s forgatás utáni rendre st -vel, illetve sj -vel jelölve a következ® összefüggéseket
el®tti egyensúlyát egyensúlyát írhatjuk fel:
st = −b(s + 1)/2c
és
sj = b(1 − s)/2c
Az eddigi két kiegyensúlyozási séma mellett természetes módon adódnak ezek tükörképei, a forgatások el®tt a T−− csúccsal a gyökérben. következ®k [2]:
51
Ezek tehát a
( (α B−
β ) T−− γ ) → ( α B◦ (β T◦ γ ) ) γ )) T−− δ ) → ( (α B◦◦− β ) J◦ (γ T+◦◦ δ ) ) sb = −b(s + 1)/2c és st = b(1 − s)/2c csúcs kett®s forgatás el®tti egyensúlya; sb , illetve st pedig
( (α B+ (β J−◦+ ahol
s
a J
rendre a B és T csúcsoknak a kett®s forgatás utáni egyensúlya Eddig nem beszéltünk arról, hogy az AVL fában az új csúcs beszúrása után mely csúcsoknak és milyen sorrendben számoljuk újra az egyensúlyát, sem hogy mikor ütemezzük be a kiegyensúlyozást.
Csak a beszúrás nyomvo-
nalán visszafelé haladva kell újraszámolnunk az egyensúlyokat, és csak itt kell kiegyensúlyoznunk, ha kiegyensúlyozatlan csúcsot találunk. Így a futási
O(lg n).
id® a fa magasságával arányos marad, ami AVL fákra
Most tehát
részletezzük a beszúró és kiegyensúlyozó algoritmus m¶ködését. Ennek során a fa magassága vagy eggyel növekszik (d=igaz), vagy ugyanannyi marad (d=hamis).
AVLbeszúr(&t, k, &d)
t=
A
t := new Csúcs(k ) d := igaz A
A
k < t → kulcs A AVLbeszúr(t → bal, k, d) d
k > t → kulcs AVLbeszúr(t → jobb, k, d)
balRészfaN®tt(t, d)
SKIP
jobbRészfaN®tt(t, d)
balRészfaN®tt(&t, &d)
d :=
d
A
AELSE
SKIP
hamis
t → s = −1
A
b := t → bal t → s := t → s − 1 b → s = −1 A kiegyensúlyozMM(t, b) kiegyensúlyozMP(t, b) d := (t → s < 0) d := hamis
jobbRészfaN®tt(&t, &d)
A
t→s=1 j := t → jobb j→s=1
A
t → s := t → s + 1
kiegyensúlyozPP(t, j )
kiegyensúlyozPM(t, j )
d := hamis 52
d := (t → s > 0)
kiegyensúlyozPP(&t, j )
t → jobb := j → bal j → bal := t j → s := t → s := 0
t := j
t → bal := b → jobb b → jobb := t b → s := t → s := 0 t := b
kiegyensúlyozPM(&t, j )
kiegyensúlyozMM(&t, b)
kiegyensúlyozMP(&t, b)
b := j → bal
j := b → jobb
t → jobb := b → bal
b → jobb := j → bal
j → bal := b → jobb
t → bal := j → jobb
b → bal := t b → jobb := j
j → bal := b j → jobb := t
t → s := −b(b → s + 1)/2c
b → s := −b(j → s + 1)/2c
j → s := b(1 − b → s)/2c b → s := 0
t → s := b(1 − j → s)/2c j → s := 0
t := b
t := j
Az AVL fába való beszúrást röviden összefoglalva: 1. Megkeressük a kulcs helyét a fában. 2. Ha a kulcs benne van a fában, KÉSZ vagyunk. 3. Ha a kulcs helyén egy üres részfa található, beszúrunk az üres fa helyére egy új, a kulcsot tartalmazó levélcsúcsot, azzal, hogy ez a részfa eggyel magasabb lett. 4. egyet fölfelé lépünk a keres®fában. Mivel az a részfa, amib®l fölfele léptünk, eggyel magasabb lett, az aktuális csúcs egyensúlyát megfelel®képp módosítjuk. (Ha a jobb részfa lett magasabb, hozzáadunk az egyensúlyhoz egyet, ha a bal, levonunk bel®le egyet.) 5. Ha az aktuális csúcs egyensúlya 0 lett, akkor az aktuális csúcshoz tartozó részfa alacsonyabb ága hozzán®tt a magasabbikhoz, tehát az aktuális részfa most ugyanolyan magas, mint a beszúrás el®tt volt, és így egyetlen más csúcs egyensúlyát sem kell módosítani: KÉSZ vagyunk. 6. Ha az aktuális csúcs új egyensúlya 1 vagy -1, akkor el®tte 0 volt, ezért az aktuális részfa magasabb lett eggyel. Ekkor a 4. ponttól folytatjuk. 7. Ha az aktuális csúcs új egyensúlya 2 vagy -2, fát ki kell egyensúlyozni. A
15
akkor a hozzá tartozó rész-
kiegyensúlyozás után az aktuális részfa visszanyeri
15 A 2 és -2 eseteket a struktogramban nem számoltuk ki expliciten, hogy az egyensúly tárolására elég legyen két bit.
53
a beszúrás el®tti magasságát,
ezért már egyetlen más csúcs egyensúlyát sem
kell módosítani: KÉSZ vagyunk.
kiegyensúlyozás után az aktuális részfa visszanyeri a beszúrás el®tti magasságát, még igazolásra vár. Azt az
Az az állítás, hogy ebben az algoritmusban a
esetet nézzük meg, amikor a kiegyensúlyozandó részfa gyökere T++. A T−− eset hasonlóan fontolható meg.
A T++ esethez tartozó kiegyensúlyozási
sémák [2]:
γ )) → ((α α T++ ((β B−◦+ γ ) J− δ ) ) → ((α (α T++ (β J+
(
T◦
β ) J◦ γ ). T◦◦− β ) B◦ (γ J+◦◦ δ ))
El®ször belátjuk, hogy ha a T csúcs jobboldali J gyereke
+
vagy
−
súlyú,
akkor a fenti sémák közül a megfelel® alkalmazható: Mivel a beszúró algoritmus a fában a beszúrás helyét®l egyesével fölfele lépked, és az els® kiegyensúlyozatlan csúcsnál azonnal kiegyensúlyoz, ez alatt nincs kiegyensúlyozatlan csúcs, azaz az
α, β
és
γ,
illetve a
δ
részfák is kiegyensúlyozottak, ez pedig
éppen a fenti forgatások feltétele, amellett, hogy bináris keres®fát akarunk kiegyensúlyozni, amit viszont a kiegyensúlyozás nélküli beszúró algoritmus garantál. Most még be kell látni, hogy a fenti sémák minden esetet lefednek, azaz J+ vagy J−: egyrészt, J nem lehet a beszúrás által létrehozott új csúcs, mert különben T-nek a beszúrás el®tti jobboldali részfája üres lett volna, tehát most nem lehetne T++. Másrészt, ha a fölfele lépkedés során nulla egyensúlyú csúcs áll el®, akkor a fölötte lev® csúcsok egyensúlya már nem módosul, így kiegyensúlyozatlan csúcs sem állhat el®. Márpedig most T++. Így tehát az új csúcstól T-ig fölfelé vezet® úton minden csúcs, azaz J egyensúlya is vagy
+
−.
Most belátjuk, hogy a kiegyensúlyozások visszaállítják a részfa beszúrás el®tti magasságát. A T++ kiegyensúlyozatlan csúcs a beszúrás el®tt kiegyensúlyozott volt. Mivel a beszúrás, a beszúrás helyét®l kezdve T-ig fölfelé vezet® úton mindegyik részfa magasságát pontosan eggyel növelte, a beszúrás el®tt T+ volt. Ezért a beszúrás el®tt, magas volt.
h = h(α) jelöléssel, a T gyöker¶ részfa h + 2 A beszúrás után tehát T++ lett, és így a T gyöker¶ részfa h + 3
magas lett. A beszúrás utáni, de még a kiegyensúlyozás el®tti állapotot tekintve a továbbiakban megkülönböztetjük a T jobboldali J gyerekére a J+ és a J− eseteket. J+ esetén már láttuk, hogy
h(α) = h = h(β) és h(γ) = h + 1. Ezért a kiegyensúlyozás után h((α T β) J γ)) = h + 2. J− esetén pedig már láttuk, hogy h(α) = h = h(δ) és h((β B γ)) = h + 1. Ezért h(β), h(γ) ≤ h. Így a kiegyensúlyozás után h((α T β ) B (γ J δ)) = h+2.
54
Ezzel beláttuk, hogy a kiegyensúlyozások mindkét esetben visszaállítják a részfa beszúrás el®tti magasságát, mégpedig úgy, hogy a beszúrás által eggyel megnövelt magasságot eggyel csökkentik. Szimmetria okokból ez hasonlóan látható be T−− esetén is, gyelembe véve a B− és a B+ eseteket.
8.11.
AVL fák: a minKivesz(t, min) eljárás
Bináris keres®fákra a minKivesz eljárás:
minKivesz(&t, &minp)
A
minp := t
t → bal =
t := minp → jobb
minKivesz(t
→ bal, minp)
[minp → jobb := ] Ezt például a ((2)4+((6)8◦(10))) AVL fára alkalmazva, a
minp → kulcs = 2
eredmény mellett, a (4++((6)8◦(10))) kiegyensúlyozatlan bináris keres®fa adódna. Látjuk, hogy a kiegyensúlyozatlan 4++ csúcs jobboldli gyereke a 8◦. Ennek az esetnek a kezelésére új kiegyensúlyozási sémát kell alkalmaznunk. Szerencsére egy balra forgatás, a megfelel® egyensúly beállítások mellett most is megoldja a problémát [2]: (α T++ (β J◦ T++ miatt
h = h(α)
γ )) →
jelöléssel nyilván
((α T+
β ) J− γ ).
h(β) = h + 1 = h(γ),
így a forgatás
után az egyensúlyokat a fenti séma szerint kell beállítani. A fa magassága a forgatás el®tt és után is eddigiekkel szemben
h+3
lesz, ez a fajta kiegyensúlyozás tehát az
nem csökkenti az aktuális részfa magasságát.
Ezután az AVL fákra alkalmazott, a megfelel® kiegyensúlyozásokkal kiegészített minKivesz eljárás pl. a következ® lehet (d most azt jelöli, hogy csökkent-e az aktuális részfa magassága):
AVLminKivesz(&t, &minp, &d)
A
minp := t
t → bal =
d := igaz
AVLminKivesz(t
t := minp → jobb [minp → jobb := ]
→ bal, minp, d)
d
A
balRészfaÖsszement(t, d)
55
SKIP
balRészfaÖsszement(&t, &d)
A
t→s=1 t → s := t → s + 1 kiegyensúlyoz_P(t, d) d := (t → s = 0)
kiegyensúlyoz_P(&t, &d)
j := t → jobb j→s=0
j → s = −1 A
j→s=1
A
kiegyensúlyozPM(&t, j )
A kiegyensúlyozP0(&t, j )
d := hamis
kiegyensúlyozPP(&t, j )
kiegyensúlyozP0(&t, j )
t → jobb := j → bal j → bal := t t → s := 1 j → s := −1 t := j
Az algoritmus helyessége hasonlóan gondolható meg, mint a beszúrás esetén. Lényeges különbség azonban, hogy ott minden beszúrást csak egyetlen kiegyensúlyozás követ, míg itt el®fordulhat, hogy a minimális csúcs eltávolítása után, minden felette lév® szinten ki kell egyensúlyozni. HF: Mutassunk ilyen, legalább négy magasságú fát!
8.12.
AVL fák: törlés
Bináris keres®fákra a töröl(t, k ) és a gyökeretTöröl(t) eljárások:
56
töröl(&t, k )
t 6=
A A
k < t → kulcs A k > t → kulcs A k = t → kulcs töröl(t → bal, k ) töröl(t → jobb, k ) gyökeretTöröl(&t)
gyökeretTöröl(&t)
At
→ bal = At → jobb = A p := t p := t
t := p → jobb delete p
SKIP
t → bal 6= ∧ t → jobb 6= minKivesz(t → jobb, p)
t := p → bal p → bal := t → bal ; p → jobb := t → jobb delete p [ t → bal := t → jobb := ; ] delete t ; t := p
Ezeket fogjuk most az az AVLminKivesz(&t, &minp, &d) eljárás mintájára kiegészíteni a
d
paraméterrel; majd a rekurzív töröl hívásokból, valamint a
minKivesz eljárásból való visszatérés után megkérdezzük, csökkent-e az aktuális részfa magassága. Ha igen, a minKivesz eljárás mintájára módosítjuk a
t→s
értéket, ha kell, kiegyensúlyozunk, és ha kell,
AVLtöröl(&t, k, &d)
d
A (t, d)
SKIP
k > t → kulcs Ak = t → kulcs AVLtöröl(t → jobb, k, d) d
A
balRészfaÖsszement
jobbRészfaÖsszement (t, d)
t → bal = p := t
A
t → jobb = p := t
t := p → jobb delete p
t := p → bal delete p
d := igaz
d := igaz
AVLgyTöröl (t, d)
d := hamis
SKIP
AVLgyTöröl(&t, &d)
A
t 6=
A
k < t → kulcs A AVLtöröl(t → bal, k, d)
beállítjuk.
A
d-t
A
t → bal 6= ∧ t → jobb 6= jobbRészfaMinGyökérbe(t, d)
A
d jobbRészfaÖsszement(t, d)
57
SKIP
jobbRészfaMinGyökérbe(&t, &d)
AVLminKivesz(t
→ jobb, p, d)
p → bal := t → bal ; p → jobb := t → jobb ; p → s := t → s [ t → bal := t → jobb := ; ]
delete
t ; t := p
Itt is lehetséges, hogy több szinten, a legrosszabb esetben akár minden szinten is ki kell egyensúlyozni.
Mivel azonban egyetlen kiegyensúlyozás sem
tartalmaz se rekurziót, se ciklust, és ezért konstans számú eljáráshívásból áll, ez sem itt, sem az AVLminKivesz eljárásnál nem befolyásolja a futási id®nek az AVLbeszúr eljárásra is érvényes
M T (n) ∈ Θ(lg n)
(ahol
n = |t|)
nagyságrendjét. HF:
A
balRészfaÖsszement(t, d)
eljárás
mintájára
dolgozzuk
ki
a
jobbRészfaÖsszement(t, d) eljárást, ennek segédeljárásait, és az ehhez szükséges kiegyensúlyozási sémát [2]! Mutassuk be ennek m¶ködését néhány példán! Mutassunk néhány olyan, legalább négy magasságú fát és kulcsot, amelyekre az AVLtöröl eljárás minden, a zikailag törölt csúcs feletti szinten kiegyensúlyozást végez!
8.13.
Tétel:
Az AVL fák magassága* Tetsz®leges
n
csúcsú nemüres AVL fa
h
magasságára:
blg nc ≤ h ≤ 1, 45 lg n
Bizonyítás: Az
blg nc ≤ h
egyenl®tlenség bizonyításához elég azt belátni, hogy ez
tetsz®leges nemüres bináris fára igaz. Egy tetsz®leges bináris fa nulladik 0 1 (gyökér) szintjén legfeljebb 2 = 1 csúcs van, az els® szintjén maximum 2 = 2 2 csúcs, a második szintjén nem több, mint 2 = 4 csúcs. Általában, ha az ii i+1 edik szinten 2 csúcs van, akkor az i + 1-edik szinten legfeljebb 2 csúcs, hiszen minden csúcsnak maximum két gyereke van. Innét egy h mélység¶ 0 1 2 h h+1 bináris fa csúcsainak n számára n ≤ 2 + 2 + 2 + . . . + 2 = 2 − 1 < 2h+1 . Innét
blg nc ≤ lg n < lg 2h+1 = h + 1, A
h ≤ 1, 45 lg n
amib®l
blg nc ≤ h.
egyenl®tlenség bizonyításához elég azt belátni, hogy ez tet-
sz®leges nemüres, kiegyensúlyozott bináris fára (KBF-re) igaz. Ehhez el®ször
58
meghatározzuk egy nimális
fh
számát.
h ≥ 0
magasságú (azaz nemüres) KBF csúcsainak mi-
Nyilván
f0 = 1
és
f1 = 2 ,
hiszen egy nulla magasságú
KBF csak a gyökércsúcsból áll, az egy magasságú KBF-ek pedig ((B)G(J)), ((B)G), vagy (G(J)) alakúak.
< f0 , f1 , f2 , . . . > sorozat szigorúan monoton növekv®. (Ennek igazolásához vegyünk egy i + 1 magas, fi+1 csúcsú t KBF-et! Ekkor a t bal és jobb részfái közül az egyik magassága i. Legyen ez az f részfa! Jelölje most s(b) egy tetsz®leges b bináris fa csúcsainak számát! Akkor fi+1 = s(t) > s(f ) ≥ fi .) Ezután h ≥ 2 esetén fh = 1 + fh−1 + fh−2 . (Ha ugyanis t egy h magasságú, minimális, azaz fh méret¶ KBF, akkor ennek bal és jobb részfáiban Az is világos, hogy az
is, a részfák magasságához mérten a lehet® legkevesebb csúcs van. Az egyik
h − 1 magas, ebben tehát fh−1 csúcs van. Mivel t KBF, a másik részfája h − 1 vagy h − 2 magas. A másik részfában tehát fh−1 vagy fh−2 csúcs van, és fh−2 < fh−1 , tehát a másik részfában fh−2 csúcs van, és így fh = 1 + fh−1 + fh−2 .) részfája kötelez®en
A képlet emlékeztet a Fibonacci sorozatra:
F0 = 0, F1 = 1, Fh = Fh−1 + Fh−2 , ha h ≥ 2. Megjegyzés: A h magasságú, és fh méret¶ KBF-eket ezért Fibonacci fáknak hívjuk. Az el®bbiek szerint egy h ≥ 2 magasságú Fibonacci fa mindig (ϕh−1 G ϕh−2 ) vagy (ϕh−2 G ϕh−1 ) alakú, ahol ϕh−1 és ϕh−2 h − 1, illetve h − 2 magasságú Fibonacci fák. HF: Rajzoljunk
h ∈ 0..4
magasságú Fibonacci fákat!
Megvizsgáljuk, van-e valami összefüggés az
< fh : h ∈ N > h Fh fh
és az
< Fh : h ∈ N >
sorozatok között.
0
1
2
3
4
5
6
7
8
9
0
1
1
2
3
5
8
13
21
34
1
2
4
7
12
20
33
fh = Fh+3 − 1. Teljes indukh ≥ 0 egész számra igaz: Feltéve,
A fenti táblázat alapján az els® néhány értékre cióval könnyen látható, hogy ez tetsz®leges
0 ≤ h ≤ k ≥ 1 esetén igaz, h = k + 1-re: fh = fk+1 = 1 + fk + fk−1 = 1 + Fk+3 − 1 + Fk+2 − 1 = Fk+4 − 1 = Fh+3 − 1.
hogy
Tudjuk, hogy
√ !h 1 1+ 5 Fh = √ − 2 5
59
√ !h 1− 5 2
Fh -ra vonatkozó explicit képlet segítségével összefüggést adunk tetsz®leges KBF n mérete és h magassága között. √ !h+3 √ !h+3 1+ 5 1 1− 5 −1≥ n ≥ fh = Fh+3 − 1 = √ − 2 2 5
Az
√ !h+3 √ !h+3 1 1+ 5 1− 5 −1 ≥√ − 2 2 5 √ h+3 √ √ < 1. Eszerint 2 < 5 < 3, azért |1 − 5|/2 < 1 és 1−2 5
Mivel
√ !h+3 1+ 5 1 1 − 1 − 1 = √ n> √ 2 5 5
√ !3 1+ 5 2
√ !h √ 1+ 5 1+ 5 − √ 2 5
Mivel
1 √ 5
√ !3 √ √ √ √ √ 1+ 5 1 + 3 5 + 3( 5)2 + ( 5)3 16 + 8 5 2+ 5 √ √ = = = √ 2 8 5 8 5 5
Ezt behelyettesítve az el®bbi,
n
-re vonatkozó egyenl®tlenségbe:
√ 2+ 5 n> √ 5
√ !h √ 1+ 5 1+ 5 − √ 2 5
Az els® együtthatót tagokra bontva, a disztributív szabállyal:
n>
√ !h 1+ 5 2 +√ 2 5
√ !h √ 1+ 5 1+ 5 − √ 2 5
Most
2 √ 5 Eszerint
√ !h √ 1+ 5 1+ 5 − √ ≥ 0 ⇐⇒ 2 5 h≥1
esetén
n>
√ !h √ 1+ 5 1+ 5 ≥ ⇐⇒ h ≥ 1 2 2
√ !h 1+ 5 2 60
h=0
-ra pedig
n = 1,
n=
és így
√ h 1+ 5 2
A fentiekb®l tetsz®leges, nemüres KBF
n≥
n
méretére és
h
magasságára
√ !h 1+ 5 2 √
Innét, ha vesszük mindkét oldal kettes alapú logaritmusát, majd
lg 1+2
5
-tel
osztunk:
h≤ Mivel
1, 44 < 1, 44042 <
nemüres KBF
n
1
lg
méretére és
√ 1+ 5 2
h
1
√
lg 1+2
5
lg n
< 1, 4404201 < 1, 45,
azért tetsz®leges,
magasságára
h ≤ 1, 45 lg n
9.
Általános fák
Az általános fák esetében, a bináris fákkal összehasonlítva, egy csúcsnak tetsz®legesen sok gyereke lehet. Itt azonban, tetsz®leges csúcshoz tartozó részfák száma pontosan egyenl® a gyerekek számával, azaz nem tartoznak hozzá üres részfák. Ha a gyerekek sorrendje lényeges, akkor
rendezett fákról beszélünk.
Általános fákkal modellezhetjük például a számítógépünkben a mappák hierarchiáját, a programok blokkstruktúráját, a függvénykifejezéseket, a családfákat és bármelyik hierarchikus struktúrát. Vegyük észre, hogy ugyan minden konkrét általános fában van az egy csúcshoz tartozó gyerekek számára valamilyen még nem tekinthet®
r-árisnak,
r
fels® korlát, de ett®l a fa
mert ez a korlát nem abszolút: a fa tetsz®-
leges csúcsa gyerekeinek száma tetsz®legesen növelhet®. Másrészt, mivel itt nem értelmezzük az
üres részfa fogalmát, ez mégsem általánosítása az r-áris
fa fogalmának. Értelmezzük azonban a gyökércsúcs (nincs szül®je) és a levélcsúcs (nincs gyereke) fogalmát, azaz továbbra is gyökeres fákról beszélünk. Az általános fák természetes ábrázolási módja a
bináris láncolt reprezentáció.
egy az els® gyerekre, tv pedig ∗p csúcs akkor levél, ha p → egy = ; és a ha p → tv = .
Itt egy csúcs szerkezete a következ® (ahol most a következ® testvérre mutat). A
∗p
csúcs akkor utolsó testvér,
16
16 Ellentétben az ún. szabad fákkal, amik irányítatlan, körmentes gráfok. 61
Csúcs + egy, tv : Csúcs* // egy : els® gyerek; tv : következ® testvér + kulcs : T // T ismert típus + Csúcs() { egy := tv := } // egycsúcsú fát képez bel®le + Csúcs(x:T) { egy := tv := ; kulcs := x } Természetesen itt is lehet
szül® pointer, ami a gyerekek közös szül®jére mutat
vissza. HF: Próbáljunk megadni az általános fákra másfajta láncolt reprezentációkat is!
Hasonlítsuk össze az általunk adott ábrázolásokat és a bináris láncolt
reprezentációt, memóriaigény és rugalmasság szempontjából! A szöveges (zárójeles) reprezentációban az általános fáknál a gyökeret el®re szokás venni.
t1 . . . tn ),
Így egy nemüres fa általános alakja (G
gyökércsúcs tartalma,
t1 . . . tn
ahol G a
pedig a részfák.
Így pl. az (1 (2 (5)) (3) (4 (6) (7)))) általános fában az 1 van a gyökérben, a gyerekei a 2, a 3 és a 4, a hozzájuk tartozó részfák pedig sorban a (2 (5)), a (3) és a (4 (6) (7))). A fa levelei az 5, a 3, a 6 és a 7. HF: Rajzoljuk le a fenti fát! Írjunk programot, ami kiír egy binárisan láncolt fát a fenti zárójeles alakban! olvassa!
Írjunk olyat is, ami egy szövegfájlból vissza-
Készítsük el a kiíró és a visszaolvasó programokat az általunk ki-
dolgozott alternatív láncolt ábrázolásokra is!
(A visszaolvasó programokat
általában nehezebb megírni.) Az általános fa preorder bejárása
17
az
egy ∼ bal
és
tv ∼ jobb megfeleltetéssel
a bináris reprezentáció preorder bejárását igényli. Az általános fa postorder bejárásához
18
azonban (az el®bbi megfeleltetéssel) a bináris reprezentáció
inorder bejárása szükséges.
19
preorder(t)
postorder(t)
t 6=
t 6= postorder(t → egy )
feldolgoz(t) preorder(t
→ egy )
feldolgoz(t)
t := t → tv
t := t → tv
17 el®ször a gyökér, majd sorban a gyerekeihez tartozó részfák 18 el®bb sorban a gyökér gyerekeihez tartozó részfák, végül a gyökér
19 A fájlrendszerekben általában preorder bejárás szerint keresünk, míg a függvénykifejezéseket (eltekintve most a lusta kiértékelést®l, aminek a tárgyalása túl messzire vezetne) postorder bejárással értékeljük ki.
62
HF: Lássuk be a fenti bejárások helyességét! (Ötlet: A testvérek listájának mérete szerinti teljes indukció pl. célravezet®.) Lássuk be egy ellenpélda segítségével, hogy az általános fa inorder bejárása reprezentáció egyik nevezetes bejárásával
21
20
nem szimulálható a bináris
sem! Írjuk meg a bináris láncolt
reprezentációra az általános fa inorder bejárását és szintfolytonos bejárását is! HF: Írjuk meg a fenti bejárásokat az általunk adott aletrnatív láncolt reprezentációkra is! Írjunk olyan programokat, amelyek képesek tetsz®leges általános fa egy adott reprezentációjából egy adott másik ábrázolású másolatot készíteni!
10.
B+ fák és m¶veleteik
http://aszt.inf.elte.hu/∼asvanyi/ad/B+ fa.pdf
11.
Gyorsrendezés (Quicksort)
http://aszt.inf.elte.hu/∼asvanyi/ad/FeketeIstvan/quick_sort_FI.doc
Gyorsrendezés(A[1..n])
Quicksort(A[1..n])
Quicksort(A[p..r])
p
q :=
szétvág(A[p..r])
Quicksort(A[p..q Quicksort(A[q
20 A (G
− 1])
SKIP
+ 1..r])
t1 . . . tn ) fára n > 0 esetén el®bb t1 -et járja be, majd feldolgozza t2 . . . tn részfákat; n = 0 esetén csak feldolgozza G-t.
bejárja sorban a
21 preorder, inorder, postorder, szintfolytonos
63
G-t, aztán
fv szétvág(A[p..r]) x := A[r] ; i := p i < r ∧ A[i] ≤ x i := i + 1 i
A
j
csere(A[i], A[j])
i := i + 1 j := j + 1
SKIP
SKIP
A[r] := A[i] ; A[i] := x
return i Vezessük be a következ® jelöléseket: • A0
az
A
vektor kezdeti állapota, a szétvág függvény meghívásakor.
• A[k..m] ≤ x akkor és csak akkor, ha tetsz®leges l -re, k ≤ l ≤ m esetén A[l] ≤ x • A[k..m] > x akkor és csak akkor, ha tetsz®leges l -re, k ≤ l ≤ m esetén A[l] > x
A szétvág fv el®feltétele: p < r (A
p
és
r
indexhatárok itt természetesen konstansok.)
A szétvág fv második ciklusának invariánsa:
A[p..r] az A0 [p..r] permutációja ∧ A[r] = x ∧ p ≤ i < j ≤ r ∧ A[p..(i − 1)] ≤ x ∧ A[i..(j − 1)] > x
A szétvág fv utófeltétele:
A[p..r] az A0 [p..r] permutációja ∧ p ≤ i ≤ r ∧ A[i] = A0 [r] ∧ A[p..(i − 1)] ≤ x ∧ A[(i + 1)..r] > x A szétvágás m¶veletigénye nyilván lineáris, hiszen a két ciklus együtt vagy
r−p
iterációt végez.
64
r −p−1
A rekurzív eljárás m¶veletigényének ezen alapuló elemzése a saját, kézzel írt el®adás jegyzetben, illetve a jelzett szakirodalomban! vizsga anyagában] csak
mT (n) ∈ O(n lg n)
és
M T (n)
(Az el®adáson [és a ∈ Ω(n2 ) bizonyítása
szerepel.)
mT (n), AT (n) ∈ Θ(n lg n) M T (n) ∈ Θ(n2 ) Ismert, hogy kisméret¶ tömbökre a beszúró rendezés hatékonyabb, mint a gyors rendezések (mergesort, heapsort, quicksort). Ezért a Quicksort(A[p..r]) eljárás jelent®sen gyorsítható, ha kisméret¶ tömbökre áttérünk beszúró rendezésre. Mivel a szétvágások során sok kicsi tömb áll el®, így ezzel a program futása sok ponton gyorsítható:
Quicksort(A[p..r])
p
q :=
szétvág(A[p..r])
− 1]) Quicksort(A[q + 1..r])
Quicksort(A[p..q
Itt
c∈N
beszúró_rendezés(A[p..r])
konstans. Optimális értéke sok tényez®t®l függ, de általában 20 és
30 között mozog. HF: Hogyan tudnánk az összefésül® rendezést hasonló módon gyorsítani? El®rendezett inputokra a Quicksort lelassul, mert a szétvág fv egyenetlenül vág. Annak érdekében, hogy az ilyen balszerencsés bemenetek valószín¶ségét csökkentsük, és azért is, mert az el®rendezett inputok rendezése a gyakorlatban egy fontos feladatosztály, érdemes a szétvágáshoz használt elemet az
A[p..r]
résztömb egy véletlenszer¶ elemének választani:
65
fv szétvág(A[p..r]) i :=
random(p, r )
x := A[i] ; A[i] := A[r] i := p i < r ∧ A[i] ≤ x i := i + 1 i
A
j
A[j] ≤ x csere(A[i], A[j]) i := i + 1 j := j + 1
A[r] := x SKIP
A[r] := A[i] ; A[i] := x
return i 11.1.
A gyorsrendezés végrekurzió-optimalizált változata*
Gyorsrendezés(A[1..n])
Quicksort(A, 1, n)
Quicksort(A[], p, r )
p
szétvág(A[p..r])
Quicksort(A, p, q
− 1)
p := q + 1 beszúró_rendezés(A[p..r])
66
12.
Az összehasonlító rendezések alsókorlát-elemzése
http://people.inf.elte.hu/fekete/algoritmusok_jegyzet/ .
19_fejezet_Rendezesek_alsokorlat_elemzese.pdf
67
