6.5. Piros-fekete fák

Ahogy azt láttuk, a lekérdező és módosító műveletek bonyolultsága arányos a vizsgált elem magasságával. Ezért a megközelítőleg teljes fákban optimálisak ezek a műveletek. Ennek megfelelően a naív beszúrás és törlés műveletét úgy módosítjuk, hogy közel teljes fát kapjunk. Ezt úgy tesszük meg, hogy a kiegyensúlyozott fákat használunk, azaz a fa bal- és jobboldali ágai közel egyforma hosszúak. Az egyik ilyen módszer a piros-fekete fák használata. Itt a fa minden egyes csúcsát pirosra vagy feketére festjük. Tehát a fa minden egyes csúcsa a következő információkat tartalmazza: szín, kulcs, bal, jobb, apa. Ha nem létezik a mutatott fiú, vagy apa, a megszokott Nil jelölést használjuk. A Nil-lel jelölt fiúkat, (más elnevezéssel a külső csúcsokat) most levélnek tekintjük, míg a belső csúcsok a kulccsal rendelkező pontok.

6.5.1. Piros-fekete tulajdonság

– Minden csúcs piros vagy fekete.

– Minden levél fekete.

– Minden piros pont mindkét fia fekete.

– Bármely két, azonos pontból induló és levélig vezető úton ugyanannyi fekete pont van.

Egy x pont fekete-magasságának nevezzük a pontból induló, levélig vezető úton található, x-et nem tartalmazó fekete pontok számát. Egy piros-fekete fa feketemagasságán a gyökér fekete-magasságát értjük. (A feltételek alapján tetszőleges út ugyanannyi fekete csúcsot tartalmaz, így a fekete magasság jól meghatározott érték.) Bármely n belső pontot tartalmazó piros-fekete fa magassága legfeljebb 2 log2(n+1). Mivel az ágakon ugyanannyi fekete csúcs található, és minden piros csúcsot fekete csúcs követ, így nincs olyan ág, melynek hossza egy másikénak kétszeresét meghaladná.

6.5.2. Forgatások

A naív beszúrások és törlések gyakran elrontják egy eredetileg piros-fekete fa piros-fekete tulajdonságát. Ezt a csúcsok átszinezésével illetve "forgatásával" állítjuk helyre. Mint az ábrából leolvasható a zöld részfa az x-nél kisebb, a kék részfa az y-nál nagyobb, a piros részfa az x és y közti elemeket tartalmazza. Az alábbiakban látható az előbbi ábra balra forgatásának a programja. A JOBBRA-FORGAT ennek szimmetrikus változata, melyben a jobb és bal mezőnevek helyet cserélnek.

Procedure BALRA-FORGAT(T,x) 
Input: A T fa, az x a piros-fekete tulajdonságot nem teljesítő csúcs 
Eredmény: Az y gyökerű fában helyreáll a piros-fekete tulajdonság 
1  y = x.jobb 
2  x.jobb = y.bal 
3  if y.bal != Nil then 
4     y.bal.apa = x 
5  endif
6  y.apa = x.apa 
7  if x.apa == Nil then 
8     T.gyöker = y 
9  else 
10    if x == x.apa.bal then 
11       x.apa.bal = y 
12    else 
13       x.apa.jobb = y 
14    endif
15 endif 
16 y.bal = x 
17 x.apa = y 

6.5.3. Piros-fekete beszúrás

Az algoritmusban szereplő három különböző eset a következő: A 6.5.1. ábra első fájába beszúrva az 1 elemet a piros-fekete tulajdonság sérül, ezért a most szinezünk (7-10. sor).

6.1. ábra - 6.5.1. ábra

6.5.1. ábra


Function PF-BESZÚR(T,x) 
Input: A T piros-fekete fa, az x a beszúrandó csúcs 
Eredmény: Az T fába beszúrja az x csúcsot 
1  BESZÚR(T,x) 
2  x.szín = PIROS 
3  while x != T.gyökér and x.apa.szín == PIROS do 
4     if x.apa == x.apa.apa.bal then 
5        y = x.apa.apa.jobb 
6        if y.szín == PIROS then 
7           x.apa.szín = FEKETE 
8           y.szín = FEKETE 
9           x.apa.apa.szín = PIROS 
10          x = x.apa.apa 
11       else 
12          if x == x.apa.jobb then 
13             x = x.apa 
14             BALRA-FORGAT(T,x) 
15          endif 
16          x.apa.szín = FEKETE 
17          x.apa.apa.szín = PIROS 
18          JOBBRA-FORGAT(T,x.apa.apa) 
19       endif 
20    else 
21       ugyanaz, csak az irányok felcserélődnek 
22    endif 
23 endw 
24 T.gyökér.szín = FEKETE

