UNIVERSITA TEA “TITU MAIORESCU ” DIN BUCUREȘTI FACULTA TEA DE INFORMA TICĂ LUCRARE DE LICENȚĂ RED -BLACK TREE Contents Red black tree – Introducere:… [627492]

UNIVERSITA TEA “TITU MAIORESCU ” DIN
BUCUREȘTI
FACULTA TEA DE INFORMA TICĂ
LUCRARE DE LICENȚĂ
RED -BLACK TREE

Contents
Red black tree – Introducere: ………………………….. ………………………….. ………………………….. …………………… 2
Red black tree – Inserarea ………………………….. ………………………….. ………………………….. ……………………….. 3
Red blac k tree – Stergerea: ………………………….. ………………………….. ………………………….. ……………………. 11
Red black tree – Comparare cu java.util.TreeMap: ………………………….. ………………………….. ……………….. 23
Red black tree – Bibliografie: ………………………….. ………………………….. ………………………….. …………………. 23

Introducere in lucrare
Red b lack tree – Introducere:
Arborii binary de cautare (BST binary search tree) sunt folosit i pentru a implementa tabele de
corespondenta , unde stocam un set de chei cu valori asociate. De asemenea, pute m implementa
seturi utilizând numai cheile fara sa mai stocam valori .
Cele mai multe dintre operațiunile BST (de exemplu, căutarea, max, min, inserare, ștergere etc.)
iau timpul O (h) unde h este înălțimea BST. Costul acestor operații poate deveni O (n) pentru un
arbore binar oblic. Dacă asigurăm că înălțimea arborerului rămâne O (Log n) după fiecare
inserare și ștergere, atunci putem garanta o limită superioară a lui O (Log n) pentru toate aceste
operații. Înălțimea unui red-black tree este întotdeauna O (Log n) unde n este numărul de noduri
din arbore.
Echili brarea copacului este necesară pentru a garanta o bună performanță, deoarece în caz
contrar arborele ar putea degenera într -o listă, de exemplu dacă introduce m chei deja sortate.
Avantajul arborilor de căutare asupra tabelelor de tip hash este că pute m traversa arborele
eficient în ordine de sortare.
AVL -tree sunt o altă variantă a arborilor de căutare binar echilibrați. Au fost popular i înainte de
a se cuno asțe red-black tree . AVL -tree sunt mai bine echilibrat i, cu o diferență de maxim unu
intre înălțimile subarboreului stâng și drept ( red-black tree garantează cel mult o diferenta de
doi). Principalul dezavantaj al AVL -tree fata de red black tree este că reechilibrarea necesită mai
mult efort.
Un red black tree este un arbore binar de căutare (BS T) cu un bit suplimentar de stocare per nod:
culoarea sa, care poate fi rosu sau negru. Fiecare nod conține câmpuri pentru culoare, cheie,

descendent stânga, descendent dreapta și parinte. Pointerii nil sunt vazuti ca ponteri pentru
nodurile externe (frunz e) și nodurile care au cheie sunt considerate noduri interne ale arborelui.

.
Un arbore binar de căutare este un red black tree dacă satisface următoarele proprietăți:
1) Fiecare nod are o culoare, rosie sau neagra .
2) Radacina este intodeauna de culoare neagra .
3) Nu există două noduri roșii adiacente (un nod roșu nu poate avea un părinte roșu sau un copil
roșu).
4) Fiecare cale de la un nod (inclusiv root) la oricare nod descendent NULL are același număr de
noduri negre.

Red black tree – Inserar ea :
Inserarea se face normal ca in orice BST. Apoi urmeaza niste operatii pentru a reechilibra
arborele . În arborele roșu-negru, folosim două instrumente pentru a face echilibrarea.
1) Recolorarea
2) Rotirea
Încercăm să recolorăm mai întâi, dacă recolorarea nu funcționează, atunci mergem pe
rotație. Mai jos este algoritmul detaliat. Algoritmii au în principal două cazuri, în funcție de
culoarea unchiului. Dacă unchiul este rosu, facem recolorarea. Dacă unchiul este negru , facem
rotații și / sau recolorări.
Culoarea unui nod NULL este considerată ca neagră.

