N4

4.

Piros-fekete fák

˝ A piros-fekete fa olyan bináris keresofa, amelynek minden pont egy extra bit információt tartalmaz, ez a pont színe, amelynek ˝ értékei: PIROS vagy FEKETE. A pontok színezésének korlátozásával biztosítható, hogy piros-fekete fában bármely, a gyökértol ˝ levélig vezeto˝ út hossza nem lehet nagyobb, mint a legrövidebb ilyen út hosszának kétszerese. Tehát az ilyen fák megközelítoleg kiegyensúlyozottak. ˝ mezoket. ˝ A fa minden pontja tartalmazza a szín, kulcs, bal, jobb és apa (szülo) Ha egy ponthoz tartozó fiú vagy apa nem létezik, ˝ külso˝ (levél) akkor a megfelelo˝ mezo˝ a NIL értéket tartalmazza. Úgy tekintjük, hogy az ilyen NIL mutató értékek a bináris keresofa pontjaira mutatnak, míg a fa kulcsot tartalmazó pontjai a belso˝ pontok. ˝ piros-fekete fa, ha teljesül rá a következo˝ piros-fekete tulajdonság: Egy bináris keresofa 1. Minden pont színe vagy PIROS vagy FEKETE. 2. A gyökérpont színe FEKETE. 3. Minden levél (NIL) színe FEKETE. 4. Minden piros pontnak mindkét fia fekete. 5. Bármely pontból bármely levélig vezeto˝ úton ugyanannyi fekete pont van. ˝ Piros-fekete fa algoritmusokban a peremfeltételek kényelmes kezelése végett egyetlen orszem pontot használunk a NIL érték ábrázolására. ˝ ˝ Az orszem használata lehetové teszi, hogy bármely x pont NIL fiát olyan közönséges pontnak tekintsük, amelynek apja x. ˝ ˝ Bevezethetnénk minden NIL számára egyedi orszemet, azonban ez tárpazarló lenne. Ehelyett egyetlen F.null orszemet haszná˝ ábrázolására. A apa, kulcs, bal, jobb mezok ˝ értéke lényegtelen, de lunk az összes NIL érték - az összes levél és a gyökér szüloje eljárásokban kényelmi okok miatt értéküket beállíthatjuk. Egy x pont fekete-magasságának nevezzük az x pontból induló, levélig vezeto˝ úton található, x-et nem tartalmazó fekete pontok számát, és f m(x)-szel jelöljük ezt az értéket. Az 5. tulajdonság miatt a fekete-magasság jól definiált, mivel minden ilyen út azonos számú fekete pontot tartalmaz. Egy piros-fekete fa fekete-magasságát a fa gyökérpontjának fekete-magasságaként definiáljuk. A következo˝ lemma megmutatja, hogy miért jók a piros-fekete fák. 4.1. lemma. Bármely n belso˝ pontot tartalmazó piros-fekete fa magassága legfeljebb 2 lg(n + 1). ˝ Bizonyítás. Eloször megmutatjuk, hogy a fa minden x gyökeru˝ részfája legalább 2 f m(x) − 1 belso˝ pontot tartalmaz. Az állítást x magassága szerinti teljes indukcióval bizonyítjuk. Ha x magassága 0, akkor x levél (nil[T ]), tehát az x gyökeru˝ részfának valóban 2 f m(x) − 1 = 20 − 1 = 0 belso˝ pontja van. Tegyük fel, hogy x magassága pozitív, és két fia van. Mindkét fiú fekete-magassága vagy ˝ f m(x), vagy f m(x) − 1 attól függoen, hogy a színe piros vagy fekete. Mivel x fiainak magassága kisebb, mint x magassága, így az indukciós feltevést alkalmazva azt kapjuk, hogy mindkét részfa legalább 2 f m(x)−1 − 1 belso˝ pontot tartalmaz. Tehát az x gyökeru˝ részfa belso˝ pontjainak száma legalább (2 f m(x)−1 − 1) + (2 f m(x)−1 − 1) + 1 = 2 f m(x) − 1, ami az állítás bizonyítását jelenti. ˝ egy levélig A lemma bizonyításához legyen x magassága h. A 4. tulajdonság szerint minden olyan út, amelyik a gyökértol halad, legalább feleannyi fekete pontot tartalmaz, mint ezen út pontjainak száma, nem számítva a gyökeret. Tehát a gyökér fekete-magassága legalább h/2, így

