Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

5.5. Piros-fekete fák

5.5. Piros-fekete fák

5.11. Definíció. A piros-fekete fa

A piros-fekete fa olyan bináris keresőfa, melynek minden csúcsa egy extra bit információt tartalmaz (a csúcs színét, amely piros, vagy fekete) és rendelkezik az alábbi Piros-fekete fa tulajdonságokkal:

Minden csúcs színe piros, vagy fekete.

A gyökér színe fekete.

Minden levél (NIL) színe fekete, a levél nem tartalmaz kulcsot.

Minden piros csúcsnak mindkét fia fekete.

Bármely két, azonos csúcsból induló, levélig vezető úton ugyanannyi fekete csúcs van.

5.1. Példa.

5.12. Definíció. A piros-fekete fa fekete magassága

Egy piros-fekete fában egy csúcs fekete magasságának nevezzük az csúcsból kiinduló, levélig vezető úton található, x-et nem tartalmazó fekete csúcsok számát.

A fa fekete magasság a gyökércsúcs fekete magassága.

5.13. Tétel.

Bármely belső csúcsot tartalmazó piros-fekete fa magassága legfeljebb

MŰVELETEK:

A bináris kereső fák műveletei piros-fekete fában idő alatt elvégezhetők. Műveletek: BALRA_FORGAT , JOBBRA_FORGAT , PF_FÁBA_BESZÚR , PF_FÁBÓL_TÖRÖL .

5.2. Példa. A forgatások hatását az alábbi ábrával szemléltetjük.

A műveletek közül most csak a beszúrást írjuk le részletesebben.

5.5.1. Beszúrás

  1. Megkeressük az új elem helyét és oda piros színnel beszúrjuk.

  2. Csak a 3. Piros-fekete tulajdonság sérülhet abban az esetben, ha a beszúrt elem szülője piros. A cél, hogy az ilyen csúcsot feljebb és feljebb vigyük a fában úgy, hogy a többi tulajdonság ne sérüljön. Ha nem tudunk már feljebb menni, akkor forgatunk. (Feltehetjük, hogy a gyökér színe mindig fekete.)

  3. Jelölések: a vizsgált piros csúcs, az piros szülője ( szülője biztosan fekete) az testvére (-nek nagybácsija). Hat eset adódik, amely a szimmetria ( bal- vagy jobbgyerek) miatt 3-ra redukálódik:

    • [(a)] piros esetén és feketére szülő pirosra változtatása után a problémás csúcs már csak a szülő lehet, ez lesz az új vizsgálandó csúcs.

    • [(b)] fekete és -nak baloldali gyereke esetén jobbra forgatást és színcseréket végzünk: feketére, volt szülője pirosra vált.

    • [(c)] fekete és -nak jobboldali gyereke esetén olyan helyzetet állítunk elő, hogy -nak baloldali gyereke legyen balra forgatással ( és szerepcsere). Ezután a (b) eset áll elő.