Vom folosi urmatoarele notatii : x e nodul nou inserat, p e parintele lui x, u este unchiul lui x, iar
g este bunicul lui x.
1) Efectua m inserarea standard BST și transforma m culoarea nodurilor nou introduse ca rosu.
2) Dacă x este rădăcină, schimba m culoarea lui x ca negru (inălțimea neagră a arborelui complet
crește cu 1).
3) Facem urmaț orele dacă culoarea părintelui x nu este negru sau x nu este rădăcină.
a) Dacă unchiul lui x este rosu (bunicul trebuie să fi fost negru din proprietatea 4 )
(i) Modifica m culoarea părintelui și a unchiului ca negru .
(ii) culoarea bunicului devine rosu.
(iii) Schimba m bunicul x = x, repet am pașii 2 și 3 pentru noul x.
b) Dacă unchiul lui x este negru , atunci pot exista patru configurații pentru x, parintele
lui x ( p) si bunicul lui x (g)
i) cazul stânga stânga (p este copilul stang al lui g și x este copilul stang al lui p)
ii) cazul stânga dreapta (p este copilul stang al lui g și x este copilul drept al lui p)
iii) cazul dreapta dreapta (oglinda cazului i)
iv) cazul dreapt a stânga (oglindă a cazului ii)

Următoarele sunt operațiile care trebuie efectuate în cele patru subcategorii , atunci când unchiul
este negru .
Cele patru cazuri când unchiul este negru:
Cazul stânga stânga

Cazul stânga dreapta

Cazul dreapta dreapta (vezi g, p și x)

Cazul dreapta stânga (vezi g, p și x)

Algoritmul in pseudocod de echilibrare al red -black tree dupa insert este urmatorul:
RB-Insert -fixup (T,z)
while color[p[z]] = RED {
if p[z] == left[p[p[z]]] {
y = right[p[p[z]]]
if color[y] = RED {
color[p[z]] = BLACK
color[y] = BLACK
color[p[p[z]]] = RED
z = p[p[z]]
}
else {

if z = right[p[z]] {
z = p[z]
LEFT -Rotate(T,z)
}
color[p[z]] = BLACK
color[p[p[z]] ] = RED
RIGHT -Rotate(T,p[p[z]])
}
}
else {
y = left[p[p[z]]]
if color[y] = RED {
color[p[z]] = BLACK
color[y] = BLACK
color[p[p[z]]] = RED
z = p[p[z]]
}
else
{
if z = left[p[z]] {
z = p[z]
RIGHT -Rotate(T,z)
}
color[p[z]] = BLACK
color[p[p[z]]] = RED
LEFT -Rotate(T,p[p[z]])
}
}
color[root[T]] = BLACK
}

RIGHT -Rotate(T,x)
y = left[x] // y now points to node to left of x
left[x] = right[y] // y's right subtree becomes x's left subtree
p[right[y]] = x // right subtree of y gets a new parent
p[y] = p[x] // y's parent is now x's parent

// if x is at root then y becomes new root
if p[x] == nil[T] then root[T] = y
else
// if x is a left child then adjust x's parent's left child or…
if x == left[p[x]] then left[p[x]] = y

else
// adjust x's parent's right child
right[p[x]] = y
// the right child of y is now x
right[y] = x
// the parent of x is now y
p[x] = y

LEFT -Rotate(T,x)
y = right[x]
right[x] = left[y]
p[left[y]] = x
p[y] = p[x]
if p[x] == nil[T] then root[T] = y
else
if x == left[p[x]] then left[p[x]] = y
else
right[p[x]] = y
left[y] = x
p[x] = y

Mai jos e implementarea in JAVA:
package romeo.tree;

public class Node<Key extends Comparable<Key>, Value> {
Key key;
Value value ;
Node<Key, Value> left, right , parent ;
boolean isBlack = false ;

public Node(Key key, Value value , boolean isBlack , Node<Key, Value> parent ) {
this.key = key;
this.value = value ;
this.isBlack = isBlack ;
this.parent = parent ;
}

public Node(Key key, Value value , boolean isBlack ) {
this(key, value , isBlack , null);
}

@Override
public String toString() {
return "Node [key=" + key + ", isBlack=" + isBlack + "]";
}

}

