Kétszínű fa

A kétszínű fa , vagy vörös-fekete fa vagy vörös és fekete fa a kiegyensúlyozott bináris keresési fa speciális típusa , amely az elméleti informatikában használt adatszerkezet . A kétszínű fákat 1972- ben találta ki Rudolf Bayer, aki a szimmetrikus bináris B-fákat (szó szerint " B-féle bináris szimmetrikus" -nak) nevezte. A fa minden csomópontjának saját adatain kívül van egy bináris attribútuma, amelyet gyakran "színének" (piros vagy fekete) értelmeznek. Ez az attribútum lehetővé teszi a fa egyensúlyának garantálását: az elemek beillesztésekor vagy törlésekor fenn kell tartani a csomópontok és azok színe közötti kapcsolatok bizonyos tulajdonságait, ami a legrosszabb esetben is megakadályozza a fa túlzott kiegyensúlyozatlanságát. A beillesztés vagy törlés során a csomópontok néha átrendeződnek vagy megváltoztatják színüket úgy, hogy ezek a tulajdonságok megmaradjanak.

A kétszínű fák legfőbb érdeke abban rejlik, hogy a csomópontok esetleges átrendeződése vagy színezése ellenére a beillesztési, keresési és törlési műveletek bonyolultsága (az elemek számában) logaritmikus. Ez a szerkezet ráadásul gazdaságos a memóriában, mivel csak egy további bit információt igényel elemenként, mint egy hagyományos bináris fa.

Történelem

1972-ben Rudolf Bayer olyan adatszerkezetet tervezett, amely egy 4. rendű B fa különleges esete volt, amelyben a fa gyökere és levelei közötti minden útnak ugyanannyi csomópontja volt, így fák lettek. Tökéletesen kiegyensúlyozottak (anélkül azonban, hogy binárisak lennének) fák keresése). Bayer "szimmetrikus bináris B fáknak" nevezte őket, később 2-3-4 faként népszerűsítették őket .

Egy 1978-ban címmel A kétszínű kerete Kiegyensúlyozott fák , Leonidas John Guibas és Robert Sedgewick épített piros-fekete fák szimmetrikus bináris B-fák. A színeket (piros és fekete) azért választották volna, mert jobban kitűntek a Xerox PARC lézernyomtatón , vagy egyszerűen csak azért, mert csak ezek a tollszínek voltak elérhetők.

A kétszínű fák műveleteinek referencia leírását (az eredeti 8 helyett csak 6 kiegyensúlyozatlan eset van) a Bevezetés az algoritmikába című könyv (Cormen és mtsai 2001) nekik szentelt fejezet tartalmazza .

Definíciók

A kétszínű fa a bináris fa speciális esete, az adatstruktúra , amelyet a számítástechnikában gyakran használnak összehasonlítható adatok, például számok vagy karakterláncok rendezésére.

A fa levelei, vagyis a terminális csomópontok nem tartalmaznak adatokat. Egyszerűen ábrázolhatók memóriaköltség nélkül null elemekkel (null mutató C-ben, NIL érték stb.) A szülőcsomópontban (jelezve, hogy a gyermekcsomópont levél). Hasznos lehet azonban egyes algoritmusok egyszerűsítése a levelek kifejezett megjelenítéséhez, vagy külön példányosítással, vagy őrszem használatával .

Mint minden bináris keresőfa , a kétszínű fák is nagyon hatékonyan kereshetők infix sorrendben (vagy bal - gyökér - jobb sorrendben), amely lehetővé teszi az elemek sorrendben történő felsorolását. Az elem keresése logaritmikus O (log n ) időben történik , n a fa elemeinek száma, beleértve a legrosszabb esetet is.

Tulajdonságok

A bicolor fa egy bináris kereső fa, amelyben minden csomópontnak van egy további attribútuma: színe, amely vagy piros, vagy fekete . A bináris keresési fákra vonatkozó korlátozások mellett a következő szabályokat alkalmazzák:

