6. előadás
AVL fák Az első kiegyensúlyozott fa algoritmus Kitalálói: Adelson-Velskii és Landis (1962) Tulajdonságok Bináris rendezőfa A bal és jobb részfák magassága legfeljebb 1-gyel különbözik A részfák is AVL fák AVL fa
AVL fa
AVL fák Jelölje m(f) az f bináris fa magasságát
(szintjeinek számát), ha x az f fa egy csúcsa: ekkor m(x) jelöli az x-gyökerű részfa magasságát. Definíció (AVL-tulajdonság): Egy bináris keresőfa AVL-fa, ha minden x csúcsára teljesül, hogy |m(bal[x]) – m(jobb[x]) |
1
AVL fák Mekkora a k - szintű AVL-fa minimális csúcsszáma?
S0 = 1 S1 = 2
S2 = 4
S3= 7
AVL fák Mekkora a k - szintű AVL-fa minimális csúcsszáma?
S4=12
AVL fák Összefüggés az AVL-fa pontszáma és magassága
között: n adattal felépíthető fa minimális magassága?
majdnem teljes bináris fa n adattal felépíthető fa maximális magassága? ugyanez a kérdés: az adott h szintszámú AVL-fák közül mennyi a minimális pontszám? A h szintszámú minimális csúcsszámú AVL-fa gyökerének egyik részfája h – 1, a másik h – 2 szintű; az eredeti fa minimalitása miatt pedig mindkét részfa minimális csúcsszámú.
h h-2 h-1
rekurzió: Sh = 1 + Sh-1 + Sh-2
AVL fák - magasság Tétel: Egy h magasságú AVL fának legalább Fh+3- 1 csúcsa
van Bizonyítás:
Legyen Sh a legkisebb h magasságú AVL fa mérete (ezt
jelöljük majd n-nel) Nyilván, S0 = 1 és S1 = 2 valamint Sh = Sh-1 + Sh-2 + 1 Indukcióval .. Sh = Fh+3-1 („3-mal eltolt Fibonacci”)
(Fh+2-1+Fh+1-1 +1=Fh+3-1)
AVL fák - magasság A Fibonacci számokra igaz a
Binet-formula: n
1
Fn
1
5
n
1
2
5
5 2
h 3
Fh
3
1
1 5
1
5 2
h 3
1
5 2
3
1
1 1 5 5 2
h
1
5 2
2
h
1 1 3 5 35 5 5 1 5 8 2 5 h
1
2 1 5 2 5
2 1 log 2
2
2
1
5 2
log 2 Sh n Sh
5 1
5 2
5
h
5
h
h
2
h
2
1
5 2
/ log 2
h 1,44 log 2 n h nem mehet az optimális fölé 44%- kal többel
Újrakiegyensúlyozás beszúrásnál A beszúrás elrontja az AVL tulajdonságot
1
4 eset:
1 és 4 tükörképek 2 és 3 tükörképek
2
3
4
Újrakiegyensúlyozás beszúrásnál Egy új attribútumot vezetünk be:
kiegyensúlyozási tényező -1 : bal részfa magasabb 1-gyel 0 : egyforma magasak a részfák +1: jobb részfa magasabb 1-gyel
A (++,+) szabály: x + y
x
0
++
y
h h
h
+
h h
h+1
beszúrás < x<
< y<
Az új levél a részfába került. A beszúrás előtt a fa magassága h+2 volt.
A (++,+) szabály: x ++ y
Az új levél a részfába került. A beszúrás előtt a fa magassága h+2 volt. Forgatás:
y
+ x
h h
Ennek a tükörképe a (--,-) szabály! (1. eset) < x< < y<
h+1
h
h
h+1
A forgatás után ismét h+2 a magasság. Ezért feljebb, a befoglaló fában (ha van), változatlanul érvényes az AVL tulajdonság, nem kell feljebb menni ellenőrizni.
++
Példa
15 +
10
20 18
3
25 -
22
17 21
30 ezt szúrtuk be
Példa 20
15
25
10
3
18
17
22 21
30
Az új levél a z alatti vagy részfába került. A beszúrás előtt a z csúcs alatti fák egyformák:
A (++,-) szabály: x +
x ++
h
y z
0
h
y
0
-
z
h
h h-1
h-1
h-1 h
< x<
h h-1
A beszúrás után az egyik részfa magassága h lett, a másik maradt h-1.
A (++,-) szabály: ++
x h
Dupla forgatás kell: először jobbra:
x
y
++
-
z
z h
h-1 h
< x<
h h-1
+ y
h-1 v. h
h v. h-1
h
0 v.+
A (++,-) szabály:
Dupla forgatás kell: azután balra:
z
x z
x y
y
A (++,-) szabály: Végeredmény z
x
Továbbra is igaz: < x< < z < < y <
A beszúrás előtt az x gyökerű fa magassága h+2 volt. A forgatás után ismét h+2 a magasság. Ezért feljebb, a befoglaló fában (ha van), változatlanul érvényes az AVL tulajdonság, nem kell feljebb menni ellenőrizni.
y
Ennek a tükörképe a (--,+) szabály!
Újrakiegyensúlyozás beszúrásnál Összefoglalva:
A beszúrás után az új levéltől felfelé haladva a gyökér
felé újra számoljuk a csúcsok címkéit ezen az útvonalon. Ha egy x csúcs címkéje ++ vagy –-lesz, akkor az x gyökerű (rész)fa (esetleg dupla) forgatásával helyreállítható az AVL tulajdonság. Műveletigény: O(1)
Újrakiegyensúlyozás beszúrásnál Tétel. Legyen S egy n csúcsból álló AVL-fa.
BESZÚR(s; S) után legfeljebb egy (esetleg dupla) forgatással helyreállítható az AVL-tulajdonság. A beszúrás költsége ezzel együtt is O(log n). Bizonyítás: az előzőekből következik
AVL fák – újrakiegyensúlyozás törlésnél A (++,+) és (++,0) szabály x
+
A törlés az részfában történt. Ennek a magassága h+1 volt és h lett. Az x gyökerű fa magassága h+3 volt.
x
+ y v. 0 h+1
h v. h+1
++ + y v. 0
h+1
h h v. h+1
< x<
< y<
h+1
A (++,+) (++,0) szabály
A törlés az részfában történt. Ennek a magassága h+1 volt és h lett. Az x gyökerű fa magassága h+3 volt. Forgatás:
x ++ y
y
+ x
h h v. h+1
< x<
0 v. -
< y<
h+1
h
h v. h+1
h+1
A forgatás után h+2 a magasság. Ezért feljebb, a befoglaló fában (ha van), nem biztos, hogy változatlanul érvényes az AVL tulajdonság, feljebb kell menni ellenőrizni, amíg a gyökérig nem jutunk.
A (++,+) szabály
z
+
Ha az eredeti
fában például:
x
+
y
+
h+1 h
<x<
h+1
h+4
A (++,+) szabály z
h+2
y
Akkor az eredmény fa:
++
0
x
h h
<x<
h+1
h+4 feljebb kell menni ellenőrizni, és szükség szerint helyreállítani, amíg a gyökérig nem jutunk.
A törlés az részfában történik. Ennek a magassága h+1 volt és h lett. Az x gyökerű fa magassága h+3.
A (++,-) szabály +
x
x ++
h+1
y
h
y
-
z z
h
0 h
h-1 v. h
< x<
h v. h-1
h-1 v. h
h v. h-1
dupla forgatás
A (++,-) szabály:
Dupla forgatás kell: először jobbra:
++
x h
x
y
++
-
z
h
z h
h-1 v. h
< x<
h v. h-1
y
h-1 v. h
h v. h-1
h
A (++,-) szabály:
Dupla forgatás kell: azután balra:
z
x z
x
y
y
h
h-1 v. h
h v. h-1
h
A (++,-) szabály: Végeredmény
A forgatás után h+2 a magasság. Ezért feljebb, a befoglaló fában (ha van), nem biztos, hogy változatlanul érvényes az AVL tulajdonság, feljebb kell menni ellenőrizni, amíg a gyökérig nem jutunk.
z
x
Továbbra is igaz: < x< < z < < y <
y
Újrakiegyensúlyozás törlésnél Összefoglalva: Mivel az x gyökerű fa magassága csökkent a forgatással,
ezért feljebb is, ha van befoglaló fa, elromolhatott az AVL tulajdonság. A törlés után a törölt elem szülőjétől kezdve felfelé haladva a gyökér felé újra számoljuk a csúcsok címkéit ezen az útvonalon. Ha egy x csúcs címkéje ++ vagy –- lesz, akkor az x gyökerű (rész)fa (esetleg dupla) forgatásával helyreállítjuk annak AVL tulajdonságát. Ha x nem a gyökér, akkor feljebb kell lépni és folytatni kell az ellenőrzést. Szélsőséges esetben az adott útvonal minden pontjában forgatni kell!
Újrakiegyensúlyozás törlésnél Tétel: Az n pontú AVL-fából való törlés után legfeljebb
1,44 log2 n (sima vagy dupla) forgatás helyreállítja az AVL-tulajdonságot. Bizonyítás: az előzőekből következik.
Összefoglalás AVL fák Az első dinamikusan kiegyensúlyozott fák A magasság az optimális 44%-án belül Újrakiegyensúlyozás forgatásokkal O(log n)
Nézzük meg az animációt!
http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html