public class RedBlackTree<Key extends Comparable<Key>, Value> {

Node<Key, Value> root;

public void set(Key key, Value value ) {
if (root == null) { //first case, root is null
root = new Node<>( key, value , true);
return ;
}
Node<Key, Value> node = root;
for (;;) {
int compare = key.compareTo( node .key);
if (compare < 0) {
if (node .left == null) {
node .left = new Node<>( key, value , false , node );
adjustAfterInsertion( node .left);
break ;
}
node = node .left;
} else if (compare > 0) {
if (node .right == null) {
node .right = new Node<>( key, value , false , node );
adjustAfterInsertion( node .right );
break ;
}
node = node .right ;
} else {
node .value = value ;
return ;
}
}

}

private void adjustAfterInsertion(Node<Key, Value> insertedNode ) {
for (;;) {
if (insertedNode == root) {
root.isBlack = true;
return ;
}
if (insertedNode .parent .isBlack ) {
return ;
}

if (insertedNode .parent == insertedNode .parent .parent .left) {
Node<Key, Value> uncle = insertedNode .parent .parent .right ;
if (uncle != null && ! uncle .isBlack ) {
insertedNode .parent .isBlack = true;
uncle .isBlack = true;
insertedNode = insertedNode .parent .parent ;
insertedNode .isBlack = false ;
continue ;
}
if (insertedNode .parent .right == insertedNode ) {
insertedNode = insertedNode .parent ;
rotateLeft( insertedNode );
}
insertedNode .parent .isBlack = true;
insertedNode .parent .parent .isBlack = false ;
rotateRigth( insertedNode .parent .parent );

} else {

Node<Key, Value> uncle = insertedNode .parent .parent .left;
if (uncle != null && ! uncle .isBlack ) {
insertedNode .parent .isBlack = true;
uncle .isBlack = true;
insertedNode = insertedNode .parent .parent ;
insertedNode .isBlack = false ;
continue ;
}
if (insertedNode .parent .left == insertedNode ) {
insertedNode = insertedNode .parent ;
rotateRigth( insertedNode );
}
insertedNode .parent .isBlack = true;
insertedNode .parent .parent .isBlack = false ;
rotateLeft( insertedNode .parent .parent );

}
}

}

private void rotateLeft(Node<Key, Value> node ) {
Node<Key, Value> rigthChild = node .right ;
node .right = rigthChild .left;
if (rigthChild .left != null) {
rigthChild .left.parent = node ;
}

rigthChild .parent = node .parent ;
if (root == node ) {
root = rigthChild ;
} else {
if (node == node .parent .left) {
node .parent .left = rigthChild ;
} else {
node .parent .right = rigthChild ;
}
}
rigthChild .left = node ;
node .parent = rigthChild ;

}

private void rotateRigth(Node<Key, Value> node ) {
Node<Key, Value> leftChild = node .left;
node .left = leftChild .right ;
if (leftChild .right != null) {
leftChild .right .parent = node ;
}
leftChild .parent = node .parent ;
if (root == node ) {
root = leftChild ;
} else {
if (node == node .parent .left) {
node .parent .left = leftChild ;
} else {
node .parent .right = leftChild ;
}
}
leftChild .right = node ;
node .parent = leftChild ;

}
}

Red black tree – Stergerea:
La fel ca la inserare, si la stergere recolorarea și rotațiile sunt folosite pentru a menține
proprietățile red-black tree. În operația de inserare, verificăm culoarea unchiului pentru a decide

cazul potrivit. În operația de ștergere, verificăm culoarea fratelui pentru a decide cazul potrivit.
Proprietatea principală care se încalcă după inserare este două roși i consecutive (proprietatea 3).
În ștergere, proprietatea principală încălcată este schimbarea înălțimii negre în subarbori ,
deoarece ștergerea unui nod negru poate determina o înălțime neagră redusă într -o singură cale
de la rădăcină la frunze .
Ștergerea este un proces destul de complex. Pentru a înțelege ștergerea, se folosește noțiunea de
dublu negru. Atunci când un nod negru este șters și înlocuit de un copil negru, copilul este
marcat ca dublu negru. Sarcina principală devine acum convertirea acestui dublu negru în negru
simplu .
Etape de ștergere
Urmează pași detaliați pentru ștergere.
1) Efectua m ștergerea standard BST. Când executăm operația de ștergere standard în BST,
întotdeauna terminăm ștergerea unui nod care este fie frunză, fie are doar un singur copil (Pentru
un nod intern, copiem succesorul și apoi apelam recursiv ștergerea succesorului, succesorul este
întotdeauna un nod frunz a sau un nod cu un copil). Deci, avem nevoie doar de tratarea cazurilor
în care un nod este frunz a sau are un copil. Fie v nodul care trebuie șters și u este copilul care
înlocuiește v (u este NULL când v este o frunză și culoarea NULL este considerată negru).
2) Cazul simplu: dacă u sau v este roșu, notăm copilul înlocuit ca negru (nu se schimbă
înălțimea neagră). Nodurile u și v nu pot fi simultan roșii, deoarece v este parinte le lui u și două
noduri rosii consecutive nu sunt permise în red-black tree.