n ≥ 2h/2 − 1. ˝ Az egyenlotlenség mindkét oldalához 1-et adva, majd logaritmusát véve kapjuk, hogy lg(n + 1) ≥ h/2, vagy h ≤ 2 lg(n + 1).



˝ O ˝ muveletek Ezen lemma közvetlen következménye, hogy a K ERES, M INIMUM, M AXIMUM, KÖVETKEZ O˝ , E L OZ ˝ mindegyike megva˝ lósítható O(lg n) idoben piros-fekete fákkal, mivel a futási ido˝ O(h), ha a fa magassága h, és egy n pontú piros-fekete fa magassága ˝ ˝ O(lg n) Bár a bináris keresofákra adott B OVÍT és TÖRÖL algoritmusok futási ideje szintén O(lg n) ha az input piros-fekete fa, azon˝ ban közvetlenül nem támogatják a B OVÍT és a TÖRÖL muveleteket, ˝ mert az algoritmus által módosított fa nem feltétlenül lesz ismét ˝ piros-fekete fa. Látni fogjuk majd, hogy ezek a muveletek ˝ is megvalósíthatók O(lg n) idoben piros-fekete fákkal, mert a piros-fekete ˝ tulajdonság fenntartható bovítés és törlés során.

4.1.

˝ Bovítés

˝ ˝ ˝ Piros-fekete fa bovítése egy új ponttal elvégezheto˝ O(lg n) idoben, ha a fa n pontot tartalmaz. A közönséges bináris keresofa ˝ ˝ lenne, majd B OVIT eljárás kissé módosított változatával bovítjük a T fát az U ponttal, mintha a fa közönséges bináris keresofa az U pont színét pirosra állítjuk. A piros-fekete tulajdonság biztosítására meghívjuk a B OVIT J AVÍT segéd eljárást, amely pontok átszínezését és forgatásokat végez.

1

3 3 2 2 1 1

7

3

NIL

1 NIL

2 1

12

NIL

41

14

10 1

NIL

16

15

NIL

26

17

1

NIL

21

19

NIL

NIL

2 1

1

20

NIL

23

NIL

1

NIL

1

28

NIL

NIL

NIL

1

1

38

35

1

NIL

NIL

2

30

NIL

47

NIL

NIL

39

NIL

NIL

(a)

26 17

41

14

21

10 7

16 12

19

15

30 23

47

28

38

20

35

39

3

nil[T] (b) 26 17

41

14

21

10 7

16 12

15

19

30 23

47

28

20

38 35

3

39

(c)

1. ábra. A sötét pontok az ábrán fekete pontok, a világosan satírozottak pedig a piros pontok. Minden piros pont mindkét fia fekete, és minden pontból induló, levélig vezeto˝ úton ugyanannyi fekete pont található. (a) Minden levél (NIL) színe fekete. Minden nem levél pont mellé odaírtuk a pont fekete-magasságát, a NIL pontok fekete-magassága 0. (b) Ugyanaz a piros-fekete fa, de minden ˝ NIL pont a nil orszemmel helyettesítettünk, amely mindig fekete színu, ˝ és a fekete-magasságát nem jelöltük. A gyökérpont apja ˝ szintén az orszem. (c) Ugyanaz a piros-fekete fa, de a leveleket és a gyökér apját teljesen elhagytuk.

2

+ 26 3

* 17 3

+ 14 2

* 10 + 7 1

2

+ 16

+ * 12 15 1

1

1

+ 41

+ 21 2

19 1

23 * 20 1

2

* 30

1

+ 28 1

2

1

+ 38 1

* 35

* 39

1

1

* 3 1

2. ábra. Példa piros-fekete fa, a * jel piros, a + jel színt jelöl.

3

+ 47

a) x.apa==x.apa.apa.bal y=x.apa.apa.jobb + * a1 D X D y.szin==Piros * B + A

Y

X

* B

Y X

X

+ C

+ E + D

X

+ G

* C

a2a y.szin==Fekete x==x.apa.jobb

* D

* B

Y

+ F + G

* D + E

* B + C

+ A

a2b y.szin==Fekete x==x.apa.bal + * A E

+ C

* A

+ E

+ A

* C + F

+ A

+ B

* E

+ B

X =gyoker * D

+ C

+ E

˝ 3. ábra. Bovít-javít a) esetei: x = x.apa. jobb; 1: y.szin == Piros, 2: y.szin == Fekete

