În postul anterior, am discutat despre introducerea la Arborele Roșu-Negru. În această postare, se discută despre inserție. În inserția arborelui AVL, am folosit rotația ca instrument pentru a face echilibrarea după inserție. În arborele Red-Black, folosim două instrumente pentru a face echilibrarea.
- Recolorare
- Rotație
Recolorarea este schimbarea culorii nodului, adică dacă este roșu, atunci îl transformăm în negru și viceversa. Trebuie remarcat faptul că culoarea nodului NULL este întotdeauna neagră. În plus, întotdeauna încercăm mai întâi recolorarea, iar dacă aceasta nu funcționează, atunci se trece la rotație. În continuare este prezentat un algoritm detaliat. Algoritmii au în principal două cazuri, în funcție de culoarea unchiului. Dacă unchiul este roșu, procedăm la recolorare. Dacă unchiul este negru, facem rotații și/sau recolorări.
Reprezentarea cu care vom lucra este:
Această reprezentare se bazează pe X
Logică:
În primul rând, trebuie să inserăm nodul în mod similar cu cel dintr-un arbore binar și să-i atribuim o culoare roșie. Acum, dacă nodul este un nod rădăcină, atunci schimbați-i culoarea în negru, dar dacă nu este așa, atunci verificați culoarea nodului părinte. În cazul în care culoarea sa este neagră, atunci nu se schimbă culoarea, dar dacă nu este neagră, adică este roșie, atunci se verifică culoarea unchiului nodului. În cazul în care unchiul nodului are culoarea roșie, se schimbă culoarea părintelui și a unchiului nodului în negru, iar cea a bunicului în roșu și se repetă același proces pentru el (adică bunicul).
Dar, dacă unchiul nodului are culoarea neagră, atunci există 4 cazuri posibile:
- Cazul Stânga Stânga (LL rotation):
- Cazul Stânga Dreapta (LR rotation):
- Cazul dreapta-dreapta (rotație RR):
- Cazul dreapta-stânga (rotație RL):
Acum, după aceste rotații, dacă culorile nodurilor nu se potrivesc, atunci recolorați-le.
Algoritm:
Să fie x nodul nou inserat.
- Executați inserția standard BST și schimbați culoarea nodurilor nou inserate în ROȘU.
- Dacă x este rădăcina, schimbați culoarea lui x în NEGRU (Înălțimea neagră a arborelui complet crește cu 1).
- Faceți următoarele dacă culoarea părintelui lui x nu este NEGRU și x nu este rădăcina.
a) Dacă unchiul lui x este ROȘU (Bunicul trebuie să fi fost negru din proprietatea 4)
(i) Schimbați culoarea părintelui și a unchiului ca fiind NEGRU.
(ii) Culoarea unui bunic ca fiind ROȘU.
(iii) Schimbați x = bunicul lui x, repetați pașii 2 și 3 pentru noul x.b) Dacă unchiul lui x este NEGRU, atunci pot exista patru configurații pentru x, părintele lui x (p) și bunicul lui x (g) (acest lucru este similar cu arborele AVL)
(i) Cazul stâng stânga (p este copilul stâng al lui g și x este copilul stâng al lui p)
(ii) Cazul stâng dreapta (p este (p este copilul stâng al lui g și x este copilul drept al lui p)
(iii) Right Right Case (Oglinda cazului i)
(iv) Right Left Case (Oglinda cazului ii)
Exemplu: Crearea unui arbore roșu-negru cu elementele 3, 21, 32 și 17 într-un arbore gol.
Soluție:
Când este inserat primul element, acesta este inserat ca nod rădăcină și, deoarece nodul rădăcină are culoarea neagră, dobândește culoarea neagră.
Noul element este întotdeauna inserat cu culoarea roșie și, deoarece 21 > 3, devine parte a subarborelui drept al nodului rădăcină.
Acum, când inserăm 32 vedem că există o pereche tată-copil roșie care încalcă regula arborelui roșu-negru, așa că trebuie să o rotim. Mai mult decât atât, observăm condițiile de rotație RR (considerând nodul nul al nodului rădăcină ca fiind negru), astfel încât, după rotație, deoarece nodul rădăcină nu poate fi roșu, trebuie să efectuăm o recolorare a arborelui, rezultând arborele prezentat mai sus.
Acum, atunci când inserăm noul element, nodul părinte și nodul copil de culoare roșie apar din nou și aici trebuie să le recolorăm. Vedem că atât nodul părinte, cât și nodul unchi au culoarea roșie, așa că pur și simplu le schimbăm culoarea în negru și schimbăm culoarea bunicului în roșu. Acum, cum bunicul este nodul rădăcină, îi schimbăm din nou culoarea în negru, rezultând astfel arborele prezentat mai sus.
Structura finală a arborelui:
Arborele final va arăta astfel
Vă rugăm să consultați Programul C pentru Inserarea Arborelui Roșu-Negru pentru implementarea completă a algoritmului de mai sus.
Arborele Roșu-Negru | Set 3 (Ștergere)