N3

˝ Kiegyensúlyozott keresofák

3.

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 t 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(Pm ) 6= X) vagy (∀i ≤ m)(Adat(Pi ) 6= X) és X < Adat(Pm ) ⇒ Bal(Pi ) = ⊥ és X ≥ Adat(Pm ) ⇒ Jobb(Pi ) = ⊥ ˝ 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(Pi ) = ⊥ és

X ≥ Adat(Pm ) ⇒ Jobb(Pi ) = ⊥

1



˝ 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

P

a

Torol(Q, x)

P

α

α

β

β

˝ 1. ábra. Fa magasságának változása bovítés és törlés hatására

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

˝ 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) =? ˝ 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 ad. Bizonyítás. Az F fa akkor és csak akkor keresofa, 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?

2

a P 2 b Q h+3

0 1

α h

h+2

β

γ

h+1 h

h+1 h+1

b Q −1 0 a P 1 0

h+2 h+1

h+3 h+2

γ h+1 h+1

α

β

h

h+1 h

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

−1 0

h+2

h+3

γ 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.

3

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

˝ balra forgatással Helyreállítás kettos Feltétel: Egy(P) = 2, Egy(Q) = −1

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

4

P

c −2 a Q +1 h+2

δ

b R −1 0 1

α

h+3

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

˝ jobbra forgatással Helyreállítás kettos Feltétel: Egy(P) = −2, Egy(Q) = +1

U jEgy(P) = −Min(Egy(R), 0) U jEgy(Q) = −Max(Egy(R), 0) U jEgy(R) = 0 Egy(R) -1 0 1 Megvalósítás

U jEgy(P)

U jEgy(Q)

1 0 0

0 0 -1

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>{

5

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){ 6

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; 7

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 8

r=(AVLFaPont<E>)q.jobb;// P p.egy=KUjQ[r.egy+1]; // / \ q.egy=KUjP[r.egy+1]; // Q d p.bal=r.jobb; // / \ q.jobb=r.bal; // a R 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;

R / =>

Q / \ a

} } p=pp; }//while gyoker=orszem.bal; if (gyoker!=null) gyoker.apa=null; orszem=null; }

9

\ P / \ b c d

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}

{S = hi}

Letesit(S)

{S = S} Megszuntet(S) {Hamis} {S = S}

{S = hi}

Uresit(S)

{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}

Torol(S, i)

{S = ha1 , . . . , ai−1 , ai+1 , . . . , an i}

{S = ha1 , . . . , ai−1 , ai , ai+1 , . . . , an i ∧ 1 ≤ i ≤ n}

{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.

2. Az F fa

a5 a8

a2 a1

a6

a4 a3

a9 a7

7. ábra. Az S = ha1 , a2 , . . . , a9 i sorozat tárolása bináris fában inorder sorrendben.

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

a9 1

a6 1

a4 2

a7 1

a3 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
p=p.jobb; } return p; } ˝ 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. Törlés esetén, ha a keresoút ˝ balra Bovítés esetén ha a keresoút ˝ egyet le kell vonni. halad egy p ponttól, akkor p rpoz értékébol 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

Q b

r2

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

Q

c r2 − r3

r3 δ

β

r1 + r3

α

β

γ

δ

γ

˝ balra forgatás során. 11. ábra. Az rpoz kiegészíto˝ információ változása kettos

˝ minden pontonjában konstans számú muvelettel AVL-fában a kiegészíto˝ információ fenntartható a keresoút ˝ 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.*; 11

P

R b

r1

c

Q a

Q a r2 R

r2 + r3

r2

P

c r1 − r2 − r3

δ

r3 b

α

α β

β

γ

δ

γ

˝ jobbra forgatás során. 12. ábra. Az rpoz kiegészíto˝ információ változása kettos

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; 12

} 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) 13

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; 14

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; } }

15