b) x.apa==x.apa.apa.jobb + b1 B y.szin==Piros Y

* A

+ B Y

+ A X

* E

+ C

b2a y.szin==Fekete x==x.apa.bal + * Y A F

+ B

+ G

+ C

X

* D

+ C

* E

* D X

+ A

+ G + D

b2b y.szin==Fekete x==x.apa.jobb * D

+ C

* F

+ E

+ E + B

Y

+ D

+ A

* D + C

X

y=x.apa.apa.bal * B

* B

X

+ A

* E

X =gyoker * E

+ C

˝ 4. ábra. Bovít-javít b) esetei: x = x.apa.bal ; 1: y.szin == Piros, 2: y.szin == Fekete

4

public static class PFFaPont<E extends Comparable<E>> extends BinKerFaPont<E>{ boolean szin=Piros; public PFFaPont(E x, PFFaPont<E> b, PFFaPont<E> j, PFFaPont<E> ap ){ super(x,b,j); this.apa=ap; } } private void BalraForgat(PFFaPont<E> p) { PFFaPont<E> r = (PFFaPont<E>)p.jobb; p.jobb = r.bal; if (r.bal != null) r.bal.apa = p; r.apa = p.apa; if (p.apa == null) gyoker = r; else if (p.apa.bal == p) p.apa.bal = r; else p.apa.jobb = r; r.bal = p; p.apa = r; } private void JobbraForgat(PFFaPont<E> p) { PFFaPont<E> l = (PFFaPont<E>)p.bal; p.bal = l.jobb; if (l.jobb != null) l.jobb.apa = p; l.apa = p.apa; if (p.apa == null) gyoker = l; else if (p.apa.jobb == p) p.apa.jobb = l; else p.apa.bal = l; l.jobb = p; p.apa = l; } public boolean Bovit(E x, boolean tobb){ PFFaPont<E> p =(PFFaPont<E>) gyoker; PFFaPont<E> pp = p; int ken=0; if (p == null) { gyoker = new PFFaPont<E>(x,null,null,p); ((PFFaPont<E>)gyoker).szin=Fekete; return true; } while (p != null) { pp=p; ken = x.compareTo(p.elem); if (ken < 0) p=(PFFaPont<E>)p.bal; else if (ken > 0) p=(PFFaPont<E>)p.jobb; else{ //= if (tobb)

5

p=(PFFaPont<E>)p.jobb; else return false; } }//while if (ken < 0){ pp.bal = new PFFaPont<E>(x,null,null,pp); BovitJavit((PFFaPont<E>)pp.bal); }else{ pp.jobb = new PFFaPont<E>(x,null,null,pp); BovitJavit((PFFaPont<E>)pp.jobb); } return true; } private void BovitJavit(PFFaPont<E> x) { x.szin = Piros; while (x != null && x != gyoker && ((PFFaPont<E>)x.apa).szin == Piros) { if (x.apa == x.apa.apa.bal) { //------- a1. eset -----PFFaPont<E> y=(PFFaPont<E>)x.apa.apa.jobb;// D+ ---> D*<-X if (y != null && y.szin == Piros) { // / \ / \ ((PFFaPont<E>)x.apa).szin = Fekete; // B* E*<-Y B+ E+ y.szin = Fekete; // / \ / \ ((PFFaPont<E>)y.apa).szin = Piros; // A+ C*<-X A+ C* x = (PFFaPont<E>)y.apa; //------ a2a. eset -----} else { // F+ ---> F+ if (x == x.apa.jobb) { // / \ / \ x = (PFFaPont<E>)x.apa; // B* G+<-Y D* G+ BalraForgat(x); // / \ / \ } // A+ D*<-X B* E+ // / \ / \ // C+ E+ A+ C+ //--------- a2b. eset -----((PFFaPont<E>)x.apa).szin = Fekete; // D+ ---> B+ ((PFFaPont<E>)x.apa.apa).szin = Piros; // / \ / \ if (x.apa.apa != null) // B* E+<-Y A* D* JobbraForgat((PFFaPont<E>)x.apa.apa); // / \ / \ } //X->A* C+ C+ E+ }else{ //x.apa == x.apa.apa.jobb //------ b1. eset ----PFFaPont<E> y=(PFFaPont<E>)x.apa.apa.bal; // B+ ---> B*<-X if (y != null && y.szin == Piros) { // / \ / \ ((PFFaPont<E>)x.apa).szin = Fekete; // Y->A* D* A+ D+ y.szin = Fekete; // / \ / \ ((PFFaPont<E>)x.apa.apa).szin = Piros; // X->C* E+ C* E+ x = (PFFaPont<E>)x.apa.apa; //-------- b2a. eset ----} else { // B+ ---> B+ if (x == x.apa.bal) { // / \ / \ x = (PFFaPont<E>)x.apa; //Y->A+ F* A+ D* JobbraForgat(x); // / \ / \ // X->D* G+ C+ F*<-X // / \ / \ // C+ E+ E+ G+ } //-------- b2b. eset -----6

((PFFaPont<E>)x.apa).szin = Fekete; ((PFFaPont<E>)x.apa.apa).szin = Piros; if (x.apa.apa != null) BalraForgat((PFFaPont<E>)x.apa.apa); }

