Copac roșu-negru

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 2 noiembrie 2019; verificările necesită 32 de modificări .

Copac roșu-negru

Tip de

arborele de căutare

Anul inventiei

1972

Autor

Rudolf Baier

Complexitatea în simbolurile O

	In medie	În cel mai rău caz
Consumul de memorie	Pe)	Pe)
Căutare	O(log n)	O(log n)
Introduce	O(log n)	O(log n)
Îndepărtarea	O(log n)	O(log n)

Fișiere media la Wikimedia Commons

Arborele roșu-negru ( ing. arbore roșu-negru , arbore RB ) este unul dintre tipurile de arbori de căutare binari cu auto-echilibrare care garantează o creștere logaritmică a înălțimii arborelui din numărul de noduri și vă permite să efectuați rapid arborele de căutare de bază operațiuni: adăugarea, ștergerea și găsirea unui nod. Echilibrul se realizează prin introducerea unui atribut suplimentar al nodului arborelui - „culori”. Acest atribut poate lua una dintre cele două valori posibile - „negru” sau „roșu”.

Inventatorul german Rudolf Bayer este considerat inventatorul copacului roșu-negru . Numele „arbore roșu-negru” a fost dat structurii datelor într-un articol de L. Gimbas și R. Sedgwick (1978). Potrivit lui Gimbas, au folosit pixuri bicolore [1] . Potrivit lui Sedgwick, roșul arăta cel mai bine pe o imprimantă laser [1] [2] .

Arborele roșu-negru este folosit pentru a organiza date comparabile, cum ar fi fragmente de text sau numere. Nodurile frunzelor arborilor roșu-negru nu conțin date, deci nu necesită alocare de memorie - este suficient să scrieți un pointer nul ca indicator către copilul din nodul strămoș. Cu toate acestea, în unele implementări, nodurile frunză explicite pot fi utilizate pentru a simplifica algoritmul.

Principiul organizării

Un arbore roșu-negru este un arbore binar de căutare în care fiecare nod are un atribut de culoare . în care:

Un nod poate fi roșu sau negru și are doi copii;
Rădăcina este de obicei neagră. Această regulă are un efect redus asupra performanței modelului, deoarece culoarea rădăcinii poate fi întotdeauna schimbată de la roșu la negru;
Toate frunzele care nu conțin date sunt negre.
Ambii copii ai fiecărui nod roșu sunt negri.
Orice cale simplă de la un nod strămoș la un nod frunză copil conține același număr de noduri negre.

Datorită acestor restricții, drumul de la rădăcină la cea mai îndepărtată frunză nu este mai mare de două ori mai lungă decât la cea mai apropiată, iar copacul este aproximativ echilibrat. Operațiile de inserare, ștergere și căutare necesită, în cel mai rău caz, timp proporțional cu lungimea arborelui, ceea ce permite arborilor roșu-negru să fie mai eficienți în cel mai rău caz decât arborii de căutare binare convenționale.

Pentru a înțelege cum funcționează, este suficient să luăm în considerare efectul proprietăților 4 și 5 împreună. Fie numărul de noduri negre de la rădăcină la o frunză B pentru un arbore roșu-negru T. Atunci cea mai scurtă cale posibilă către orice frunză conține B noduri și toate sunt negre. O cale posibilă mai lungă poate fi construită prin includerea nodurilor roșii. Cu toate acestea, din cauza clauzei 4, arborele nu poate avea două noduri roșii la rând și conform clauzelor 2 și 3, drumul începe și se termină cu un nod negru. Prin urmare, cea mai lungă cale posibilă constă din 2B-1 noduri, alternativ roșu și negru.

Dacă permiteți unui nod fără frunză să aibă mai puțin de doi copii și unui nod frunză să conțină date, arborele păstrează proprietățile de bază, dar algoritmii de lucru cu acesta devin mai complicati. Prin urmare, articolul se ocupă doar de „noduri de frunze false”, care nu conțin date și servesc pur și simplu pentru a indica unde se termină arborele. Aceste noduri pot fi omise în unele ilustrații. Din punctul 5, rezultă, de asemenea, că descendenții nodului roșu pot fi fie două noduri intermediare negre, fie două frunze negre, și ținând cont de articolele 3 și 4 - că dacă unul dintre descendenții nodului negru este un nod de frunză , atunci al doilea ar trebui să fie, de asemenea, foaie, sau designul descris mai sus de o foaie roșie și două.

De asemenea, în literatură există o interpretare în care nu nodurile în sine, ci marginile care duc la ele sunt vopsite în culori roșu / negru - dar acest lucru nu este de mare importanță pentru înțelegerea principiului funcționării sale.

Analogia arborelui B cu parametrul 4