Az 6.5.2. ábra első fájába beszúrva a 2 elemet, a piros-fekete tulajdonság megint sérül, de átszinezés most nem elegendő. Ezért egy balra- majd egy jobbraforgatással lehet helyreállítani a fát (13-18. sor).

6.2. ábra - 6.5.2. ábra

6.5.2. ábra


A 6.5.3. ábra első fájába beszúrva az 1 elemet, az átszinezés most sem elegendő, viszont egy jobbraforgatással helyre lehet állítani a fát (16-18. sor).

6.3. ábra - 6.5.3. ábra

6.5.3. ábra

6.2. példa - 10. példa

És most készítsünk egy fát a 7, 4, 8, 9, 3, 2, 6, 5 és 1 elemek sorozatos piros-fekete beszúrásával!

6.4. ábra - A 7, 4 és 8 beszúrása

A 7, 4 és 8 beszúrása


6.5. ábra - A 9, 3 és 2 beszúrása

A 9, 3 és 2 beszúrása


6.6. ábra - A 6, 5 és 1 beszúrása

A 6, 5 és 1 beszúrása



6.5.4. Piros-fekete törlés

A piros-fekete törlés is a naív törlésre épül. Ha piros csúcsot töröltünk, akkor a fekete-magasságok nem változnak, tehát minden rendben van, nincs további műveletekre szükség. Ha fekete csúcsot töröltünk, akkor újra színezéssel és forgatással állítjuk helyre a piros-fekete tulajdonságot (PF-TÖRÖL-JAVÍT). Most a külső csúcsok is rendelkeznek a belső csúcsok mezőivel (szín, apa, stb.), hogy az algoritmus egyszerűbb legyen.

Procedure PF-TÖRÖL(T,z) 
Input: A T piros-fekete fa, az x a törlendő csúcs 
Eredmény: Az T fából törli az x csúcsot 
1  if z.bal == Nil or z.jobb == Nil then 
2     y = z 
3  else 
4     y = KÖVETKEZŐ(z)
5  endif 
6  if y.bal != Nil then 
7     x = y.bal 
8  else 
9     x = y.jobb
10 endif 
11 x.apa = y.apa 
12 if y.apa == NilT then 
13    T.gyökér = x 
14 else 
15    if y == y.apa.bal then 
16       y.apa.bal = x 
17    else 
18       y.apa.jobb = x 
19    endif
20 endif 
21 if y != z then 
22    z.kulcs = y.kulcs // hasonlóan a többi adatra 
23 endif 
24 if y.szín == FEKETE then 
25    PF-TÖRÖL-JAVÍT(T,x)
26 endif 
13 return y 

6.3. példa - 11. példa

Az előzőleg felépített fából töröljük az elemeket a beszúrás sorrendjében. A jobb nyomonkövethetőség érdekében a program futása során kapott átmeneti fákat is megadjuk.

6.7. ábra - A 7 törlése

A 7 törlése


6.8. ábra - A 4 törlése

A 4 törlése


6.9. ábra - A 8 törlése

A 8 törlése


6.10. ábra - A 9 és 3 törlése

A 9 és 3 törlése


6.11. ábra - A 6 és 5 törlése

A 6 és 5 törlése


Az interneten több Java animáció is található a piros-fekete fával kapcsolatban.A www.ece.uc.edu címen található programban a törlés nem az előbb ismertetett algoritmussal lett megoldva, ezért ajánlom kevésbé látványos programot, amely a pf-fa.htm állományban található.


Procedure PF-TÖRÖL-JAVÍT(T,x) 
Input: A T piros-fekete fa, az x az a csúcs, ahol sérül a piros-fekete tulajdonság 
Eredmény: Az T fában helyreáll a piros-fekete tulajdonság 
1  while x != T.gyökér and x.szín == FEKETE do 
2     if x == x.apa.bal then 
3        w = x.apa.jobb 
4        if w.szín == PIROS then 
5           w.szín = FEKETE 
6           x.apa.szín = PIROS 
7           BALRA-FORGAT(T,x.apa) 
8           w = x.apa.jobb 
9        endif 
10       if w.bal.szín == FEKETE and w.jobb.szín == FEKETE then 
11          w.szín = PIROS 
12          x = apa.x 
13       else 
14          if w.jobb.szín == FEKETE then 
15             w.bal.szín = FEKETE 
16             w.szín = PIROS 
17             JOBBRA-FORGAT(T,w) 
18             w = x.apa.jobb 
19          endif 
20          w.szín = x.apa.szín 
21          x.apa.szín = FEKETE 
22          w.jobb.szín = FEKETE 
23          BALRA-FORGAT(T,x.apa) 
24          x = T.gyökér 
25       endif 
26    else 
27       // ugyanaz, csak az irányok felcserélődnek 
28    endif 
29 endw 
30 x.szín = FEKETE