AVL fa Def A P ∈ F pont (magasság-)egyensúlya: Egy(P) = h(Job(P)) − h(Bal(P)) Def Az F binfa AVL-fa, ha (∀P ∈ F)(−1 ≤ Egy(P) ≤ 1) tétel Ha F AVL-fa, akkor h(F) ≤ 1.44 · lg(n + 1), ahol n az F fa pontjainak számát jelöli. Biz Legyen Nm az m magasságú, legkevesebb pontot tartalmazó AVL-fa pontjainak száma. Ekkor Nm ≥ |F|, ha F AVL-fa és h(F) = m. N0 = 0 , N1 = 1 , N2 = 2 és Nm = 1 + Nm−2 + Nm−1 , ha m > 1. Legyen Bi = Ni + 1. Ekkor B0 = 1√,B1 = 2 és Bm = Bm−2 + Bm−1 ha (m > 1). lemma Φm ≤ Bm , ahol (Φ = 1 + 5)/2. 1 = Φ0 ≤ B0 , Φ ≤ B1 . Teljes indukció alapján, ha 2, . . . , m − 1-re áll az egyenl˝otlenség Bm = Bm−2 + Bm−1 ≤ Φm−2 + Φm−1 = Φm−2 (1 + Φ). Viszont (1 + Φ) = Φ2 , így a lemmát igazoltuk. Tehát Φm ≤ Bm = Nm + 1 ≤ n + 1, azaz m · log Φ ≤ log(n + 1). Következésképpen h(F) = m ≤ log1 Φ log(n + 1) = 1.44 · log(n + 1). Muveletek ˝ Mind a beszúrás mind pedig a törlés esetén az algoritmus els˝oként a bináris keres˝ofáknál tanultaknak megfelel˝oen beszúrja illetve törli az elemet, majd a beszúráshoz illetve törléshez tartozó b˝ovít˝oúton illetve törl˝oúton felfele haladva lokális forgatásokkal helyreállítja a tulajdonságot. Def U = [P0 , . . . , Pm ] X-b˝ovít˝oút, ha • ha X < Adat(Pi ) akkor Pi+1 = Bal(Pi ) és ha X > Adat(Pi ) akkor Pi+1 = Jobb(Pi ) i < m esetén • ha X < Adat(Pm ) akkor Bal(Pm ) = Nil és ha X > Adat(Pm ) akkor Jobb(Pm ) = Nil Def U = [P0 , . . . , Pm ] X-törl˝oút, ha • ∃0 ≤ t ≤ m amelyre Adat(Pt ) = X és ha X < Adat(Pi ) akkor Pi+1 = Bal(Pi ) és ha X > Adat(Pi ) akkor Pi+1 = Jobb(Pi ) i < t esetén • t = m és Bal(Pt ) = Nil vagy Jobb(Pt ) = Nil vagy t < m és Bal(Pt ) 6= Nil ∧Jobb(Pt ) 6= Nil és Pt+1 = Jobb(Pt ),Pi+1 = Bal(Pi ) ha (t < i < m) Jobbra és balraforgatás BalraForgat(F,x) y:=jobb(x) jobb(x):=bal(y) if bal(y)!=Nil(T) then apa(bal(y)):=x apa(y):=apa(x) If apa(x)=Nil(F) Then F:=y else if x=bal(apa(x)) 1
then bal(apa(x)):=y else jobb(apa(x):=y bal(y):=x apa(x):=y A JobbraForgat teljesen hasonló, x helyére a balfia kerül.
X 2
Y
a
0 1 b
c
Y -1 0
X
c 1 0 a
b
Egyszeres balra forgatás
1. ábra. Kétszeres forgatás A kétszeres balra forgatás esetén feltesszük, hogy bal( jobb(x) 6= Nil, ez a feltétel teljesül, amikor a helyreállítás során ezt a forgatást kell használni. KetszeresBalraForgat(F,x) y:=jobb(x) z:=bal(jobb(x)) jobb(x):=bal(z) if bal(z)!=Nil then apa(bal(z)):=x bal(y):=jobb(z) if jobb(z)!=Nil then apa(jobb(z)):=y apa(z):=apa(x) If apa(x)=Nil Then F:=z 2
Y -2
X c -1 0 a
b
X 0 1
Y
a
0 -1 b
c
Egyszeres jobbra forgatás
2. ábra.
else if x=bal(apa(x)) then bal(apa(x)):=z else jobb(apa(x):=z bal(z):=x apa(x):=z jobb(z):=y apa(y):=z A JobbraForgat teljesen hasonló, x helyére a balfiának jobbfia kerül. A helyreállítás id˝oigénye Miután a b˝ovít˝o és törl˝oút minden eleménél legfeljebb egy forgatást hajtunk végre az id˝oigény O(log(n)). Igazolható, hogy beszúrás esetén konstans. Demonstrációs programok AVL fák esetén. http://people.ksp.sk/~kuko/bak/index.html http://www.csi.uottawa.ca/~stan/csi2514/applets/avl/BT.html Általános keres˝ofák Az általános keres˝ofa olyan absztrakt adatszerkezet, amely fa és minden cellájában nem csak egy kulcs (adat) hanem kulcsok egy rendezett sorozata van. Tehát minden p ∈ F esetén Adat(p) = [a1 , . . . , ak ]. Ekkor azt mondjuk, hogy p rangja k, Rang(p) = k. Def. Az F fa (általános) keres˝ofa, ha ∀p ∈ F esetén: 3
A 2
B
a
-1
C d
b
-1 0 1
c
C 0
A
B
0 0 -1 a
b
c
1 0 0
d
Kétszeres balra forgatás
3. ábra.
• p-nek Rang(p)+1 = Fok(p) számú fia van. • Adat(p) = [a1 , . . . , ak ] egy rendezett sorozat. • max(F f iu(p, i)) ≤ ai ≤ min(F f iu(p, i + 1)), minden i = 1, . . . , Rang(p), ahol F f iu(p, i) az F fa f iu(p, i) gyöker˝u részfája. Def. Az F fa t-rend˝u (t ≥ 2) B-fa, ha teljesül rá az alábbi 4 feltétel: • Általános keres˝ofa. • A gyökér kivételével minden p ∈ F pontra t − 1 ≤ Rang(p) ≤ 2t − 1, a gyökér rangja legfeljebb 2t − 1. • Minden p ∈ F nem levél pontra Fiu(p, i) 6= Nil, i = 1, . . . , Rang(p) + 1. • Minden p ∈ F levélpontra d(p) = h(F), azaz minden levél pont mélysége azonos. Egy p pontot telítettnek nevezünk, ha Rang(p) = 2t − 1, illetve minimálisnak, ha Rang(p) = t − 1. Továbbá feltesszük, hogy minden ponthoz tartozik egy Level boolean változó, ami akkor igaz, ha a pont levél. B-fák felhasználása: B fákat olyan adatszerkezetek esetén használják, amelyek nem férnek el a gyorsmemóriában. Az aktuális pont van a gyorsmemóriában, és amikor másik lapra érünk azt a háttértárból olvassuk be. Következésképpen a m˝uveletek hatékonysága els˝osorban a pontokhoz történ˝o hozzáférések számától függ. B-fák magassága Tétel: Minden n adatot tartalmazó t-rend˝u F B-fára h(F) ≤ logt 4
n+1 2
+ 1.
C B
-2 d
1
A
a
b
-1 0 1
c
A 0
B
C
0 0 -1 a
b
c
1 0 0
d
Kétszeres jobbra forgatás
4. ábra.
Biz. Vizsgáljuk meg, hogy egy h magasságú t rend˝u B-fában mennyi az adatok minimálisan lehetséges száma. A gyökér legalább egy adatot tartalmaz, és van két fia. A els˝o szinten mindkét fiú legalább t − 1 adatot tartalmaz, és mindkett˝onek van legalább t fia. Azaz a második szinten legalább 2t pont van. A második szinten a 2t pont mindegyike tartalmaz legalább t − 1 adatot, így a szinten az adatok száma 2t(t − 1) tovább minden pontnak van legalább t fia, így a következ˝o szinten a pontok száma 2t 2 . Teljes indukcióval igazolható, hogy az i-edik szinten a pontok száma legalább 2t i−1 , így az adatok száma legalább 2t i−1 (t − 1). Következésképpen egy h magas fában az adatok száma h−1
1 + ∑ 2t i−1 (t − 1) = 1 + 2(t − 1) i=0
Tehát n ≥ 2t h−1 − 1, így h ≤ logt
n+1 2
t h−1 − 1 = 2t h−1 − 1. t −1
+ 1. Keresés B fában
A keresés általánosítása a bináris keres˝ofák esetén használt keres algoritmusnak. Bfakeres(F,x) i:=1 while i<=Rang(F) and k>kulcs(F,i) i:=i+1 if i<=Rang(F) and k=kulcs(F,i) Then return(F,i) 5
P= a1, .... , ak
Fiu(P,0)
Fiu(P,k1)
Fiu(P,1)
Fiu(P,k)
Általános keresőfa
5. ábra.
if level(F) Then return Nil else return BFakeres(Ffiu(F,i),k) Pontok szétvágása A Beszúrás során a pontot abba a levélbe szúrjuk be, ahol a sikertelen keresése véget érne. Ekkor ha ez a levél telített, akkor a beszúrás sértené a pontok rangjára vonatkozó korlátot. Ennek megel˝ozésére a beszúrás során megszüntetjük a telített pontokat. Erre használhatjuk a telített pontok szétvágását megvalósító alábbi eljárást. Az algoritmus az y pontot, amelyre Rang(y) = 2t − 1 és amely az x pont i-edik fia vágja ketté a közepén. A középs˝o adat felmegy az x-be. Bfavag(x,i,y) Letesit(z: Bfapont) Level(z):=Level(y) Rang(z):=t-1 for j=1 to t-1 kulcs(z,j):=kulcs(y,j+t) if notLevel(y) Then for j=1 to t Fiu(z,j):=Fiu(y,j+t) Rang(y):=t-1 for j:=Rang(x)+1 down to i+1 Fiu(x,j+1):=Fiu(x,j) 6
F(x,i+1):=z for j:=Rang(x)+1 down to i kulcs(x,j+1)=kulcs(x,j) kulcs(x,i):=kulcs(y,t) Rang(x):=Rang(x)+1
X=
Y=
....xi, xi+1 ....
y1,....yt-1, yt, yt+1 .... y2t-1
X=
....xi,,yt,,xi+1 ....
yt+1 .... y2t-1
y1,....yt-1
B fa szétvágása
6. ábra. Beszúrás B fába Bfabeszur(F,k) If Rang(F)=2t-1 Then r:=F Letesit(s: Bfapont) Level(s):=false Rang(s):=0 Fiu(s,1):=F F:=s Bfavag(F,1,r) NemTelitettBeszur(F,k) Else NemTelitettBeszur(F,k) NemTelitettBeszur(F,k) i:=Rang(F) if level(F) 7
then while i>=1 and k=1 and kkulcs(F,i) then i:=i+1 NemTelitettBeszur(Fiu(F,i),k) Törlés B fából Els˝oként megkeressük a törlend˝o csúcsot, ha a törlend˝o kulcs nem levélben van, akkor megkeressük a rákövetkez˝o elemet (annak a részfának a maximális (legjobbrább es˝o) eleme, amelynek a gyökere a keresett kulcs jobboldali fia). Ez az elem már levélben helyezkedik el, azt töröljük a fából az adatokat törlés el˝ott kicseréljük. Probléma akkor áll fennt ha a levél, amelyben a tényleges törlést végrehajtjuk minimális. Ezt a lehet˝oséget úgy zárjuk ki, hogy a ténylegesen kitörlend˝o elem keresése során, mindig megszüntetjük a minimális pontokat a fában. Minimális pontok megszüntetése Ha a pontnak vagy a balszomszédja vagy a jobbszomszédja nem minimális, akkor a megfelel˝o nem minimális szomszédból átadunk egy elemet. Ezt úgy tehetjük meg, hogy az átadó pont legszéls˝o eleme felmegy az apába, és az apa megfelel˝o eleme, lemegy a minimális pontba, amelyben meg akarjuk szüntetni a minimalitást. Ha a pontnak egy minimális szomszédja van, vagy mindkét szomszédja minimális, akkor a pontot és egy minimális szomszédját összevonjuk. A két pontból, továbbá az apában a két pontot elválasztó kulcsból egy új pont lesz, aminek a rangja 2t − 1. Az összevonás a Bfavag m˝uvelet inverze. Mind a beszúrás mind pedig a törlés futási ideje legrosszabb esetben a B fa magasságával arányos. Tehát a futási id˝o O(logt (n)). A fenti algoritmusok mind a beszúrás mind pedig a törlés esetén az ugynevezett pesszimista stratégiát követték, ami azt jelenti, hogy a beszúrás helyének, illetve a ténylegesen törlend˝o elemnek a keresése során gondoskodnak róla, hogy ne legyen telített illetve minimális pont. Létezik optimista megvalósítása is ugyanezeknek az ötleteknek, amely során els˝oként megkeressük a beszúrás helyét illetve a törlend˝o elemet és szükség esetén állítjuk helyre a rangokra vonatkozó korlátokat, felfele menve a beszúró illetve törl˝oúton. Demonstrációs programok http://people.ksp.sk/~kuko/bak/index.html http://slady.net/java/bt/view.php Kiskérdések • AVL fa definíció • egyszeres, kétszeres forgatás • az AVL fa tulajdonság helyreállításainak esetei • B fa definíciója 8
X= x1, x2, ... xk
Z=z1, ... , zt-1
Y=y1, ... , yj
X= yj, x2, ... xk
Y=y1, ... , yj-1
Z=x1,z1, ... , zt-1
7. ábra.
• B fa szétvágása • Beszúrás B fába • Törlés B fából
9
