Kiválasztás kupaccal A bináris kupac egy majdnem teljes bináris fa, amely minden szintjén teljesen kitöltött kivéve a legalacsonyabb szintet, ahol balról jobbra haladva egy adott csúcsig vannak elemek. A fát egy tömbben reprezentáljuk, minden elem a szint szerinti bejárás szerinti sorszámának megfelel˝o eleme a tömbnek. A kupacot reprezentáló A tömbhöz két értéket rendelünk, hossz(A) a tömb mérete, kupacmeret(A) a kupac elemeinek a száma. A kupac gyökere A[1], a szerkezeti kapcsolatok egyszer˝uen számolhatóak: • A[i] bal fia A[2i] • A[i] jobb fia A[2i + 1] • A[i] apja A[bi/2c] A kupac minden gyökért˝ol különböz˝o elemére teljesül, hogy az értéke nem lehet nagyobb, mint az apjáé. Ennek következménye, hogy a kupac minden részfájára teljesül, hogy a gyökéreleme maximális. MAXIMUM-KUPACOL Eljárás A MAXIMUM-KUPACOL eljárás helyreállítja az A[i] elemre a kupactulajdonságot. Az elemet süllyeszti cserékkel mindaddig, amíg a tulajdonság sérül. MAXIMUM-KUPACOL(A,i) l:=2i //az A[i] elem bal fiának indexe r:=2i+1 //az A[i] elem jobb fiának indexe if l<=kupacmeret(A) and A[l]>A[i] then max:=l else max:=i if r<=kupacmeret(A) and A[r]>A[max] then max:=r // A[max] a három elem közül a legnagyobb if max!=i then {Csere(A[i],A[max]) MAXIMUM-KUPACOL(A,max)} Példa A=[5,14,13,8,3,4,6,2] MAXIMUM-KUPACOL(A,1) A=[14,5,13,8,3,4,6,2] A=[14,8,13,5,3,4,6,2] Kiválasztás kupaccal Az algoritmus során a for ciklus j értékkel való végrehajtása után a kupac az els˝o j elemb˝ol az i legkisebbet tartalmazza. Kupacvalaszt(A,i) Kupacmeret(A):=i for j= [i/2] to 1 MAXIMUM KUPACOL(A,j) // az elso i elembol egy kupac 1
5 14 8
13 3
14
4
6
2
5 8
13 3
2
4
6
14 8
5
13 3
4
6
2
1. ábra.
for j=i+1 to n {if A[1]>A[j] then {Csere(A[1],A[j]) MAXIMUM KUPACOL(A,1)}} return A[1] Futási id˝o: O(i) + (n − i)O(log i) Példa A=[2,5,7,3,6,4,8], k=3 A=[2,5,7|3,6,4,8] A=[7,5,2|3,6,4,8] A=[3,5,2|7,6,4,8] A=[5,3,2|7,6,4,8] A=[4,3,2|7,6,5,8] Minimum és maximum egyideju˝ választása A feladat adott n méret˝u tömb elemeib˝ol kiválasztani a maximális és minimális elemet. MaxMin(A) if (n%2=0) then {k:=2 if (A[1]
while(kA[maxi] then maxi:=k+2} else {if A[k+2]A[maxi] then maxi:=k+1} k:=k+2} Futási id˝o Az algoritmus legfeljebb b3n/2c összehasonlítást végez. Bináris keres˝ofák Az F = (M,R,Adat) absztrakt adatszerkezetet bináris keres˝ofának nevezzük, ha • F bináris fa, R = {bal, jobb, apa}, bal, jobb, apa : M → M, • Adat : M → Elemtip és Elemtip-on értelmezett egy ≤ lineáris rendezési reláció, • (∀x ∈ M)(∀p ∈ Fbal(x) )(∀q ∈ Fjobb(x) )(kulcs(p) ≤ kulcs(x) ≤ kulcs(q)) InorderBejaras(F,M) if F!=Nil then {InorderBejaras(bal(F),M) M(F) InorderBejaras(jobb(F),M)} Az InorderBejaras algoritmus a bináris keres˝ofa elemeit a kulcsok rendezés szerinti sorrendjében látogatja meg. Adott kulcsú elem keresése KERES(F,k) if F=Nil or k=kulcs(F) then return F If k< kulcs(F) then return KERES(bal(F),k) else return KERES(jobb(F),k)
KERES2(F,k) while(F!=Nil and k!=kulcs(F)) {if k
3
13 >
<=
23
6 <=
>
>
3
28
9 <=
8
2. ábra.
FabanMinimum(F) while(bal(F)!=Nil) F:=bal(F) return F
FabanMaximum(F) while(jobb(F)!=Nil) F:=jobb(F) return F Futási id˝o: A fa magasságával arányos. Rákövetkez˝o, megel˝oz˝o elem keresése FabanKovetkezo(p) if jobb(p)!=Nil then return FabanMinimum(jobb(p)) q:=apa(p) while(q!=Nil and p=jobb(q)) {p:=q q:=Apa(q)} return q 4
FabanMegelozo(p) if bal(p)!=Nil then return FabanMaximum(bal(p)) q:=apa(p) while(q!=Nil and p=bal(q)) {p:=q q:=Apa(q)} return q Futási id˝o: A fa magasságával arányos. Beszúrás bináris keres˝ofába A fát a gyökérpontja által adtuk meg. Beszur(F,z) y:=Nil x:=F while(x!=Nil) {y:=x if kulcs(z)
13 >
<=
23
6 <=
>
>
3
28
9 >
<=
8
11
3. ábra.
13 >
<=
23
8 <=
3
>
>
28
9 >
11
4. ábra.
6
Keres˝ofák magassága Példa: Ha az 1, 2, . . . , n sorrendben szúrunk pontokat egy üres fába a magasság n lesz. Tétel Az n csúcsból álló véletlen építés˝u bináris fák magassága O(log n). Kiegyensúlyozott bináris keres˝ofák magassága O(log n) • piros fekete fa • AVL fa • önszervez˝o bináris keres˝ofák (splay fák) Optimális bináris keres˝ofa építése Tegyük fel, hogy ismerjük minden a fában szerepl˝o ki kulcsra a keresésének gyakoriságát, ami pi (i = 1, . . . , n). Továbbá adott minden i-re a ki és ki+1 közés es˝o sikertelen keresések gyakorisága q0 , q1 , . . . , qn . Értelemszer˝uen q0 a k1 -nél kisebb, qn a kn -nél nagyobb kulcsok gyakorisága. Ha felépítünk egy F bináris keres˝ofát x1 , . . . , xn pontokkal, akkor egy sikeres keresés költsége a gyakoriság szorozva a pont mélységével. A sikertelen keresésekhez hozzárendelhetünk új yi pontokat, ahol a keresés kilép a fából. Ekkor az F fára a várható keresési költség n
n
C(F) = ∑ pi dF (xi ) + ∑ q j dF (y j ). i=1
j=0
a cél azon fa megkonstruálása, amelyre ez az összeg minimális. Rekurzív összefüggés Tegyük fel, hogy van egy optimális F keres˝ofa a k1 , . . . , kn kulcsokból, aminek xr a gyökere. Ekkor a baloldali részfa F1 a k1 , . . . , kr−1 kulcsokból álló bináris keres˝ofa, a jobboldali részfa F2 pedig a kr+1 , . . . , kn csúcsokból áll. Nyilván mindkett˝o optimális kell legyen, különben lecserélve o˝ ket F helyett is jobbat kapnánk. Könnyen igazolható, hogy n
n
C(F) = C(F1 ) +C(F2 ) + ∑ pi + ∑ q j . i=1
j=0
Részproblémák: Minden 0 ≤ i ≤ j ≤ n-re legyen OPT (i, j) az optimális bináris keres˝ofa költsége a pi+1 , . . . , p j sikeres és a qi , . . . , q j sikertelen keresési gyakoriságokkal. OPT (i, i) = qi j
OPT (i, j) =
∑
u=i+1
j
pu + ∑ qv + min {OPT (i, r − 1) + OPT (r, j)}. v=i
i
A rekurzív összefüggések alapján a feladat megoldható átlós táblázatkitöltéssel. Kiskérdések • Linkiválaszt algoritmus • Kupacvalaszt algoritmus 7
• bináris keres˝ofa definíciója • keresés bináris keres˝ofában Szorgalmi feladat Adjunk meg egy eljárást, amely kiválasztja a legkisebb és a második legkisebb elemet n elemb˝ol n − 1 + dlog ne elempár összehasonlításával. Beküldés: [email protected], Leírás +magyarázat + futási id˝o elemzés • els˝o négy megoldó 8-8 pont • a második négy megoldó 5-5 pont A szerzett plusszpontok a vizsga minimumkövetelményébe nem számítanak bele.
8