Egy csomópont vörös vagy fekete;
A gyökér fekete;
A vörös csomó gyermekei fekete színűek;
Minden csomópontnak 2 gyermeke van. Ezek más csomópontok vagy NIL lapok , amelyeknek nincs értékük, és ezek az egyetlen csomópontok gyermek nélkül. Színük mindig fekete , ezért figyelembe veszik a fekete magasság kiszámításakor.
A gyökértől bármely levélig ( NIL ) vezető út ugyanannyi fekete csomópontot tartalmaz. Ezt a fekete csomópontok számát fekete magasságnak nevezhetjük .

Ezek a korlátozások a kétszínű fák fontos tulajdonságát vonják maguk után: a gyökértől a levélig (annak magassága) a lehető leghosszabb út csak kétszer hosszabb lehet, mint a lehető legkisebb: a legkiegyensúlyozatlanabb esetben az utak közül a legrövidebb csak fekete csomó, és a leghosszabb a vörös és a fekete csomó között váltakozik. Az ilyen tulajdonságokat kielégítő fa tehát szinte kiegyensúlyozott . Mivel a beillesztési, keresési és törlési műveletek a fa magasságával arányos legrosszabb időt igénylik, a kétszínű fák hatékonyak maradnak, ellentétben a szokásos bináris kereső fákkal .

Annak megértéséhez, hogy ezek a megszorítások miként garantálják a fenti tulajdonságot, elegendő észrevenni, hogy egyetlen útnak sem lehet két egymást követő piros csomópontja a 3. tulajdonság miatt. A gyökértől a levélig a legkisebb elméleti út fekete csomóként szerepel, míg a nagyobbik váltakozik a piros és fekete csomókat. És mivel az 5. tulajdonság szerint ezek az utak mindegyike azonos számú fekete csomópontot tartalmaz, a nagyobb út nem lehet kétszer akkora, mint a kisebb.

A 2. tulajdonság nem szükséges. Az egyetlen eset, amikor a gyökér pirosra fordulhat, az a két eset, amikor a színe nem számít: vagy a gyökér az egyetlen csomópont, vagy két fekete szála van. Ez a tulajdonság csak azért kerül hozzáadásra, hogy 2-3-4 fával gyorsabban szemlélje az izomorfizmust: minden fekete csomópont és lehetséges vörös gyermekei 2-3-4 facsomót képviselnek.

Használat és előnyök

A kétszínű tengelyek, valamint az AVL tengelyek nyújtják a legjobb garanciát a behelyezésre, a törlésre és a keresési időre kedvezőtlen esetekben. Ez nem csak lehetővé teszi számukra, hogy a valós idejű alkalmazásokban használhatók legyenek, hanem kedvezőtlen esetekben garantált végrehajtási idővel rendelkező egyéb adatstruktúrák alapjául is szolgálhatnak, például algoritmikus geometriában . Az ütemező a Linux kernel , a teljesen igazságos ütemező használ is egy piros-fekete fa.

A vörös-fekete fák nagyon hasznosak a funkcionális programozásban is : ez az állandó adatstruktúra leggyakrabban használt példája, amely felhasználható olyan asszociatív tömbök felépítésére, amelyek képesek a korábbi változatok memóriában tartására egy változás után. A vörös-fekete fák állandó változatai O (log n ) további memóriát igényelnek minden egyes beszúráshoz vagy törléshez.

Tevékenységek

A bicolor fán történő keresést pontosan úgy végezzük, mint a bináris kereső fáknál . A behelyezés vagy törlés után azonban a bicolor fa tulajdonságai sérülhetnek. Ezeknek a tulajdonságoknak a visszaállításához kis számú ( ) színváltozásra van szükség (ami a gyakorlatban nagyon gyors), és legfeljebb három forgatásra van szükség (kettő beillesztésre). Ez lehetővé teszi a beillesztést és a törlést, de a megvalósítást bonyolultabbá teszi a kezelendő speciális esetek nagy száma miatt. $O (\ log (n))$ $O (\ log (n))$

Ebben a részben egy C megvalósítás segítségével szemléltetjük a műveleteket, a fa szerkezetének következő meghatározása alapján.

#define NOIR 0 #define ROUGE 1 #define FEUILLE NULL struct noeud { struct noeud *gauche; //Pointeur vers fils gauche struct noeud *droit; //Pointeur vers fils droit struct noeud *parent; //Pointeur vers père int couleur; // ROUGE ou NOIR int clé; // Peut être n'importe quel type, tant que les opérations de comparaison (<, = , > ) sont définies };