Un arbore roșu-negru este similar ca structură cu un arbore B cu parametrul 4, în care fiecare nod poate conține de la 1 până la 3 valori și, în consecință, de la 2 până la 4 pointeri către copii. Într-un astfel de arbore B, fiecare nod va conține o singură valoare, corespunzătoare valorii nodului negru al arborelui roșu-negru, cu valori opționale înainte și/sau după acesta în același nod, ambele corespund la nodurile roșii echivalente ale arborelui roșu-negru.

O modalitate de a vedea această echivalență este de a „ridica” nodurile roșii în reprezentarea grafică a arborelui roșu-negru, astfel încât acestea să fie la nivel orizontal cu strămoșii lor nod negri, formând o pagină. Într-un arbore B sau într-o reprezentare grafică modificată a unui arbore roșu-negru, toate nodurile frunzelor au aceeași adâncime.

Acest tip de arbore B este mai general decât un arbore roșu-negru, deși, după cum puteți vedea, mai mulți arbori roșu-negru pot fi obținuți dintr-un astfel de arbore B cu parametrul 2. Dacă o pagină B-tree conține o singură valoare, nodul este negru și are doi copii. Dacă pagina conține trei valori, atunci nodul central este negru, iar fiecare dintre vecinii săi este roșu. Totuși, dacă pagina conține două valori, orice nod poate deveni negru în arborele roșu-negru (caz în care al doilea va fi roșu).

Lucrul cu copaci roșu-negri

Arborele roșu-negru sunt unul dintre cei mai folosiți arbori de căutare auto-echilibrați în practică. În special, containerele de set și map din majoritatea implementărilor bibliotecii C++ STL [3] , clasa Java TreeMap [4] , precum și multe alte implementări de matrice asociative din diferite biblioteci, se bazează pe arbori roșu-negru.

Copacii roșu-negri sunt mai populari decât copacii perfect echilibrați. în cel din urmă, prea multe resurse pot fi cheltuite pentru ștergerea din arbore și menținerea echilibrului necesar. După inserare sau ștergere, este necesară o operație de recolorare, care necesită (O(log n ) sau O(1)) schimbări de culoare (ceea ce este destul de rapid în practică) și nu mai mult de trei rotații ale arborelui (nu mai mult de două pentru inserare). ). Deși inserarea și ștergerea sunt complexe, ele sunt încă intensive în muncă O(log n ).

Inserați

Un nou nod în arborele roșu-negru este adăugat în locul uneia dintre frunze, colorate în roșu, și două frunze sunt atașate acestuia (deoarece frunzele sunt o abstractizare care nu conține date, adăugarea lor nu necesită o operațiune suplimentară) . Ce se întâmplă în continuare depinde de culoarea nodurilor din apropiere. Observa asta:

Proprietatea 3 (Toate frunzele sunt negre) este întotdeauna adevărată.
Proprietatea 4 (Ambele copii ai oricărui nod roșu sunt negri) poate fi încălcată numai prin adăugarea unui nod roșu, prin recolorarea unui nod negru în roșu sau prin rotirea lui.
Proprietatea 5 (Toate căile de la orice nod la nodurile frunză conțin același număr de noduri negre) poate fi încălcată numai prin adăugarea unui nod negru, recolorarea unui nod roșu în negru (sau invers) sau rotirea.

Notă : litera N va desemna nodul curent (colorat în roșu). În primul rând, noul nod este inserat, dar această procedură poate fi aplicată recursiv altor noduri (vezi cazul 3). P va desemna strămoșul lui N , G va desemna bunicul lui N , iar U va desemna unchiul (nodul care are un părinte comun cu nodul P ). Rețineți că în unele cazuri rolurile nodurilor se pot schimba, dar în orice caz, fiecare desemnare va reprezenta același nod ca la început. Orice culoare descrisă în figură este fie presupusă în acest caz, fie obținută din alte considerente.

Fiecare caz este acoperit cu exemple de cod C. O definiție a structurii nodului ar putea arăta astfel:

enumerare node_culos { RED , BLACK }; struct node { struct node * părinte , * stânga , * dreapta ; enum node_colors culoare ; intkey ; _ };

Unchiul și bunicul nodului curent pot fi găsiți folosind funcțiile:

nod struct * bunicul ( struct node * n ) { dacă (( n != NULL ) && ( n -> părinte != NULL )) return n -> părinte -> părinte ; altfel returnează NULL ; } nod struct * uncle ( struct node * n ) { struct node * g = bunicul ( n ); dacă ( g == NULL ) returnează NULL ; // Nici un bunic înseamnă nici un unchi dacă ( n -> părinte == g -> stânga ) intoarce g -> dreapta ; altfel întoarcere g -> stânga ; }

Rotirea la stânga și la dreapta a arborelui se poate face astfel:

gol rotiți_stânga ( nodul structura * n ) { struct node * pivot = n -> dreapta ; pivot -> părinte = n -> părinte ; /* posibil să facă pivotarea rădăcinii arborelui */ dacă ( n -> părinte != NULL ) { dacă ( n -> părinte -> stânga == n ) n -> părinte -> stânga = pivot ; altfel n -> părinte -> dreapta = pivot ; } n -> dreapta = pivot -> stânga ; if ( pivot -> stânga != NULL ) pivot -> stânga -> părinte = n ; n -> părinte = pivot ; pivot -> stânga = n ; } gol rotiți_dreapta ( nodul de structură * n ) { struct node * pivot = n -> stânga ; pivot -> părinte = n -> părinte ; /* posibil să facă pivotarea rădăcinii arborelui */ dacă ( n -> părinte != NULL ) { dacă ( n -> părinte -> stânga == n ) n -> părinte -> stânga = pivot ; altfel n -> părinte -> dreapta = pivot ; } n -> stânga = pivot -> dreapta ; if ( pivot -> dreapta != NULL ) pivot -> dreapta -> părinte = n ; n -> părinte = pivot ; pivot -> dreapta = n ; }

Cazul 1: Nodul curent N este la rădăcina arborelui. În acest caz, este vopsit în negru pentru a menține proprietatea 2 (rădăcina este neagră) adevărată. Deoarece această acțiune adaugă un nod negru la fiecare cale, proprietatea 5 (Toate căile de la orice nod dat la nodurile frunză conțin același număr de noduri negre) nu este încălcată.

gol insert_case1 ( struct node * n ) { dacă ( n -> părinte == NULL ) n -> culoare = NEGRU ; altfel insert_case2 ( n ); }

Cazul 2: părintele P al nodului curent este negru, adică proprietatea 4 (ambele copii ai fiecărui nod roșu sunt negri) nu este încălcată. În acest caz, arborele rămâne corect. Proprietatea 5 (Toate căile de la orice nod dat la nodurile frunză conțin același număr de noduri negre) nu este încălcată deoarece nodul curent N are doi copii frunze negre, dar deoarece N este roșu, calea către fiecare dintre acești copii conține același numărul de noduri negre, care este calea către frunza neagră care a fost înlocuită cu nodul curent, astfel încât proprietatea rămâne adevărată.

gol insert_case2 ( nodul struct * n ) { if ( n -> părinte -> culoare == NEGRU ) întoarcere ; /* Arborele este încă valabil */ altfel insert_case3 ( n ); } Notă: În următoarele cazuri, se presupune că N are un bunic G , deoarece părintele său P este roșu, iar dacă ar fi o rădăcină, ar fi colorat în negru. Astfel N are și un unchi U , deși poate fi un nod frunză în cazurile 4 și 5.

Cazul 3: Dacă ambii părinte P și unchiul U sunt roșii, atunci ambii pot fi recolorați în negru, iar bunicul G devine roșu (pentru a păstra proprietatea 5 (Toate căile de la orice nod dat la nodurile frunză conțin același număr de noduri negre)) . Acum nodul roșu actual N are un părinte negru. Deoarece orice cale prin părinte sau unchi trebuie să treacă prin bunic, numărul de noduri negre din aceste căi nu se va schimba. Cu toate acestea, bunicul lui G poate încălca acum proprietățile 2 (Rădăcina este neagră) sau 4 (Ambele copii ai fiecărui nod roșu sunt negri) (proprietatea 4 poate fi încălcată deoarece părintele lui G poate fi roșu). Pentru a remedia acest lucru, întreaga procedură este efectuată recursiv pe G din Cazul 1.

gol insert_case3 ( struct node * n ) { struct node * u = uncle ( n ), * g ; dacă (( u != NULL ) && ( u -> culoare == ROȘU )) { // && (n->parent->color == RED) A doua condiție este testată în insert_case2, adică părintele este deja roșu. n -> părinte -> culoare = NEGRU ; u -> culoare = NEGRU ; g = bunicul ( n ); g -> culoare = ROȘU ; insert_case1 ( g ); } altfel { insert_case4 ( n ); } } Notă: În cazurile rămase, părintele P se presupune a fi copilul stâng al strămoșului său. Dacă nu este cazul, trebuie să schimbați la stânga și la dreapta . Exemplele de cod se vor ocupa de asta.

Cazul 4: părintele lui P este roșu, dar unchiul lui U este negru. De asemenea, nodul curent N este copilul drept al lui P , iar P la rândul său este copilul stâng al strămoșului său G . În acest caz, se poate efectua o rotație de arbore, care schimbă rolurile nodului actual N și strămoșului său P . Apoi, pentru fostul nod părinte P din structura actualizată, utilizați cazul 5 deoarece Proprietatea 4 (Ambele copii ai oricărui nod roșu sunt negri) este încă încălcată. Rotația face ca unele căi (în subarborele etichetat „1” în diagramă) să treacă prin nodul N , ceea ce nu era cazul înainte. Acest lucru face ca unele căi (în subarborele etichetat „3”) să nu treacă prin nodul P. Cu toate acestea, ambele noduri sunt roșii, astfel încât Proprietatea 5 (Toate căile de la orice nod dat la nodurile frunză conțin același număr de noduri negre) nu este încălcată prin rotație. Cu toate acestea, proprietatea 4 este încă încălcată, dar acum problema se reduce la cazul 5.

gol insert_case4 ( struct node * n ) { struct node * g = bunicul ( n ); if (( n == n -> părinte -> dreapta ) && ( n -> părinte == g -> stânga )) { rotiți_stânga ( n -> părinte ); n = n -> stânga ; /* * rotate_left se poate face după cum urmează, având în vedere că există deja *g = grandparent(n) * * struct node *saved_p=g->left, *saved_left_n=n->left; * g->stânga=n; * n->left=saved_p; * saved_p->right=saved_left_n; * */ } else if (( n == n -> părinte -> stânga ) && ( n -> părinte == g -> dreapta )) { rotiți_dreapta ( n -> părinte ); n = n -> dreapta ; /* * rotate_right se poate face după cum urmează, având în vedere că există deja *g = grandparent(n) * * struct node *saved_p=g->right, *saved_right_n=n->right; *g->dreapta=n; * n->dreapta=salvat_p; * saved_p->left=saved_right_n; * */ } insert_case5 ( n ); }

Cazul 5: părintele P este roșu, dar unchiul U este negru, nodul curent N este copilul stâng al lui P și P este copilul stâng al lui G. În acest caz, arborele este rotit cu G . Rezultatul este un arbore în care fostul părinte P este acum părintele atât al nodului curent N , cât și al fostului bunic G . Se știe că G este negru, deoarece fostul său copil P nu ar putea fi altfel roșu (fără a încălca Proprietatea 4). Apoi culorile lui P și G se schimbă și, ca rezultat, arborele satisface Proprietatea 4 (Ambele copii ai oricărui nod roșu sunt negri). Proprietatea 5 (Toate căile de la orice nod dat la nodurile frunză conțin același număr de noduri negre) rămâne, de asemenea, adevărată, deoarece toate căile care trec prin oricare dintre aceste trei noduri au trecut anterior prin G , așa că acum toate trec prin P . În fiecare caz, dintre aceste trei noduri, doar unul este colorat în negru.

gol insert_case5 ( struct node * n ) { struct node * g = bunicul ( n ); n -> părinte -> culoare = NEGRU ; g -> culoare = ROȘU ; if (( n == n -> părinte -> stânga ) && ( n -> părinte == g -> stânga )) { rotiți_dreapta ( g ); } altfel { rotiți_stânga ( g ); } }

Eliminare

Când ștergem un nod cu doi copii non-frunze într-un arbore de căutare binar normal, căutăm fie cel mai mare element din subarborele din stânga, fie cel mai mic element din subarborele din dreapta și îi mutăm valoarea în nodul care urmează să fie eliminat. Îndepărtăm apoi nodul din care am copiat valoarea. Copierea unei valori de la un nod la altul nu încalcă proprietățile arborelui roșu-negru, deoarece structura arborelui și culorile nodurilor nu se schimbă. Este demn de remarcat faptul că noul nod care este îndepărtat nu poate avea două noduri copil fără frunză simultan, altfel nu va fi cel mai mare/mai mic element. Astfel, reiese că cazul ștergerii unui nod care are doi copii non-frunză se reduce la cazul ștergerii unui nod care conține cel mult un nod copil non-frunză. Prin urmare, descrierea ulterioară va pleca de la presupunerea că nodul de șters are cel mult un copil fără frunză.

Vom folosi notația M pentru nodul care trebuie eliminat; notăm cu C descendentul lui M , pe care îl vom numi și simplu „descendentul său”. Dacă M are un copil fără frunze, luați-l ca C . În caz contrar, pentru C luăm oricare dintre descendenții frunzelor.

Dacă M este un nod roșu, înlocuiți-l cu copilul nostru C , care prin definiție trebuie să fie negru. (Acest lucru se poate întâmpla numai atunci când M are doi copii frunze, deoarece dacă un nod roșu M are un copil negru fără frunză pe o parte și un copil frunză pe cealaltă parte, atunci numărul de noduri negre de pe ambele părți va fi diferit, astfel arborele va deveni invalid Arborele roșu-negru din cauza încălcării Proprietății 5.) Toate căile prin nodul care urmează să fie eliminat vor conține pur și simplu un nod roșu mai puțin, părintele și copilul nodului care urmează să fie eliminat trebuie să fie negre, deci Proprietatea 3 („Toate frunzele sunt negre”) și Proprietatea 4 („Ambele copii ai nodului roșu sunt negri”) sunt încă valabile.

Un alt caz simplu este când M este negru și C este roșu. Pur și simplu eliminarea unui nod negru ar încălca proprietatea 4 ("Ambele copii ai unui nod roșu sunt negri") și proprietatea 5 ("Orice cale simplă de la un nod dat la orice nod frunză conține același număr de noduri negre"), dar dacă am recolorează C negru, ambele proprietăți vor fi păstrate.

Un caz dificil este când atât M , cât și C sunt negre. (Acest lucru se poate întâmpla numai atunci când un nod negru care are doi copii frunze este îndepărtat, deoarece dacă un nod negru M are un copil negru fără frunză pe o parte și un copil frunză pe cealaltă, atunci numărul de noduri negre pe ambele părți va fi diferit și arborele va deveni un arbore roșu-negru invalid deoarece proprietatea 5 este încălcată.) Începem prin a înlocui nodul M cu copilul său C . Vom numi acest descendent (în noua sa poziție) N și „fratele” său (un alt descendent al noului său strămoș) - S. (Înainte de aceasta, S era „fratele” lui M .) În figurile de mai jos, vom folosi și notația P pentru noul strămoș al lui N (vechiul strămoș al lui M ), S L pentru copilul stâng al lui S , și S R pentru copilul drept al lui S ( S nu poate fi un nod frunză, deoarece dacă N din presupunerea noastră este negru, atunci subarborele P care conține N este de înălțimea doi negri și, prin urmare, celălalt subarborele lui P care conține S trebuie, de asemenea, fi negru de înălțimea doi, ceea ce nu poate fi cazul când S este o frunză) .

Notă : În unele cazuri, schimbăm rolurile și denumirile nodurilor, dar în fiecare caz, orice desemnare continuă să însemne același nod ca la începutul cazului. Orice culori descrise în figură sunt fie presupuse întâmplător, fie obținute din alte presupuneri. Albul înseamnă o culoare necunoscută (roșu sau negru).

Vom căuta un „frate” folosind această funcție:

nod struct * frate ( struct node * n ) { dacă ( n == n -> părinte -> stânga ) return n -> părinte -> dreapta ; altfel return n -> părinte -> stânga ; } Notă : Pentru ca arborele să rămână bine definit, avem nevoie ca fiecare frunză să rămână o frunză după toate transformările (astfel încât să nu aibă copii). Dacă nodul pe care îl eliminăm are un copil fără frunză N , este ușor de observat că proprietatea este valabilă. Pe de altă parte, dacă N este o frunză, atunci, după cum puteți vedea din imagini sau din cod, proprietatea deține și ea.

Putem efectua pașii de mai sus folosind următorul cod, unde funcția replace_nodeînlocuiește childun nod ndin arbore. Pentru comoditate, codul din această secțiune presupune că frunzele nule sunt reprezentate de obiecte nod reale, nu NULL (codul de inserare ar trebui să funcționeze cu aceeași reprezentare).

void replace_node ( nod * n , nod * copil ) { copil -> părinte = n -> părinte ; if ( n == n -> părinte -> stânga ) { n -> părinte -> stânga = copil ; } altfel { n -> părinte -> dreapta = copil ; } } gol delete_one_child ( struct node * n ) { /* * Condiție: n are cel mult un copil diferit de zero. */ struct node * child = is_leaf ( n -> right ) ? n -> stânga : n -> dreapta ; înlocui_nod ( n , copil ); if ( n -> culoare == NEGRU ) { dacă ( copil -> culoare == ROȘU ) copil -> culoare = NEGRU ; altfel delete_case1 ( copil ); } liber ( n ); } Notă : Dacă N este o frunză nulă și nu dorim să reprezentăm frunzele nule ca obiecte reale, putem modifica algoritmul apelând mai întâi delete_case1() pe părintele său (nodul pe care l-am șters nîn codul de mai sus) și ștergându-l după acea. Putem face acest lucru deoarece tatăl este negru și, prin urmare, se comportă ca o frunză nulă (și uneori este numit o frunză „fantomă”). Îl putem îndepărta în siguranță, deoarece nva rămâne o frunză după toate operațiunile, așa cum se arată mai sus.

Dacă N și tatăl său actual sunt negri, atunci eliminarea tatălui va face ca căile care trec prin N să aibă un nod negru mai puțin decât căile care nu trec prin el. Deoarece aceasta încalcă proprietatea 5 (toate căile de la orice nod la nodurile sale frunză conțin același număr de noduri negre), arborele trebuie reechilibrat. Există mai multe cazuri de luat în considerare:

Cazul 1: N este o nouă rădăcină. În acest caz, totul este făcut. Am eliminat un nod negru din fiecare cale, iar noua rădăcină este un nod negru, astfel încât proprietățile sunt păstrate.

gol delete_case1 ( struct node * n ) { dacă ( n -> părinte != NULL ) delete_case2 ( n ); } Notă : În cazurile 2, 5 și 6, presupunem că N este copilul stâng al strămoșului său P . Dacă este copilul potrivit, stânga și dreapta trebuie schimbate în toate cele trei cazuri. Din nou, exemplele de cod iau în considerare acest lucru.

Cazul 2: S este roșu. În acest caz, schimbăm culorile lui P și S și apoi facem o rotație la stânga în jurul lui P , făcând din S bunicul lui N. Rețineți că P trebuie să fie negru dacă are un copil roșu. Subarborele rezultat are încă un nod negru mai puțin, așa că nu am terminat încă cu asta. Acum N are un frate negru și un tată roșu, așa că putem trece la pașii 4, 5 sau 6. (Noul său frate este negru, deoarece a fost descendentul lui S roșu .)

În cele ce urmează, S va desemna noul frate N .

void delete_case2 ( struct node * n ) { struct node * s = frate ( n ); if ( s -> culoare == RED ) { n -> părinte -> culoare = ROȘU ; s -> culoare = NEGRU ; dacă ( n == n -> părinte -> stânga ) rotiți_stânga ( n -> părinte ); altfel rotiți_dreapta ( n -> părinte ); } delete_case3 ( n ); }

Cazul 3: copiii P , S și S sunt negri. În acest caz, pur și simplu recolorăm S roșu. Ca rezultat, toate căile prin S , dar nu prin N au un nod negru mai puțin. Deoarece eliminarea tatălui lui N face ca toate căile care trec prin N să conțină un nod negru mai puțin, astfel de acțiuni uniformizează echilibrul. Cu toate acestea, toate căile prin P conțin acum un nod negru mai puțin decât căile care nu trec prin P , astfel încât proprietatea 5 (toate căile de la orice vârf la nodurile sale frunză conțin același număr de noduri negre) este încă încălcată. Pentru a remedia acest lucru, aplicăm procedura de reechilibrare la P pornind de la cazul 1.

void delete_case3 ( struct node * n ) { struct node * s = frate ( n ); daca ( ( n -> părinte -> culoare == NEGRU ) && ( s -> culoare == NEGRU ) && ( s -> stânga -> culoare == NEGRU ) && ( s -> dreapta -> culoare == NEGRU ) ) { s -> culoare = ROȘU ; delete_case1 ( n -> părinte ); } altfel delete_case4 ( n ); }

Cazul 4: S și copiii lui sunt negri, dar P este roșu. În acest caz, pur și simplu schimbăm culorile lui S și P . Acest lucru nu afectează numărul de noduri negre de pe căile prin S , dar va adăuga unul la numărul de noduri negre de pe căile prin N , restabilind astfel influența nodului negru eliminat.

void delete_case4 ( struct node * n ) { struct node * s = frate ( n ); daca ( ( n -> părinte -> culoare == ROȘU ) && ( s -> culoare == NEGRU ) && ( s -> stânga -> culoare == NEGRU ) && ( s -> dreapta -> culoare == NEGRU ) ) { s -> culoare = ROȘU ; n -> părinte -> culoare = NEGRU ; } altfel delete_case5 ( n ); }

Cazul 5: S este negru, copilul stâng al lui S este roșu, copilul drept al lui S este negru și N este copilul stâng al tatălui său. În acest caz, rotim copacul spre dreapta în jurul lui S . Astfel, copilul stâng al lui S devine tatăl său și noul frate al lui N. După aceea, schimbăm culorile lui S și noului său tată. Toate căile conțin în continuare același număr de noduri negre, dar acum N are un frate negru cu un copil drept roșu și trecem la cazul 6. Nici N și nici tatăl său nu afectează această transformare. (Pentru cazul 6, notăm cu S noul frate al lui N. )

void delete_case5 ( struct node * n ) { struct node * s = frate ( n ); if ( s -> color == BLACK ) { /* this if declarația este banală, din cauza cazului 2 (chiar dacă cazul 2 a schimbat fratele în copilul unui frate, copilul fratelui nu poate fi roșu, deoarece niciun părinte roșu nu poate avea un copil roșu). */ /* următoarele afirmații forțează doar roșul să fie în stânga stângii părintelui sau în dreapta dreptei, astfel încât cazul șase se va roti corect. */ daca ( ( n == n -> părinte -> stânga ) && ( s -> dreapta -> culoare == NEGRU ) && ( s -> stânga -> culoare == ROȘU ) ) { /* și acest ultim test este banal din cauza cazurilor 2-4. */ s -> culoare = ROȘU ; s -> stânga -> culoare = NEGRU ; rotiți_dreapta ( s ); } altfel dacă ( ( n == n -> părinte -> dreapta ) && ( s -> stânga -> culoare == NEGRU ) && ( s -> dreapta -> culoare == ROȘU ) ) { /* și acest ultim test este banal din cauza cazurilor 2-4. */ s -> culoare = ROȘU ; s -> dreapta -> culoare = NEGRU ; rotiți_stânga ( s ); } } delete_case6 ( n ); }

Cazul 6: S este negru, copilul drept al lui S este roșu și N este copilul stâng al tatălui său P . În acest caz, rotim arborele la stânga în jurul lui P , după care S devine părintele lui P și copilul său drept. În continuare, schimbăm culorile lui P și S ( P ia culoarea lui S , S ia culoarea lui P ) și face copilul drept al lui S negru. Subarborele are în continuare aceeași culoare rădăcină, astfel încât proprietățile 4 (Ambele copii ai fiecărui nod roșu sunt negri) și 5 (toate căile de la orice vârf la nodurile sale frunze conțin același număr de noduri negre) nu sunt încălcate. Cu toate acestea, N are acum un strămoș negru suplimentar: fie P a devenit negru, fie a fost negru și S a fost adăugat ca bunic negru. Astfel, căile care trec prin N trec printr-un nod negru suplimentar.

Între timp, dacă calea nu trece prin N , atunci există 2 opțiuni posibile:

Trece prin noul frate N. Apoi, trebuie să treacă prin S și P , care tocmai au schimbat culorile și locurile. Prin urmare, calea conține același număr de noduri negre.
Trece prin noul unchi N , copilul drept al lui S . A trecut cândva prin S , tatăl lui S și copilul drept al lui S (care era roșu), dar acum trece doar prin S , care a căpătat culoarea fostului părinte, și copilul drept al lui S , care are a fost revopsită de la roșu la negru ( Presupunem că culoarea S : negru). Efectul este că această cale trece prin același număr de noduri negre.

În orice caz, numărul de noduri negre de pe aceste căi nu se va schimba. Prin urmare, am restaurat proprietățile 4 (Ambele copii ai fiecărui nod roșu sunt negri) și 5 (toate căile de la orice vârf la nodurile sale frunză conțin același număr de noduri negre). Nodul alb din diagramă poate fi roșu sau negru, dar trebuie să indice aceeași culoare atât la începutul cât și la sfârșitul transformării.

void delete_case6 ( struct node * n ) { struct node * s = frate ( n ); s -> culoare = n -> părinte -> culoare ; n -> părinte -> culoare = NEGRU ; if ( n == n -> părinte -> stânga ) { s -> dreapta -> culoare = NEGRU ; rotiți_stânga ( n -> părinte ); } altfel { s -> stânga -> culoare = NEGRU ; rotiți_dreapta ( n -> părinte ); } }

Toate apelurile de funcții recursive sunt înclinate și convertite în bucle, astfel încât algoritmul necesită memorie O(1) . În algoritmul de mai sus, toate cazurile sunt conectate pe rând, cu excepția cazului 3, în care poate apărea o revenire la cazul 1, care se aplică strămoșului nodului: acesta este singurul caz în care implementarea secvențială va fi o buclă eficientă (după un rotatie in cazul 3).

De asemenea, recursiunea de coadă nu apare niciodată pe nodurile copil, așa că o buclă de recursie de coadă se poate muta doar de la nodurile copil la părinții lor succesivi. Nu vor exista mai mult de O(log n ) călătorii dus-întors la cazul 1 (unde n este numărul total de noduri din arbore înainte de ștergere). Dacă are loc o rotație în cazul 2 (singura posibilă în ciclul cazurilor 1-3), atunci părintele nodului N devine roșu după rotație și ieșim din ciclu. Astfel, nu se va efectua mai mult de o rotație în timpul acestui ciclu. După ieșirea din buclă, vor exista cel mult două rotații suplimentare. În general, nu vor exista mai mult de trei rotații ale arborelui.

Comparație cu un arbore AVL echilibrat

Înălțimea copacului

Fie înălțimea arborelui h, numărul minim de vârfuri N. Atunci:

pentru arborele AVL . Deoarece , , N(h) crește ca șir Fibonacci , deci , unde $N(h)=N(h-1)+N(h-2)+1$ $N(0)=0$ $N(1)=1$ $N(h)=\Theta (\lambda ^{h})$ $\lambda =({\sqrt {5}}+1)/2\aproximativ 1,62$
pentru lemn roșu-negru $N(h)\geq 2^{{(h-1)/2}}=\Theta ({\sqrt {2}}^{h})$

Prin urmare, cu același număr de frunze, un copac roșu-negru poate fi mai mare decât un arbore AVL, dar nu mai mult de un factor de 1. [5] $\log \lambda /\log {\sqrt {2}}\aproximativ 1,388$

Caută

Întrucât arborele roșu-negru este, în cel mai rău caz, mai mare, căutarea în el este mai lentă, dar pierderea în timp nu depășește 39%.

Inserați

Inserarea necesită până la 2 ture în ambele tipuri de arbori. Cu toate acestea, datorită înălțimii mai mari a copacului roșu-negru, inserarea poate dura mai mult.

Eliminare

Îndepărtarea dintr-un arbore roșu-negru necesită până la 3 rotații, într-un arbore AVL poate necesita un număr de rotații până la adâncimea arborelui (până la rădăcină). Prin urmare, ștergerea dintr-un arbore roșu-negru este mai rapidă decât ștergerea dintr-un arbore AVL. Totuși, testele arată că arborii AVL sunt mai rapizi decât arborii roșu-negru în toate operațiunile [6] [7] , autorul ultimului test sugerând că arborii roșu-negru pot fi mai performanti cu cantități mari de memorie [8] .

Memorie

Arborele AVL de la fiecare nod stochează diferența de înălțime (un număr întreg de la -1 la +1, sunt necesari 2 biți pentru codificare). Arborele roșu-negru de la fiecare nod stochează o culoare (1 bit). Astfel, un copac roșu-negru poate fi mai economic. (Adevărat, având în vedere că în sistemele de calcul moderne, memoria este alocată în multipli de octeți, atunci arborii sunt exact la fel)

Cu toate acestea, în practică, ambele tipuri de arbori folosesc numere întregi, deoarece lucrul cu biți necesită calcule suplimentare ale procesorului (o instrucțiune de asamblare și %al 0x10000000). Cu toate acestea, există implementări ale arborelui roșu-negru care stochează valoarea culorii în biți. Un exemplu este Boost Multiindex . Scopul stocării culorii într-un pic este de a reduce consumul de memorie al arborelui roșu-negru ( Comprimarea nodului de indici ordonați ). Bitul de culoare din această implementare este stocat nu într-o variabilă separată, ci într-unul dintre pointerii nodului arborelui, transformându-l într-un pointer etichetat .

Dovada limitelor asimptotice

Un arbore roșu-negru care conține n noduri interne are o înălțime de . $O(log(n))$

Denumiri:

$h(v)$ este înălțimea subarborelui înrădăcinat la $v$
$bh(v)$ este numărul de noduri negre (fără numărare dacă este negru) de la orice frunză din subarborele (numită înălțimea neagră) $v$ $v$

Lema: Un subarbore înrădăcinat la un nod are cel puțin noduri interne. $v$ $2^{bh(v)}-1$

Dovada lemei (prin inductie pe inaltime):

Baza de inducție: . $h(v)=0$

Dacă subarborele are înălțimea zero, atunci trebuie să fie null , deci . $v$ $bh(''v'')=0$

Asa de:

2^{bh(v)}-1=2^{0}-1=1-1=0

Etapa de inducție: să fie un nod astfel încât subarborele să aibă și cel puțin noduri interne. Să arătăm că atunci , pentru care , are cel puțin noduri interne. $v$ $h(v)=k$ $2^{bh(v)}-1$
$v'$ $h(v')=k+1$ $2^{bh(v')}-1$

Deoarece are , este un nod intern. Ca atare, are doi copii, ambii fiind de culoare neagră , fie (în funcție de roșu sau negru). Prin ipoteza de inducție, fiecare descendent are cel puțin noduri interne și, prin urmare, are cel puțin $v'$ $h(v')>0$ $bh(v')$ $bh(v')-1$ $v'$
$2^{bh(v')-1}-1$ $v'$

2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1

nodurile interne.

Folosind această lemă, putem arăta că arborele are o înălțime logaritmică. Deoarece cel puțin jumătate dintre nodurile din orice cale de la rădăcină la frunză sunt negre (proprietatea 4 a arborelui roșu-negru), înălțimea neagră a rădăcinii este de cel puțin . După lemă avem: $h(rădăcină)/2$

n\geq 2^{{{h({\text{root))} \over 2}}}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\ text{rădăcină))) \over 2}\leftrightarrow \;h({\text{rădăcină)))\leq 2\log _{2}{(n+1)}.

Deci înălțimea rădăcinii este . $O(log(n))$

Vezi și

Profunzime prima căutare
Lățimea prima căutare
Copaci echilibrați (auto-echilibrați):

arborele AVL
arbore matrice
Arbore perfect echilibrat
arbore în expansiune
B+-copaci
2-3-copac
R-arborele
B*-copac

Lista structurilor de date (arbori)

Link -uri

Literatură

Kormen T., Leizerson C., Rivest R., Stein K. Algorithms: construction and analysis = Introduction to algorithms. - Ed. a II-a. - M . : Editura „Williams” , 2011. - S. 336-364. - ISBN 978-5-8459-0857-5 .

Note

↑ 1 2 structuri de date - De unde provine termenul „Arbore roșu/negru”? - Schimb de stivă de inginerie software . Preluat la 4 ianuarie 2019. Arhivat din original la 5 ianuarie 2019. (nedefinit)
↑ Curs „Algoritmi: Design și Analiză, Partea 1”, prelegere „Copaci roșu-negru” Arhivat 25 august 2014 la Wayback Machine (video 5:07 )
↑ Dr Dobbs - Arborele roșu-negru al lui STL
↑ Clasa TreeMap . Preluat la 13 martie 2015. Arhivat din original la 18 martie 2015. (nedefinit)
↑ în limita pentru un număr mare de frunze
↑ AVL vs RB Arhivat pe 11 iulie 2016 la Wayback Machine
↑ Red-Black versus AVL: benchmarks Arhivat 10 februarie 2015 la Wayback Machine
↑ AVL vs. Roșu-Negru: concluzia Arhivat la 10 februarie 2015 la Wayback Machine

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele segmentului
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree