roșu negru copac rotații și culoare răstoarnă

Thamindu Dilshan Jayawickrama
Thamindu Dilshan Jayawickrama

urmați

11 iulie 2020 · 6 min citire

un arbore de căutare tipic, cum ar fi arborele de căutare binar (BST), ar putea rula într-o înălțime de o(n), ceea ce ar putea duce la complexitatea în cel mai rău caz pentru operațiuni de bază, cum ar fi Căutarea, inserarea, ștergerea etc. Acest lucru depinde în întregime de ordinea elementelor care sunt inserate în BST. Dar, există anumite situații în care nu avem întregul set de elemente atunci când începem să construim arborele. Aici intră în joc copacii de căutare echilibrați. Într-un arbore de căutare echilibrat, o înălțime de O(log n) este garantată atunci când se implementează un set dinamic de n elemente. Copacii roșu-negru, copacii AVL, copacii 2-3 și copacii B sunt câteva dintre exemplele pentru implementările echilibrate ale copacilor de căutare. Acest articol este totul despre operațiunile de modificare copac implicate cu copaci roșu-negru.

un copac roșu-negru (RB-Tree) este un arbore de căutare binar de auto-echilibrare în care fiecare nod urmează un set de reguli. Fiecare nod dintr-un arbore RB are un atribut suplimentar; culoarea, care ar putea fi roșie sau neagră. Într-o implementare tipică RB-Tree, va exista un set de noduri santinelă pentru a semnala că este atins un nod de frunze. Aceste noduri sunt denumite NULLs (sau NILs) și considerate ca noduri de frunze în acest articol. Mai jos sunt setul de reguli sau proprietățile pe care fiecare nod ar trebui să le urmeze.

  1. fiecare nod este roșu sau negru.

2. Rădăcina și frunzele sunt negre.

3. Dacă un nod este roșu, atunci părintele său este negru.

4. Toate căile simple de la orice nod la o frunză descendentă au același număr de noduri negre (Negru-înălțime).

înălțimea unui arbore RB rămâne la o(log n) după fiecare operație de modificare a arborelui care a dus la o limită superioară garantată de o(log n) pentru acele operațiuni. Operațiile Inserare și ștergere provoacă modificări ale arborelui RB. După fiecare operație de modificare a arborelui, arborele va fi auto-echilibrat prin schimbări de culoare și rotații. Înainte de a intra în aceste operațiuni, ar trebui să fim familiarizați cu următoarea notație.

o rotație este o operație specială concepută pentru auto-echilibrarea arborilor binari de căutare care poate fi efectuată în o(1) timp. O proprietate interesantă pe rotații este că păstrează traversarea inorder a cheilor (ordonarea cheilor).

decizia de a efectua o rotație sau o schimbare de culoare se bazează pe Mătușa nodului considerat (nodul curent). Dacă nodul are o mătușă neagră, facem o rotație. Dacă nodul are o mătușă roșie, facem un flip de culoare. După efectuarea unei rotații, ar trebui să fixăm culoarea copacului. După efectuarea acestor operații, arborele ar trebui să fie încheiat ca mai jos.

dacă nodul curent este copilul stâng al copilului stâng al bunicului său, rotim dreapta bunicul în jurul părintelui. Dacă nodul curent este copilul drept al copilului drept al bunicului său, am lăsat rotiți bunicul în jurul părintelui. Dacă nodul curent este copilul drept al copilului stâng al bunicului său, efectuăm o rotație Stânga-dreapta unde rotim bunicul și copilul în jurul părintelui. Dacă nodul curent este copilul stâng al copilului drept al bunicului său, efectuăm o rotație dreapta-stânga unde rotim bunicul și copilul în jurul părintelui. Toate rotațiile pot fi rezumate în diagrama de mai jos.

un fapt important de reținut este că, după efectuarea oricărei operații de modificare a arborelui, ar trebui să validați arborele împotriva setului de reguli pentru a afla dacă există încălcări. Dacă există o încălcare (ex: rădăcina este roșie), ar trebui să o corectați. Acum să construim un simplu RB-copac prin introducerea de mai jos set de chei. Rețineți că, pentru simplitate, nodurile de frunze (NULL) sunt ignorate în diagramele de mai jos.

5, 8, 1, 10, 9, 15, 20

ar trebui să inserăm fiecare cheie ca un nod roșu. Prin urmare, inserăm 5 ca un nod roșu și imediat îl colorăm înapoi la negru, deoarece este nodul rădăcină. Apoi introducem 8 ca copil drept al nodului 5. urmăm proprietatea BST de bază atunci când introducem chei. Inserarea 1 este aceeași cu inserarea 8.

apoi, ar trebui să inserăm 10 ca copilul drept al lui 8. Îl introducem ca un nod roșu și verificăm încălcările. Ambele 8 și 10 sunt noduri roșii și încalcă proprietatea a 3-a. Ar trebui să căutăm mătușa și e roșie. Așa că facem un flip de culoare. După flip-ul de culoare, putem vedea că nodul rădăcină este roșu și încalcă proprietatea 2nd. Așa că o rezolvăm schimbând culoarea nodului rădăcină.

apoi, ar trebui să introducem cheia 9. După inserare, putem vedea că ambele noduri 9 și 10 sunt roșii și încalcă proprietatea 2nd. Verificăm mătușa și, deoarece este negru (NULL-urile sunt negre), efectuăm o rotație dreapta-stânga (încălcarea este în subarborele stâng al copilului drept). După rotație, ar trebui să facem o remediere a culorii.

acum să introducem cheia 15. După inserare, putem vedea că există două noduri roșii consecutive, iar mătușa celor 15 este un nod roșu. Deci, ar trebui să facem un flip de culoare. După aceea, verificăm orice încălcare și putem afla că nu există încălcări.

acum să introducem cheia 20 în copac. După inserare, putem vedea că mătușa este neagră și, prin urmare, ar trebui să efectuăm o rotație la stânga (încălcarea este în subarborele drept al copilului drept). După rotație, ar trebui să facem o remediere a culorii.

în acest articol, ne-am uitat într-un anumit arbore de căutare binar de auto-echilibrare; copac roșu-negru. Acestea sunt garantate a avea o înălțime de O(log n), prin urmare, având o complexitate de timp în cel mai rău caz de O(log n) pentru operațiunile de bază ale arborelui. Copacii roșu-negru sunt deosebit de utili în multe aplicații de informatică. C++ Standard Template Library (STL) a stabilit, MultiSet, hartă, și multimap bazate pe RB-copaci. De asemenea, TreeMap în limbajul Java este o implementare NavigableMap bazată pe RB-Tree.

Lasă un răspuns

Adresa ta de email nu va fi publicată.