// B+ ---> D+ // / \ / \ //Y->A+ D* B* E*<-X // / \ / \ // C+ E* A+ C+

} }//while ((PFFaPont<E>)gyoker).szin = Fekete; }//BovitJavit A B OVIT eljárás futási ideje legrosszabb esetben a fa magasságával arányos, tehát O(lg n) minden n pontú fára. Továbbá, legfeljebb két forgatás kell a helyreállításhoz.

4.2.

Törés

˝ törlés eljárásának módosításával kapható. Miután kitöröltük a kívánt pontot, A törlés algoritmusa a közönséges bináris keresofa végrehajtjuk a TÖRÖLJAVÍT eljárást, amely helyreállítja a fa piros-fekete tulajdonságát pontok átszínezésével és forgatásokkal. TÖRÖLJAVÍT eljárást csak akkor kell végrehajtani, ha a ténylegesen kitörölt pont színe fekete. Ekkor úgy tekintjük, hogy a kitörölt pont azon fia, amelyik a helyébe kerül átveszi ezt a feketét. Ha piros volt, akkor készen vagyunk, egyébként "kétszeresen" fekete lesz. Az a cél, hogy ezt az extra feketét eltüntessük átszínezéssel és lokális forgatással. a) x==x.apa.bal

w=x.apa.jobb 1.

+ B

X

++ A

W

+ D

+ E

+ C

+ E

* B

* D

X

++ A

W

+ C

X

+? B

w.szin==Piros ? B X

++ A

2.

W

+ D

+ A + E

+ C

* D + C

w.szin==Fekete, w mindkét fia fekete

5. ábra. Töröl-javít 1. és 2. esetei.

public boolean Torol(E x){ PFFaPont<E> p =(PFFaPont<E>) gyoker; PFFaPont<E> q; PFFaPont<E> pp; int ken; while (p!=null && (ken = x.compareTo(p.elem))!=0){ if (ken<0) p=(PFFaPont<E>)p.bal; else p=(PFFaPont<E>)p.jobb; } if (p==null) return false; if (p.bal != null && p.jobb != null){ 7

+ E

a) x==x.apa.bal

w=x.apa.jobb

X

++ A

? B

3.

? B

W

+ F

X

++ A

+ G

* D + C

+ D

W + C

* F + E

+ E

+ G

w.szin==Fekete, w.jobb.szin==Fekete (=> w.bal.szin==Piros) ?

? B

X

++ A

4.

W

D +

+ D

! C

+ E

B + A

* E

! C

w.szin==Fekete, w.jobb.szin==Piros ( w.bal.szin==Piros v Fekete )

6. ábra. Töröl-javít 3. és 4. esetei.

q=(PFFaPont<E>)p.jobb; while (q.bal!=null){ q=(PFFaPont<E>)q.bal; } p.elem=q.elem; //helyettesítés a követ˝ ovel p=q; } PFFaPont<E>

helyett=(PFFaPont<E>)(p.bal != null ? p.bal : p.jobb);

if (helyett != null) {//a törlend˝ o pontnak egy fia van:helyett helyett.apa = p.apa; if (p.apa == null) gyoker = helyett; else if (p == p.apa.bal) p.apa.bal = helyett; else p.apa.jobb = helyett; p.bal = p.jobb = p.apa = null; if (p.szin == Fekete) TorolJavit(helyett); } else if (p.apa == null) { // gyoker = null; } else {//a törlend˝ o pontnak nincs fia if (p.szin == Fekete) TorolJavit(p); if (p.apa != null) {// p kikapcsolása if (p == p.apa.bal) p.apa.bal = null; else if (p == p.apa.jobb) p.apa.jobb = null; p.apa = null; 8

} } return true; }//Torol private void TorolJavit(PFFaPont<E> x){ while (x != gyoker && x.szin == Fekete) { if (x == (PFFaPont<E>)x.apa.bal ) { //-------- a1. eset ------PFFaPont<E> w = (PFFaPont<E>)x.apa.jobb;// B+ ---> D+ // / \ / \ if (w.szin == Piros) { // X->A++ D*<-W B* E+ w.szin = Fekete; // / \ / \ ((PFFaPont<E>)x.apa).szin = Piros; // C+ E+ A++ C+<-W BalraForgat((PFFaPont<E>)x.apa); // w = (PFFaPont<E>)x.apa.jobb; // } // if ( (w.bal == null || //-------- a2. eset -------((PFFaPont<E>)w.bal).szin==Fekete)&& // B? ---> B?+<-X (w.jobb == null || // / \ / \ ((PFFaPont<E>)w.jobb).szin==Fekete)){// X->A++ D+<-W A+ D* w.szin = Piros; // / \ / \ x = (PFFaPont<E>)x.apa; // C+ E+ C+ E+ }else{ //-------- a3. eset -------if ( w.jobb == null || // B? ---> B? ((PFFaPont<E>)w.jobb).szin==Fekete){// / \ / \ ((PFFaPont<E>)w.bal).szin=Fekete; // X->A++ F+<-W A++ D+<-W w.szin = Piros; // / \ / \ JobbraForgat(w); // D* G+ C+ F* w = (PFFaPont<E>)x.apa.jobb; // / \ / \ } // C+ E+ E+ G+ w.szin = ((PFFaPont<E>)x.apa).szin; //------- a4. eset --------((PFFaPont<E>)x.apa).szin = Fekete; // B? ---> D? ((PFFaPont<E>)w.jobb).szin = Fekete; // / \ / \ BalraForgat((PFFaPont<E>)x.apa); // X->A++ D+<-W B+ E+ x = (PFFaPont<E>)gyoker; // / \ / \ } // C! E* A+ C! } else { // x == x.apa.jobb //------ b1. eset --------PFFaPont<E> w = (PFFaPont<E>)x.apa.bal;// // D+ ---> B+ if (w.szin == Piros) { // / \ / \ w.szin = Fekete; // W->B* E++<-X A+ D* ((PFFaPont<E>)x.apa).szin = Piros; // / \ / \ JobbraForgat((PFFaPont<E>)x.apa); // A+ C+ W->C+ E+<-X w = (PFFaPont<E>)x.apa.bal; // } // if ( (w.jobb == null || //------- b2. eset -------((PFFaPont<E>)w.jobb).szin==Fekete)&&// D? ---> D?+<-X (w.bal == null || // / \ / \ ((PFFaPont<E>)w.bal).szin==Fekete)){// W->B+ E++<-X B* E+ w.szin = Piros; // / \ / \ x = (PFFaPont<E>)x.apa; // A+ C+ A+ C+ } else { if (w.bal ==null ||

//------- b3. eset --------// F? ---> F?

9

((PFFaPont<E>)w.bal).szin==Fekete){// / \ / \ ((PFFaPont<E>)w.jobb).szin=Fekete; // W->B+ G++<-X E+ G++<-X w.szin = Piros; // / \ / \ BalraForgat(w); // A+ E* B* D+ w = (PFFaPont<E>)x.apa.bal; // / \ / \ // C+ D+ A+ C+ } //------- b4. eset --------w.szin = ((PFFaPont<E>)x.apa).szin; // D? ---> B? ((PFFaPont<E>)x.apa).szin = Fekete; // / \ / \ ((PFFaPont<E>)w.bal).szin = Fekete; // W->B+ E++<-X A+ D+ JobbraForgat((PFFaPont<E>)x.apa); // / \ / \ x = (PFFaPont<E>)gyoker; // A* C! C! E+ } // } } x.szin = Fekete; }//TorolJavit A TOROL eljárás futási ideje legrosszabb esetben a fa magasságával arányos, tehát O(lg n) minden n pontú fára. Továbbá, legfeljebb három forgatás kell a helyreállításhoz.

10