3) Dacă ambele u și v sunt negre .

3.1) Culoarea u ca dublu negru. Acum sarcina noastră se reduce pentru a converti acest negru
dublu la negru unic. Dacă v este frunza, atunci u este NULL și culoarea NULL este considerată
negru. Deci, ștergerea unei frunze negre provoacă de asemenea un dublu negru.

3.2) Facem urmatoarele cat timp nodul curent u este dublu negru și nu este rădăcină. Nodul s este
fratele nodului u.
(a): Dacă fratele este negru și cel puțin unul dintre copiii fratelui este roșu efectu am
rotația (rotirile). Nodul r este copilul lui s. Acest caz poate fi împărțit în patru subcategorii în
funcție de pozițiile lui s și r.
(i) Cazul stânga stânga (s este copilul din stanga si r este copilul din stanga al lui s
sau ambii copii ai lui s sunt roșii). Acesta este cazul in oglinda al cazului dreapta dreapta
prezentat în diagrama de mai jos.
(ii) Cazul stânga dreapt a (s este copilul din stanga și r este copil ul din
dreapta ).Acesta este cazul in oglinda al cazului dreapta stânga prezentat în diagrama de
mai jos.
(iii) Cazul dreapta dreapta (s este copilul drept și r este copilul drept al lui s sau
ambii copii ai lui s sunt roșii)

(iv) Cazul dreapta stânga (s este copilul drept al părintelui său și r este copilu l
stang al lui s)

(b): Dacă fratele este negru și ambii copii sunt negri i efectua m recolorarea și repeta m
pentru părinte dacă părintele este negru.

În acest caz, dacă părintele a fost roșu, atunci nu mai e nevoie să reapelam pentru p, putem pur și
simplu să îl facem negru (roșu + dublu negru = negru simplu )
(c): Dacă fratele este roșu, efectua m o rotație pentru a muta vechiul frate, recolor ăm
vechiul frate și părinte. Noul frate este mereu negru (vezi diagrama de mai jos). Aceasta
transformă în principal arborele în cazul fratelui negru (prin rotire) și duce la cazul (a) sau
(b). Acest caz poate fi împărțit în două subcategorii.
(i) Cazul stânga (s este copilul din stang a). Aceast caz este oglinda cazului drept
prezentat în diagrama de mai jos. Rotim dreapta părintele p.

(iii) Cazul dreapta (s este copilul din dreapta ). Rotim părintele p in stanga .

3.3) Dacă u este rădăcină, o facem negru simplu (înălțimea neagra a arborelui complet se reduce
cu 1).
Algoritmul in pseudocod :
RB-DELETE(T, z)
if left[z] = nil[T] or right[z] = nil[T]
then y ← z
else y ← TREE -SUCCESSOR(z)
if left[y] ≠ nil[T]
then x ← left[y]
else x ← right[y]
p[x] ← p[y]
if p[y] = nil[T]
then root[T] ← x
else if y = left[p[y]]

then left[p[y]] ← x
else right[p[y]] ← x
if y != z
then key[z] ← key[y]
copy y's satellite data into z
if color[y] = BLACK
then RB -DELETE -FIXUP(T, x)
return y

TREE -SUCCESSOR(x)
if right[x] ≠ NIL
then return TREE -MINIMUM (right[x])
y ← p[x]
while y ≠ NIL and x = right[y]
do
x ← y
y ← p[y]
return y

TREE -MINIMUM (x)
while left[x] ≠ NIL
do x ← left[x]
return x

RB-DELETE -FIXUP(T, x)
1 while x ≠ root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w ← right[p[x]]
4 if color[w] = RED
5 then color[w] ← BLACK ▹ Case 1

