Arbori: rou-negru

Arborele rou-negru este un arbore binar de cutare care are un bit suplimentar pentru memorarea fiecrui nod:culoareaacestuia, care poate fi ROUsauNEGRU.Prin restrngerea modului n care se coloreaz nodurile pe orice drum de la rdcina la o frunz, arborii rou-negru garanteaz c nici un astfel de drum nu este mai lung dect dublul lungimii oricrui alt drum, deci c arborele este aproximativ echilibrat.Propozitia urmtoare arat de ce arborii rou-negru sunt echilibrai: un arbore rou-negru cunnoduri are adncimea cel mult 2log(n+1).Fiecare nod al arborelui conine cmpurile culoare, cheie, stnga, dreapta i p. Daca fiul sau printele unui nod nu exist, cmpul pointer corespunztor din nod are valoarea null.Un arbore binar de cutare este arbore rou-negru dac el indeplinete urmtoarele proprieti rou-negru:1) Fiecare nod este fie rou, fie negru.2) Rdcina este ntodeauna neagr.3) Fiecare frunz (null) este neagr.4) Daca un nod este rou, atunci ambii fii ai si sunt negri.5) Fiecare drum simplu de la un nod la un descendent care este frunza conine acelai numr de noduri negre.Numrul de noduri negre pe orice drum de la un nod n jos spre o frunz se va numinlime neagra nodului. Noiunea de nlime neagr este bine definit pe baza proprietii 4, conform creia toate drumurile de la nod n jos au acelai numr de noduri negre. Vom defini nlimea neagr a unui arbore rou-negru ca fiind nlimea neagr a rdcinii sale.Arborii rou-negru au dezavantajul ca dupa fiecare inserare/tergere a unui nod, codul trebuie reparcurs pentru a face corectrile de rigoare, acestea constnd n rotiri i recolorri ale nodurilor (dupa cum se poate vedea i n codul din programul urmtor).

Implementare in C++:

#include#include

typedef struct arbore{ int rosu; int negru; struct nod;}nod *st,*dr,*parinte; void rotire_st( arbore T; nod x ) /* procedura de rotatie la stanga transforma configuratia celor doua noduri prin schimbarea unui numar constant de pointeri */{ nod y; y = x->dr; /* setam y *//* Intoarecem stanga lui y in dreapta lui x */ x->dr = y->st; if ( y->st != NULL )y->st->parinte = x;/* parintele nou a lui y a fost parintele lui x */ y->parinte = x->parinte;/* Setam parinte lui y in locul lui x *//* Prima data vedem dak suntem in radacina */ if ( x->parinte == NULL ) T->radacina = y; elseif ( x == (x->parinte)->st ) /* x a fost in stanga parintilor */ x->parinte->st = y;else /* x trebuia sa fie in dreapta */ x->parinte->dr = y; /* In final, punem pe x in stanga lui y*/ y->st = x; x->parinte = y; }void rb_insereaza( arbore T, nod x ) /* putem insera un nod intr-un arbore rosu-negru in O(lg n) timp. Pentru aceasta trebuie sa folosim o versiune putin modificata a functiei de inserare in arbore */{ /* Se inseara in arbore normal */ arbore_insereaza( T, x ); /* Acum returnam proprietataea rosu si negru */ x->culoare = rosu;/* urmatoarea parte de cod e necesara deoarece in urma procedurii de inserare se poate ca radacina sa nu mai fie neagra (regula 2) sau ca un nod rosu sa aiba fii de acceasi culoare (regula 4) */ while ( (x != T->radacina) && (x->parinte->culoare == rosu) ) { if ( x->parinte == x->parinte->parinte->st ) { /* Daca parintele lui x se afla in dreapta, y este in drepta lui x*/ y = x->parinte->parinte->right; if ( y->culoare == rosu ) { /* caz 1 - schimbam culorile */ x->parinte->culoare = negru; y->culoare = negru; x->parinte->parinte->culoare = rosu; /* mutam pe x in sus */ x = x->parinte->parinte; } else { /* y este un nod negru */ if ( x == x->parinte->dr ) { /* si x este in dreapta */ /* caz 2 - mutam pe x sus si rotim */ x = x->parinte; rotire_st( T, x ); } /* case 3 */ x->parinte->culoare = negru; x->parinte->parinte->culoare = rosu; rotire_dr( T, x->parinte->parinte ); } } else { /* repeteam If`u pana se schimba stanga cu dreapta */ } } /* se coloreaza radacina negra */ T->radacina->culoare = negru; }void main() /* functia principala */{}

3