A következő funkciókat fogjuk használni az adott csomópont (szülő, nagyszülő stb.) "Genealógiájához" is.

struct noeud* parent(struct noeud* n) { return n->parent; } struct noeud* grandparent(struct noeud* n) { struct noeud* p = parent(n); if (p == NULL) return NULL; // Un noeud sans parent n'a pas de grand-parent return parent(p); } struct noeud* frere(struct noeud* n) { struct noeud* p = parent(n); if (p == NULL) return NULL; // Un noeud sans parent n'a pas de frere if (n == p->gauche) return p->droit; else return p->gauche; } //Renvoie le frère du père struct noeud* oncle(struct noeud* enfant) { struct noeud* p = parent(enfant); struct noeud* g = grandparent(enfant); if (g == NULL) return NULL; // Pas de grand parent, donc pas d'oncle return frere(p); }

Végül szükségünk lesz a bináris fák forgatására:

void rotation_gauche(struct noeud* x) { struct noeud* y = x->droit; //le fils droit de x devient le fils gauche de y x->droit = y->gauche; if (y->gauche != FEUILLE) y->gauche->parent = x; y->parent = x->parent; //Si x est la racine, y devient la racine if (x->parent == NULL) x = y; //Sinon, on remplace x par y else if (x == x->parent->gauche) x->parent->gauche = y; else x->parent->droit = y; //On attache x à gauche de y y->gauche = x; x->parent = y; } void rotation_droite(struct noeud* x) { struct noeud* y = x->gauche; //le fils gauche de x devient le fils droit de y x->gauche = y->droit; if (y->droit != FEUILLE) y->droit->parent = x; y->parent = x->parent; //Si x est la racine, y devient la racine if (x->parent == NULL) x = y; //Sinon, on remplace x par y else if (x == x->parent->droit) x->parent->droit = y; else x->parent->gauche = y; //On attache x à droite de y y->droit = x; x->parent = y; }

Elem keresése

Az elem keresése ugyanúgy történik, mint egy bináris keresőfánál: a gyökérből kiindulva összehasonlítjuk a keresett értéket a fa aktuális csomópontjának értékével. Ha ezek az értékek megegyeznek, a keresés befejeződik, és az aktuális csomópont visszatér. Ellenkező esetben úgy döntünk, hogy lemegyünk a bal vagy a jobb gyermekcsomópontra attól függően, hogy a keresett érték alacsonyabb vagy magasabb. Ha elért egy levelet, a keresett érték nem található meg a fán.

A fa csomópontjainak színe közvetlenül nem avatkozik be a keresésbe. Azonban a normál bináris kereső fától eltérően a vörös-fekete fák a legrosszabb esetben is garantálják a keresés O-ban (log n ) történő végrehajtásának idejét . Valójában a bináris keresőfa kiegyensúlyozatlanná válhat kedvezőtlen esetekben (például ha az elemeket növekvő sorrendbe helyezzük, a bináris keresési fa egy kapcsolt listává degenerálódik ). A művelet bonyolultsága a legrosszabb esetben tehát O ( n ) egy potenciálisan kiegyensúlyozatlan bináris fára. Éppen ellenkezőleg, a piros-fekete fa esetében a fent látható kétszínű tulajdonságok garantálják, hogy egy csomópont legfeljebb 2 log n összehasonlításban, tehát O (log n ) műveletben érhető el .

Beszúrás

A beszúrás ugyanúgy kezdődik, mint egy klasszikus bináris fán: a gyökérből kiindulva összehasonlítjuk a beillesztett értéket a fa aktuális csomópontjának értékével, és úgy döntünk, hogy lemegyünk a bal vagy a jobb gyermekcsomópontra attól függően, hogy a beillesztett érték alacsonyabb vagy magasabb. Az új csomópont akkor kerül beillesztésre, ha már nem lehet leszállni, vagyis amikor az aktuális csomópont a fa levele. Ezt a lapot az új csomópont helyettesíti.

struct noeud *insertion(struct noeud *racine, struct noeud *n) { // Insertion d'un nouveau nœud dans l'arbre insertion_recursif(racine, n); // Réparation de l'arbre au cas où les propriétés rouge-noir seraient violées insertion_repare_arbre(n); // Recherche de la nouvelle racine à renvoyer racine = n; while (parent(racine) != NULL) racine = parent(racine); return racine; } void insertion_recursif(struct noeud *racine, struct noeud *n) { // Descente récursive dans l'arbre jusqu'à atteindre une feuille if (racine != NULL && n->clé < racine->clé) { if (racine->gauche != FEUILLE) { insertion_recursif(racine->gauche, n); return; } else racine->gauche = n; } else if (racine != NULL) { if (racine->droit != FEUILLE) { insertion_recursif(racine->droit, n); return; } else racine->droit = n; } // Insertion du nouveau noeud n n->parent = racine; n->gauche = FEUILLE; // NIL n->droit = FEUILLE; // NIL n->couleur = ROUGE; }

Miután hozzáadta az új csomópontot a fához, ellenőrizni kell, hogy a kétszínű fa tulajdonságai megfelelően vannak-e tiszteletben tartva, és ha nem, akkor színváltoztatási műveleteket és forgatásokat kell végrehajtania azok helyreállítása érdekében. A behelyezett csomópont kezdetben vörös színű . Ezután több lehetséges eset áll rendelkezésre a fa tulajdonságainak visszaállítására a beillesztett csomópontból.

void insertion_repare_arbre(struct noeud *n) { if (parent(n) == NULL) insertion_cas1(n); else if (parent(n)->couleur == NOIR) insertion_cas2(n); else if (oncle(n)->couleur == ROUGE) insertion_cas3(n); else insertion_cas4(n); }

A beillesztett csomópontnak nincs szülője: valójában a fa gyökerében található. Az egyetlen javítás, amelyet fekete színnel kell színezni a 2. tulajdonság tiszteletben tartása érdekében.void insertion_cas1(struct noeud *n) { if (parent(n) == NULL) n->couleur = NOIR; }
A beillesztett csomópont szülője fekete , akkor a fa érvényes: a 3 tulajdonság be van jelölve, és a fa fekete magassága változatlan, mivel az új csomópont piros . Tehát nincs más tennivaló.void insertion_cas2(struct noeud *n) { return; /* Ne rien faire puisque l'arbre est bien un arbre rouge-noir */ }
A beillesztett csomópont szülője piros , ezért a 3. tulajdonság érvénytelen. A teendő a beillesztett csomópont nagybátyjának színétől , azaz a beillesztett csomópont szülőjének "testvérétől" függ. Más szavakkal: a beillesztett csomópontból (N) kiindulva tekintjük annak szülőcsomópontját (P), majd P szülőcsomópontját vagy nagyszülőjét (G), végül pedig a nagybátyát (U), aki G fia. nem P. Ha a bácsi piros , akkor a szülő és a bácsi fekete színű , a nagyszülő (aki szükségszerűen fekete volt) pedig vörös . Ez a színváltozás azonban további sérülést okozhatott a fán fentebb lévő két szín tulajdonságában. Most meg kell ismételni ugyanazt az esetelemzést, de ezúttal az így pirosra színezett nagyszülő csomópontból kell kiindulni .void insertion_cas3(struct noeud *n) { parent(n)->couleur = NOIR; oncle(n)->couleur = NOIR; struct noeud *g = grandparent(n); g->couleur = ROUGE; insertion_repare_arbre(g); }
Abban az esetben, ha a bácsi fekete , el kell végeznie olyan forgatásokat, amelyek a szülője és a nagyszüle körül beillesztett csomópont konfigurációjától függenek, hogy helyrehozzák az egyensúlyt a fában.void insertion_cas4(struct noeud *n) { struct noeud *p = parent(n); struct noeud *g = grandparent(n); if (n == g->gauche->droit) { rotation_gauche(p); n = n->gauche; } else if (n == g->droit->gauche) { rotation_droit(p); n = n->droit; } insertion_cas5(n); }
A szülő a nagyszülő helyét veszi át, a nagyszülő pedig a nagybátyáét. A szülő fekete lesz , a nagyszülő pedig piros , a fa pedig tiszteletben tartja a kétszínű tulajdonságokat.void insertion_cas5(struct node *n) { struct noeud *p = parent(n); struct noeud *g = grandparent(n); if (n == p->gauche) rotation_droit(g); else rotation_gauche(g); p->couleur = NOIR; g->couleur = ROUGE; }

Az egyetlen eset, amikor a javítás nem ér véget azonnal, a 3. eset, amikor a nagyszülő feketéről vörösre vált, ami új ellenőrzést kényszerít a nagyszülőtől kezdve. Könnyen ellenőrizhető azonban, hogy a funkció mindig véget ér-e. Mivel az ellenőrizni kívánt csomópont mindig szigorúan magasabb, mint az előző, elkerülhetetlenül a nem rekurzív esetek egyikébe kerülünk (a legrosszabb esetben felmegyünk, amíg el nem érjük a fa gyökerét, vagyis 1). Ezért legfeljebb két elfordulás lehet, és számos színváltozás kevesebb, mint a fa magasságának fele, vagyis O-ban (log n ). A gyakorlatban a valószínűsége, hogy egymás után többször elesik a 3. esetben, exponenciálisan csökken; átlagosan tehát a tulajdonságok javításának költsége szinte állandó.

Törlés

A törlés a törlendő csomópont keresésével kezdődik, mint egy klasszikus bináris fában.

Ne feledje, hogy mindig abban az esetben tehetjük magunkat, amikor a törlendő csomópontnak legfeljebb egy gyermeke van, amely nem levél. Abban az esetben, ha az eltávolítandó csomópontnak két gyermeke van, akik nem levelek, akkor a bal részfa egyik legnagyobb elemét (vagyis a csomópontot közvetlenül megelőző elemet a fa sorrendjében) keressük a legkisebb elemnek a jobb alfa (azaz a közvetlen utód). A törlendő csomópont értékét felváltja az előd vagy az utód értéke, és ez az utolsó csomópont, amelynek értékét éppen másolták, törlődik. Vegye figyelembe, hogy egy érték másolása nem változtatja meg a fa kétszínű tulajdonságait.

A fáról hatékonyan törölni kívánt csomópontnak tehát legfeljebb egy gyermeke lesz, amely nem levél. M-vel jelöljük a törlendő csomópontot. M-nek tehát van vagy nem levél gyermeke (megjegyezte C), vagy nincs (ebben az esetben a levelek egyikét választjuk a C-hez). Törlés után az M által elfoglalt helyet a fában C foglalja el.

A legegyszerűbb esetben a törölt M csomópont piros : elég, ha kicseréljük gyermekével C, amely a 3. tulajdonság alapján szükségszerűen fekete . Az M eltávolításával nem változtatjuk meg a fa fekete magasságát., Ezért a tulajdonságok mind tiszteletben maradnak.

Egy másik egyszerű eset akkor fordul elő, ha a törölt M csomópont fekete, de gyermeke C piros . Az M eltávolításával csökkentjük a fa negyedmagasságát, ami sértené az 5. tulajdonságot. Ezenkívül M szülője P lehet piros: vagy C helyettesíti M-t P fiaként, ami szintén megsértheti a 3. tulajdonságot. Ezeket a tulajdonságokat a visszaállított egyszerűen színező C fekete .

A legbonyolultabb eset akkor fordul elő, ha a törölt M csomópont és annak gyermeke C egyaránt fekete .

Megjegyzések és hivatkozások

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein , Bevezetés az algoritmikába , Dunod ,2002[ a kiadás részlete ].
Rudolf Bayer, „ Szimmetrikus bináris B-fák: adatszerkezet és karbantartási algoritmusok ”, Acta Informatica , vol. 1, n o 4,1972, P. 290–306 ( DOI 10.1007 / BF00289509 , online olvasás )
(in) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein , Bevezetés az algoritmusokba , Cambridge (Massachusetts), MIT Press,2001, második kiadás , 273–301 p. ( ISBN 978-0-262-03293-3 , használati BNF n o FRBNF38834736 ) , "Red-Black Fák"
Leo J. Guibas és Robert Sedgewick : „ A kiegyensúlyozott fák dikromatikus kerete ”, (: nincs) ,1978. október( DOI 10.1109 / sfcs.1978.3 , online olvasás , hozzáférés : 2019. március 25. )
„ adatszerkezetek - Hol jelent a” Red / Black Tree „származik? » , On Software Engineering Stack Exchange (hozzáférés : 2019. március 25. )