6 color[p[x]] ← RED ▹ Case 1
7 LEFT -ROTATE(T, p[x]) ▹ Case 1
8 w ← right[p[x]] ▹ Case 1
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ▹ Case 2
11 x p[x] ▹ Case 2
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ▹ Case 3
14 color[w] ← RED ▹ Case 3
15 R IGHT -ROTATE(T, w) ▹ Case 3
16 w ← right[p[x]] ▹ Case 3
17 color[w] ← color[p[x]] ▹ Case 4
18 color[p[x]] ← BLACK ▹ Case 4
19 color[right[w]] ← BLACK ▹ Case 4
20 LEFT -ROTATE(T, p[x]) ▹ Case 4
21 x ← root[T] ▹ Case 4
22 else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK
Algoritmul in JAVA :
private Node<Key, Value> delete(Node<Key, Value> node ) {
Node<Key, Value> y;
if (node .left == null || node .right == null) {
y = node ;
} else {
y = getSuccesor( node );
}

Node<Key, Value> x;
if (y.left != null) {
x = y.left;

} else {
x = y.right ;
}
if (x != null) {
x.parent = y.parent ;
}
Node<Key, Value> xParent = y.parent ;

boolean yIsLeft = false ;
if (y.parent == null) {
root = x;
} else if (y == y.parent .left) {
y.parent .left = x;
yIsLeft = true;
} else {
y.parent .right = x;
yIsLeft = false ;
}

if (y != node ) {
node .key = y.key;
}

if (y.isBlack && x != null) {
deleteFixUp( x, xParent , yIsLeft );
}

return y;
}

private Node<Key, Value> getSuccesor( Node<Key, Value> node ) {
if (node .right != null) {
return treeMinimum( node .right );
}
Node<Key, Value> y = node .parent ;
while (y != null && node == y.right ) {
node = y;
y = y.parent ;
}
return y;
}

private Node<Key, Value> treeMinimum(Node<Key, Value> node ) {
while (node .left != null) {
node = node .left;
}
return node ;
}

private void deleteFixUp(Node<Key, Value> node , Node<Key, Value> nodeParent ,
boolean nodeIsLeft ) {
while (node != root && isBlack( node )) {
Node<Key, Value> w;
if (nodeIsLeft ) {
w = nodeParent .right ;
if (!isBlack( w)) {
w.isBlack = true;
nodeParent .isBlack = false ;
rotateLeft( nodeParent );

w = nodeParent .right ;
}

if (isBlack( w.left) && isBlack( w.right )) {
w.isBlack = false ;
//System.out.println("Node=" + node);
node = nodeParent ;
nodeParent = node .parent ;
nodeIsLeft = (nodeParent == null || node == nodeParent .left);
} else {
if (isBlack( w.right )) {
w.left.isBlack = true;
w.isBlack = false ;
rotateRigth( w);
w = nodeParent .right ;
}

w.isBlack = nodeParent .isBlack ;
nodeParent .isBlack = true;
if (w.right != null) {
w.right .isBlack = true;
}
rotateLeft( nodeParent );
node = root;
nodeParent = null;
}
} else { /* nodeIsLeft == false */
w = nodeParent .left;
if (!isBlack( w)) {
w.isBlack = true;
nodeParent .isBlack = false ;

rotateRigth( nodeParent );
w = nodeParent .left;
}

if (isBlack( w.right ) && isBlack( w.left)) {
w.isBlack = false ;
node = nodeParent ;
nodeParent = node .parent ;
nodeIsLeft = (nodeParent == null || node == nodeParent .left);
} else {
if (isBlack( w.left)) {
w.right .isBlack = true;
w.isBlack = false ;
rotateLeft( w);
w = nodeParent .left;
}

w.isBlack = nodeParent .isBlack ;
nodeParent .isBlack = true;
if (w.left != null) {
w.left.isBlack = true;
}
rotateRigth( nodeParent );//xx
node = root;
nodeParent = null;
}
}
}

node .isBlack = true;
}

Red black tree – Comparare cu
java.util. TreeMap:

Concluzii
Red black tree – Bibliografie:
* [Pearson] – Algorithms, 4th ed. – [Sedgewick, Wayne]
* https://www.andrew.cmu.edu/user/mm6/95 –
771/examples/RedBlackTreeProject/dist/javadoc/redblacktreeproject/RedBlackTree.html
* http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap14.htm
* https://www.geeksforgeeks.org/red -black -tree-set-2-insert/
* https://stackoverflow.com/questions/6723488/red -black -tree-deletion -algorithm