Algoritmusok és adatszerkezetek II. Horváth Gyula Szegedi Tudományegyetem Természettudományi és Informatikai Kar
[email protected]
3.
˝ Kiegyensúlyozott keresofák
A T tulajdonság magasság-egyensúlyozó tulajdonság, ha:
1. (∃c ∈ R)(∀F)(T (F) ⇒ h(F) ≤ c · lg(|F|) ˝ 2. T fenntartható Bovítés és Törlés során: ˝ Bovit, Torol után O(h(F)) idoben helyreállítható. Következmény: |F| = n esetén Keres, Bovit, Torol : Tlr (n) = O(lg n)
3.1.
AVL-fák (Adelson-Velskij, Landis, 1962)
Definíció. A P ∈ F pont (magasság-)egyensúlya: Egy(P) = h(Job(P)) − h(Bal(P)) Definíció. Az F binfa AVL-fa, ha (∀P ∈ F)(−1 ≤ Egy(P) ≤ 1) 3.1. tétel. Ha F AVL-fa, akkor h(F) ≤ 1.44 · lg(n + 1); |F| = n Bizonyítás. Legyen Nm az m magasságú, legkevesebb pontot tartalmazó AVL-fa pontjainak száma, azaz, Nm ≤ |F|, ha F AVL-fa és h(F) = m •N0 = 0 , N1 = 1 , N2 = 2 •Nm = 1 + Nm−2 + Nm−1 , ha m > 1
⇒ Nm + 1 = (Nm−2 + 1) + (Nm−1 + 1) Jelölje Bi := Ni + 1 értéket. Tehát B0 := 1, B1 := 2, · · · , Bm = Bm−2 + Bm−1 (m > 1) ? Φm ≤ Bm alsó korlátot keresünk. Tfh. 1 = Φ0 ≤ B0 , Φ1 ≤ B1 és ha 2, · · · , m − 1-ig áll az ≤ Bm = Bm−2 + Bm−1 ≥ Φm−2 + Φm−1 = Φm−2 (1 + Φ) Ha (1 + Φ) ≥ Φ2 , akkor Bm ≥ Φm−2 (1 + Φ) ≥ Φm−2 Φ2 = Φm De a Φ2√= (1 + Φ) azaz (Φ2 − Φ − 1 = 0) egyenlet megoldása: Φ = 1+2 5 ≈ 1.618 Φm ≤ Bm = Nm + 1 ≤ n + 1 m · lg Φ ≤ lg(n + 1) h(F) = m ≤ lg1Φ lg(n + 1) = 1.44 · lg(n + 1)
A Bovit és Torol muveletek ˝ megvalósítása: ˝ 1. közönséges bovítés/törlés; ˝ 2. AVL tulajdonság helyreállítása a keresoúton visszafelé haladva lokális forgatásokkal. ˝ Pm -ig vezeto˝ út az F bináris fában és X adatelem; Legyen U = hP0 , P1 , · · · , Pm i a gyökértol F = P0 ∧ Pi+1 = Bal(Pi ) ∨ Pi+1 = Jobb(Pi ). ˝ Definíció. Az U pontsorozat X-keresoút, ha
1. X < Adat(Pi ) ⇒ Pi+1 = Bal(Pi ) és
X ≥ Adat(Pi ) ⇒ Pi+1 = Jobb(Pi )(i < m) 2. Vagy Adat(Pm ) = X és
(∀i < m)(Adat(Pi ) 6= X) vagy (∀i ≤ m)(Adat(Pi ) 6= X) és X < Adat(Pm ) ⇒ Bal(Pm ) = ⊥ és X ≥ Adat(Pm ) ⇒ Jobb(Pm ) = ⊥ ˝ oút, ˝ Definíció. U X-bovít ha
1. X < Adat(Pi ) ⇒ Pi+1 = Bal(Pi ) és
X ≥ Adat(Pi ) ⇒ Pi+1 = Jobb(Pi )(i < m) 2. X < Adat(Pm ) ⇒ Bal(Pm ) = ⊥ és
X ≥ Adat(Pm ) ⇒ Jobb(Pm ) = ⊥
˝ Definíció. U X-törloút, ha
1. (∃0 ≤ t ≤ m)(Adat(Pt ) = X) és hP0 , · · · , Pt i ˝ X-keresoút 2. t = m és Bal(Pt ) = ⊥ ∨ Jobb(Pt ) = ⊥ vagy Bal(Pt ) 6= ⊥ ∧ Jobb(Pt ) 6= ⊥ és Pt+1 = Jobb(Pt ),Pi+1 = Bal(Pi )(t < i < m)
˝ oút ˝ (X-törloút) ˝ Tfh. P az X-bovít egy pontja és ˝ ˝ Bovítésnél: X ≥ Adat(P) és h(Jobb(P)) nott Törlésnél: X < Adat(P)és h(Bal(P)) csökkent . Bovit(P, x) a
P
a
Torol(Q, x)
P
P
α
β
α
β
˝ 1. ábra. Fa magasságának változása bovítés és törlés hatására
˝ Muvelet ˝ elott
Muvelet ˝ után Egy(P) = −1 Egy(P) = 0, új h(P) = h(P) Egy(P) = 0 Egy(P) = 1, új h(P) = h(P) + 1 Egy(P) = +1 Egy(P) = 2, forgatni kell! új h(P) =?
BForgat(P) a
P
b
JForgat(Q)
b
Q
a
Q
P
α
γ
β
γ
α
β
˝ a keresofa ˝ tulajdonságot. 2. ábra. Az egyszeru˝ balra/jobbra forgatás megorzi
˝ a keresofa ˝ tulajdonságot. 3.2. Állítás. Az egyszeru˝ balra és jobbra forgatás megorzi ˝ ha az inoreder bejárása rendezett sorozatot Bizonyítás. Az F fa akkor és csak akkor keresofa, ad. Az Inorder(F)=
jelöléssel:
< F >=< α >, a, < β >, b, < γ > < F 0 >=< α >, a, < β >, b, < γ >
3.2.
A forgatás utáni egyensúly és magasság kiszámítása
˝ ˝ oút ˝ egy pontja, és a bovítés ˝ Tfh. az F fát bovítettük az x adattal. Legyen P az x-bovít P-nek a Q-gyökeru˝ jobb-részfájába történt. Továbbá, Q magassága növekedett, és így Egy(P) = 2 lett. ˝ Ha a bovítés és AVL-egyensúly helyreállítás után Egy(Q) ≥ 0, akkor egyetlen balra forgatás helyreállítja az egyensúlyt. Hogyan változik a részfa magassága?
a P 2 b Q h+3
0 1
α
h+2
h β
γ
h+1 h
h+1 h+1
b Q −1 0 a P h+3 h+2
1 0
h+2 h+1
γ
α
β
h
h+1 h
h+1 h+1
3. ábra. 1.a eset: AVL egyensúly helyreállítása egyszeru˝ balra forgatással. Ha Egy(Q) = 1 ⇒ a magasság csökken. Ha Egy(Q) = 0 ⇒ nem csökken; csak törlés esetén lehet.
b P −2 a
Q h+3
−1 0
h+2
γ h
α
β
h+1 h+1
h h+1
a Q 0 1 b P 0 −1
α
h+1 h+2
h+1 h+1
h+2 h+3 β h h+1
γ h
4. ábra. 2.a eset: AVL egyensúly helyreállítása egyszeru˝ jobbra forgatással. Ha Egy(Q) = −1 ⇒ a magasság csökken. Ha Egy(Q) = 0 ⇒ nem csökken; csak törlés esetén lehet.
˝ balra forgatással Helyreállítás kettos Feltétel: Egy(P) = 2, Egy(Q) = −1
a P 2
c
Q h+3
−1 α
h+2
b R −1 0 1
h
δ h
β
γ
h h h−1
h−1 h h
b
R
0 c
a P 0 0 −1
Q
+1 0 0
h+2 h+1
α
β
γ
δ
h
h h h−1
h−1 h h
h
˝ balra forgatás. 5. ábra. 1.b eset: AVL egyensúly helyreállítása kettos
U jEgy(P) = −Max(Egy(R), 0) U jEgy(Q) = −Min(Egy(R), 0) U jEgy(R) = 0 Egy(R) U jEgy(P) U jEgy(Q) -1 0 1
0 0 -1
1 0 0
˝ jobbra forgatással Helyreállítás kettos Feltétel: Egy(P) = −2, Egy(Q) = +1
P
c −2 a Q +1 h+2 α
h+3
δ
b R −1 0 1
h
h β
γ
h h h−1
h−1 h h
b
R
0 c P +1 0 0
a Q 0 0 −1
h+1
h+2 h+1
α
β
γ
δ
h
h h h−1
h−1 h h
h
˝ jobbra forgatás. 6. ábra. 1.b eset: AVL egyensúly helyreállítása kettos
U jEgy(P) = −Min(Egy(R), 0) U jEgy(Q) = −Max(Egy(R), 0) U jEgy(R) = 0 Egy(R) U jEgy(P) U jEgy(Q) -1 0 1
1 0 0
0 0 -1
Megvalósítás
public class AVLFaPont<E extends Comparable<E>> extends BinKerFaPont<E>{ byte egy; public AVLFaPont(E x, AVLFaPont<E> b, AVLFaPont<E> j ){ super(x,b,j); } public AVLFaPont(){ super(); } } public class BinKerFaAVL<E extends public BinKerFaAVL(){ super(); }
Comparable<E>>
extends BinKerFa<E>{
public boolean Bovit(E x, boolean tobb){ AVLFaPont<E> p =(AVLFaPont<E>) gyoker; AVLFaPont<E> pp; int ken; if (p == null) { gyoker = new AVLFaPont<E>(x,null,null); return true; } pp=p; while (p != null) { ken = x.compareTo(p.elem); pp=p; if (ken < 0) p=(AVLFaPont<E>)p.bal; else if (ken > 0) p=(AVLFaPont<E>)p.jobb; else {// = if (!tobb) return false; else{ p =(AVLFaPont<E>)p.jobb; } } }
ken = x.compareTo(pp.elem); if (ken<0){ pp.bal = new AVLFaPont<E>(x,null,null); pp.bal.apa=pp; Helyreallit(pp, false, 1); }else{ pp.jobb = new AVLFaPont<E>(x,null,null); pp.jobb.apa=pp; Helyreallit(pp, true, 1); } return true; }//Bovit
public boolean Torol(E x){ AVLFaPont<E> p =(AVLFaPont<E>) gyoker; AVLFaPont<E> q; AVLFaPont<E> pp; int ken; while (p!=null && (ken = x.compareTo(p.elem))!=0){ if (ken<0) p=(AVLFaPont<E>)p.bal; else p=(AVLFaPont<E>)p.jobb; } if (p==null) return false; if (p.bal != null && p.jobb != null){ q=(AVLFaPont<E>)p.jobb; while (q.bal!=null){ q=(AVLFaPont<E>)q.bal; } p.elem=q.elem; //helyettesítés a követ˝ ovel p=q; }
if (p.bal==null) q=(AVLFaPont<E>)p.jobb; else q=(AVLFaPont<E>)p.bal; pp=(AVLFaPont<E>)p.apa; if (q!=null) q.apa=pp; if (p==gyoker){ gyoker=q; }else{ if (p==pp.bal){ pp.bal=q; Helyreallit(pp, false, -1); }else{ pp.jobb=q; Helyreallit(pp, true, -1); } } return true; }
// Az új egyensúly értékek táblázatai egyszer˝ u balra forgatáskor; // Egy(Q) függvényében: private final byte[] BUjP={1,0}; private final byte[] BUjQ={-1,0}; // Az új egyensúly értékek táblázatai egyszer˝ u jobbra forgatáskor; // Egy(Q) függvényében: private final byte[] JUjP={0,-1}; private final byte[] JUjQ={0,1}; // Az új egyensúly értékek táblázatai egyszer˝ u kett˝ os balra forgatáskor; // Egy(R) függvényében: private final byte[] KUjP={0,0,-1}; private final byte[] KUjQ={1,0,0}; private void Helyreallit(AVLFaPont<E> p, boolean jobbra, int nott){ //jobbra=true/false: b˝ ovítés/törlés a p jobb-részfájában //nott=1: b˝ ovítés, nott=-1: törlés AVLFaPont<E> orszem=new AVLFaPont<E>(); orszem.bal=gyoker; gyoker.apa=orszem; int pegy; AVLFaPont<E> pp, q, r;
while (p!=orszem){ pegy=p.egy; if (jobbra) p.egy+=nott; else p.egy-=nott; if (p.egy==0 && nott>0 || pegy==0 && nott<0) break; pp=(AVLFaPont<E>)p.apa; jobbra=p==pp.jobb; if (p.egy==2){ q=(AVLFaPont<E>)p.jobb; if (q.egy>=0){ //egyszeres balra forgatás p.egy=BUjP[q.egy]; // P Q q.egy=BUjQ[q.egy]; // / \ / \ p.jobb=q.bal; // a Q => P c q.bal=p; // / \ / \ q.apa=p.apa; p.apa=q; // b c a b if (p.jobb!=null) p.jobb.apa=p; if (p==pp.bal) pp.bal=q; else pp.jobb=q; p=q; if (q.egy==0 && nott>0 || q.egy==-1 && nott<0) break;
}else{ //kétszeres balra forgatás r=(AVLFaPont<E>)q.bal; // P R p.egy=KUjP[r.egy+1]; // / \ / \ q.egy=KUjQ[r.egy+1]; // a Q => P Q q.bal=r.jobb; // / \ / \ / \ p.jobb=r.bal; // R d a b c d r.bal=p; // / \ r.jobb=q; // b c r.apa=p.apa; p.apa=r; q.apa=r; if (p.jobb!=null) p.jobb.apa=p; if (q.bal!=null) q.bal.apa=q; r.egy=0; if (p==pp.bal) pp.bal=r; else pp.jobb=r; p=r; if (nott>0)break; }
}else if (p.egy==-2){ q=(AVLFaPont<E>)p.bal; if (q.egy<=0){ //egyszeres jobbra forgatás p.egy=JUjP[q.egy+1]; // P Q q.egy=JUjQ[q.egy+1]; // / \ / \ p.bal=q.jobb; // Q c => a P q.jobb=p; // / \ / \ q.apa=p.apa; p.apa=q; // a b b c if (p.bal!=null) p.bal.apa=p; if (p==pp.bal) pp.bal=q; else pp.jobb=q; p=q; if (q.egy==0 && nott>0 || q.egy==+1 && nott<0 ) break;
}else{//q.egy==1 //kétszeres jobbra forgatás r=(AVLFaPont<E>)q.jobb;// P R p.egy=KUjQ[r.egy+1]; // / \ / \ q.egy=KUjP[r.egy+1]; // Q d => Q P p.bal=r.jobb; // / \ / \ / \ q.jobb=r.bal; // a R a b c d r.bal=q; r.jobb=p; // / \ r.apa=p.apa; // b c q.apa=r; p.apa=r; if (q.jobb!=null) q.jobb.apa=q; if (p.bal!=null) p.bal.apa=p; r.egy=0; if (p==pp.bal) pp.bal=r; else pp.jobb=r; p=r; if (nott>0) break; } } p=pp; }//while gyoker=orszem.bal;
if (gyoker!=null) gyoker.apa=null; orszem=null; }
3.3.
A Sorozat adattípus megvalósítása AVL-fával
Értékhalmaz: Sorozat = {ha1 , . . . , an i : ai ∈ E} Muveletek: ˝
S : Sorozat, x : E, i : Integer
{Igaz}
Letesit(S)
{S = hi}
{S = S} Megszuntet(S) {Hamis} {S = S}
Uresit(S)
{S = hi}
{S = ha1 , . . . , an i} Elemszam(S) {Elemszam = ni} {S = ha1 , . . . , ai , ai+1 , . . . , an i ∧ 0 ≤ i ≤ n} Bovit(S, i, x) {S = ha1 , . . . , ai , x, ai+1 , . . . , an i} {S = ha1 , . . . , ai−1 , ai , ai+1 , . . . , an i ∧ 1 ≤ i ≤ n}
Torol(S, i)
{S = ha1 , . . . , ai−1 , ai+1 , . . . , an i}
{S = ha1 , . . . , ai , . . . , an i ∧ 1 ≤ i ≤ n} Kiolvas(S, i, x) {x = ai ∧ S = Pre(S)} {S = ha1 , . . . , ai , . . . , an i ∧ 1 ≤ i ≤ n} Modosit(S, i, x) {S = ha1 , . . . , x, . . . , an i}
Adatszerkezet választás. 1. Tároljuk az S = {ha1 , . . . , an i sorozatot egy F bináris fában úgy, hogy F inorder bejárása az S sorozatot adja. a5 a8
a2 a1
a4 a3
a6
a9 a7
7. ábra. Az S = ha1 , a2 , . . . , a9 i sorozat tárolása bináris fában inorder sorrendben.
2. Az F fa minden p pontjában tároljuk kiegészíto˝ információként p bal-részfájában lévo˝ pontok száma +1 értéket; rpoz(p) = 1 + |FBal(p) |. Tehát rpoz(p) a p pontra végrehajtott inorder bejárás során p sorszáma. A sorozat i-edik elemét tartalmazó pont keresése: a5 5 a8 3
a2 2 a1 1
a4 2 a3 1
a9 1
a6 1 a7 1
8. ábra. Kiegészíto˝ információ: rpoz(p) = 1 + |FBal(p) |.
private SFaPontAVL<E> Keres(int i){ SFaPontAVL<E> p=gyoker; int poz=i; while (poz!=p.rpoz) if (poz
˝ 3. A kiegészíto˝ információ fenntartása bovítés és törlés során. ˝ ˝ balra halad egy p ponttól, akkor p rpoz értékéhez egyet kell adni. Bovítés esetén ha a keresoút ˝ balra halad egy p ponttól, akkor p rpoz értékébol ˝ egyet le kell Törlés esetén, ha a keresoút vonni. Továbbá, ha AVL-fát használunk, akkor az AVL-egyensúlyt helyreállító forgatás után aktualizálni kell a kiegészíto˝ információt. P
a
BF ORGAT (P)
r1
Q b
r2
Q b
P a
r1 + r2
r1 γ
α β
γ
α
β
9. ábra. Az rpoz kiegészíto˝ információ változása egyszeres balra forgatás során.
JF ORGAT (P)
P
Q
Q a
b r1
r2
a r2
P b γ
α
r1 − r2
α β
β
γ
10. ábra. Az rpoz kiegészíto˝ információ változása egyszeres jobbra forgatás során.
P
a
R b
r1
Q c R
α
b
r2
P a
r1 + r3
r1
Q
c r2 − r3
r3 δ α
β
β
γ
δ
γ
˝ balra forgatás során. 11. ábra. Az rpoz kiegészíto˝ információ változása kettos
P
c
R b
r1
Q a
Q a r2 R
r2
P
c r1 − r2 − r3
δ
r3 b
α α β
r2 + r3
β
γ
δ
γ
˝ jobbra forgatás során. 12. ábra. Az rpoz kiegészíto˝ információ változása kettos
˝ minden pontonjában konstans AVL-fában a kiegészíto˝ információ fenntartható a keresoút számú muvelettel ˝ megvalósítható. Tehát ha a sorozat adattípust AVL-fával valósítjuk meg, akkor a K IOLVAS, M ODOSIT, B OVIT, TOROL muveletek ˝ futási ideje legrosszabb esetben is a fa magasságával arányos, tehát O(lg n).
import java.util.*; public class SorozatAVL<E> implements Sorozat<E>{ public static class SFaPontAVL<E> extends BinFaPont<E>{ byte egy; int rpoz; SFaPontAVL(E x, int bpontsz, SFaPontAVL<E> b, SFaPontAVL<E> j){ super(x,b,j); this.rpoz=bpontsz; } } int eszam; SFaPontAVL<E> gyoker; SorozatAVL(){ eszam=0; gyoker=null; }
private SFaPontAVL<E> Keres(int i){ SFaPontAVL<E> p=gyoker; int poz=i; while (poz!=p.rpoz) if (poz)p.bal; else{ poz=poz-p.rpoz; p=(SFaPontAVL<E>)p.jobb; } return p; }
public void Bovit(int i, E x){ if (i<0 || i>eszam) throw new NoSuchElementException(); SFaPontAVL<E> p=gyoker; SFaPontAVL<E> apa=gyoker; int poz=i; boolean balra=true; if (gyoker==null){ eszam=1; gyoker = new SFaPontAVL<E>(x, 1, null, null); return; }
while (p!=null){ apa=p; if (poz)p.bal; balra=true; }else{ poz=poz-p.rpoz; p=(SFaPontAVL<E>)p.jobb; balra=false; } } SFaPontAVL<E> ujp=new SFaPontAVL<E>(x, 1, null, null); ujp.apa=apa; if (balra){ apa.bal = ujp; Helyreallit(apa, false, 1); }else{ apa.jobb = ujp; Helyreallit(apa, true, 1); } ++eszam; }
public void Torol(int i){ if (i<1 || i>eszam) throw new NoSuchElementException(); int poz=i; SFaPontAVL< E> p = gyoker; SFaPontAVL< E> q; while (poz!=p.rpoz){ if (poz)p.bal; }else{ poz=poz-p.rpoz; p=(SFaPontAVL<E>)p.jobb; } }
if (p.bal != null && p.jobb != null){ q=(SFaPontAVL<E>)p.jobb; while (q.bal!=null){ --q.rpoz; q=(SFaPontAVL<E>)q.bal; } p.elem=q.elem; p=q; } if (p.bal==null) q=(SFaPontAVL<E>)p.jobb; else q=(SFaPontAVL<E>)p.bal; if (q!=null) q.apa=p.apa; if (p==gyoker){ gyoker=q; }else{ if (p==p.apa.bal) p.apa.bal=q; else p.apa.jobb=q; } --eszam; }
public E Kiolvas(int i){ if (i<1 || i>eszam) throw new NoSuchElementException(); SFaPontAVL<E> p=Keres(i); return p.elem; } public void Modosit(int i, E x){ if (i<1 || i>eszam) throw new NoSuchElementException(); SFaPontAVL<E> p=Keres(i); p.elem=x; }
private int Epit(SFaPontAVL<E> p, E a[], int bal, int jobb){ int balm=0; int jobbm=0; SFaPontAVL<E> balf, jobbf; int kozep=(bal+jobb) >>1; p.elem=a[kozep]; p.rpoz=kozep-bal+1; if (bal(); balm=Epit(balf, a, bal, kozep-1); p.bal=balf; balf.apa=p; } if (kozep<jobb){ jobbf=new SFaPontAVL<E>(); jobbm=Epit(jobbf, a, kozep+1, jobb); p.jobb=jobbf; jobbf.apa=p; } p.egy=(byte)(jobbm-balm); return 1+(balm<jobbm ? jobbm : balm); }
SorozatAVL(E a[]){ if (a.length==0){ this.gyoker=null; this.eszam=0; return; } this.gyoker=new SFaPontAVL<E>(); this.eszam=a.length; Epit(gyoker, a, 0, a.length-1); } private void tombbe(E[] a, int bal,int jobb, SFaPontAVL<E> p){ int k=bal+p.rpoz-1; a[k]=p.elem; if (bal)p.bal); if (k<jobb) tombbe(a, k+1, jobb, (SFaPontAVL<E>)p.jobb); } public E[] Tombosit(){ int n=eszam; E[] a=(E[]) new Object[n]; tombbe(a, 0, n-1, gyoker); return a; } }
