1- Ogni nodo è rosso o nero
2- La radice è nera
3- Tutte le foglie sono nere (puntatori nulli sono considerati neri)
4- Entrambi i figli di un nodo rosso sono neri
5- Tutti i cammini che vanno da un nodo qualsiasi ad una delle foglie contengono lo stesso numero di nodi neri
Per il resto, condivide tutte le caratteristiche che contraddistinguono gli alberi binari di ricerca, compreso il tempo di esecuzione di molte operazioni eseguite sull'albero.
La maggior parte di queste operazioni è identica a quelle eseguite sugli alberi binari di ricerca. Inserimento ed eliminazione di un nodo, però, richiedono un lavoro extra per mantenere inalterate le proprietà degli alberi rosso-neri.
Evitando volutamente i dettagli (che si rivelano abbastanza tediosi; ci sono libri e risorse a volontà sull'argomento), ritengo più utile affrontare brevemente la questione della conservazione delle proprietà dell'albero come conseguenza di un'eliminazione (l'inserimento non comporta particolari difficoltà).
Il metodo di eliminazione è simile a quello implementato per gli alberi binari di ricerca. Quindi se un nodo da eliminare ha un solo figlio, questo prenderà il suo posto. Se ha due figli, il suo successore prenderà il suo posto. I problemi con le proprietà dell'albero nascono se il nodo da eliminare è nero con un solo figlio oppure (indipendentemente da suo colore) ha due figli ed il successore è nero. Nel primo caso si può avere una violazione della proprietà 2 (se il nodo da eliminare è la radice ed il figlio è rosso; la radice diventerebbe rossa) o della proprietà 4 (se il padre ed il figlio del nodo da eliminare sono rossi; si avrebbero due nodi rossi consecutivi). Nel secondo caso si può avere una violazione della proprietà 5 in quanto lo spostamento del nodo nero potrebbe compromettere uno dei cammini che lo attraversano.
Come si ripristinano le proprietà? L'algoritmo prevede scambi di colore e rotazioni tra nodi quando riconosce una determinata disposizione di alcuni nodi specifici a partire dal nodo che prende il posto di quello eliminato (primo caso) o dal nodo che prende il posto del successore (secondo caso).
/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono una maggiore semplificazione.*/ #include <stdio.h> struct Node { int val; struct Node *parent; struct Node *left; struct Node *right; bool black; }; void bst_walk(Node*); Node* bst_search(Node*, int); Node* bst_min(Node*); Node* bst_max(Node*); Node* bst_successor(Node*); Node* bst_predeccessor(Node*); void transplant(Node*&, Node*, Node*); void left_rotate(Node*&, Node&); void right_rotate(Node*&, Node&); void rb_insert(Node*&, Node&); void rb_insert_fixup(Node*&, Node*&); void rb_delete(Node*&, Node&); void rb_delete_fixup(Node*&, Node*&); int main(int argc, char *argv[], char *envp[]) { Node n12 = { 12, nullptr, nullptr, nullptr, false }; Node *root = nullptr; rb_insert(root, n12); Node n5 = { 5, nullptr, nullptr, nullptr, false }; Node n9 = { 9, nullptr, nullptr, nullptr, false }; Node n2 = { 2, nullptr, nullptr, nullptr, false }; Node n18 = { 18, nullptr, nullptr, nullptr, false }; Node n13 = { 13, nullptr, nullptr, nullptr, false }; Node n17 = { 17, nullptr, nullptr, nullptr, false }; Node n19 = { 19, nullptr, nullptr, nullptr, false }; Node n15 = { 15, nullptr, nullptr, nullptr, false }; rb_insert(root, n5); rb_insert(root, n9); rb_insert(root, n2); rb_insert(root, n18); rb_insert(root, n13); rb_insert(root, n17); rb_insert(root, n19); rb_insert(root, n15); bst_walk(root); printf("\n"); printf("Max elemento: %d\n", bst_max(root)->val); printf("Min elemento: %d\n", bst_min(root)->val); printf("Successore di %d: %d\n", n5.val, bst_successor(&n5)->val); printf("Predeccessore di %d: %d\n", n5.val, bst_predeccessor(&n5)->val); if (Node *n = bst_search(root, 18)) printf("L'elemento %d è nell'albero binario di ricerca!\n", n->val); else printf("L'elemento non è nell'albero binario di ricerca!\n", n->val); rb_delete(root, n9); rb_delete(root, n17); rb_delete(root, n5); rb_delete(root, n13); bst_walk(root); printf("\n"); return 0; } // Nodo n diventa figlio sinistro del figlio destro di n void left_rotate(Node *&root, Node &n) { Node *nt = n.right; n.right = nt->left; if (nt->left != nullptr) nt->left->parent = &n; nt->parent = n.parent; if (n.parent == nullptr) root = nt; else if (&n == n.parent->left) n.parent->left = nt; else n.parent->right = nt; nt->left = &n; n.parent = nt; } // Nodo n diventa figlio destro del figlio sinistro di n void right_rotate(Node *&root, Node &n) { Node *nt = n.left; n.left = nt->right; if (nt->right != nullptr) nt->right->parent = &n; nt->parent = n.parent; if (n.parent == nullptr) root = nt; else if (&n == n.parent->right) n.parent->right = nt; else n.parent->left = nt; nt->right = &n; n.parent = nt; } void rb_insert(Node *&root, Node &n) { Node *nt = nullptr; Node *nroot = root; // Scorre fino a trovare dove poter inserire il nodo // rispettando proprietà degli alberi binari di ricerca while (nroot != nullptr) { nt = nroot; if (n.val < nroot->val) nroot = nroot->left; else nroot = nroot->right; } // Padre del nuovo nodo impostato a ultimo nodo valido trovato in while n.parent = nt; if (nt == nullptr) // Se nt è null allora albero era vuoto root = &n; else if (n.val < nt->val) nt->left = &n; // Imposta nuovo nodo come figlio sinistro di ultimo nodo valido trovato in while else nt->right = &n; // Imposta nuovo nodo come figlio sinistro di ultimo nodo valido trovato in while // Ma se un nodo viene prima cancellato e poi reinserito è necessario "annullare" i suoi figli n.left = nullptr; n.right = nullptr; // Maggior parte dei nodi inseriti sono rossi. // Ripristina proprietà alberi RB Node *ntp = &n; rb_insert_fixup(root, ntp); } void rb_insert_fixup(Node *&root, Node *&n) { // Itera finchè non trova un nodo padre non rosso while (n->parent && !n->parent->black) { // Se padre di n == figlio sinistro di padre di padre di n if (n->parent->parent && n->parent == n->parent->parent->left) { // Imposta lo zio di n Node *nt = n->parent->parent->right; // Se zio è rosso if (nt && !nt->black) { // caso 1 n->parent->black = true; nt->black = true; n->parent->parent->black = false; n = n->parent->parent; } else { // Se zio è nero ed n è figlio destro di padre di n if (n == n->parent->right) { // caso 2 n = n->parent; left_rotate(root, *n); } // Se zio è nero ma n è figlio sinistro // caso 3 n->parent->black = true; n->parent->parent->black = false; right_rotate(root, *n->parent->parent); } } else // Se invece padre di n == figlio destro di padre di padre di n, esegue le stesse operazioni ma in modo simmetrico { Node *nt = n->parent->parent->left; if (nt && !nt->black) { n->parent->black = true; nt->black = true; n->parent->parent->black = false; n = n->parent->parent; } else { if (n == n->parent->left) { n = n->parent; right_rotate(root, *n); } n->parent->black = true; n->parent->parent->black = false; left_rotate(root, *n->parent->parent); } } } root->black = true; } void transplant(Node *&root, Node *oldn, Node *newn) { if (oldn->parent == nullptr) root = newn; // oldn è radice dell'albero else if (oldn == oldn->parent->left) oldn->parent->left = newn; // oldn si trova nel sottoalbero sinistro di suo padre else oldn->parent->right = newn; // oldn si trova nel sottoalbero sinistro di suo padre if (newn != nullptr) newn->parent = oldn->parent; // imposta padre di newn a padre di oldn } void rb_delete(Node *&root, Node &n) { // Tiene traccia del nodo rimosso o del successore di n (in caso n abbia entrambi i figli). // Se fosse nero il suo spostamento o rimozione potrebbe portare a violazione proprietà alberi RB Node *nt = &n; // Tiene traccia del nodo che prenderà il posto di n o del successore di n (in caso n abbia entrambi i figli) Node *nt2 = nullptr; // Tiene traccia del colore originario di n o di suo successore; bool black = n.black; if (n.left == nullptr) { nt2 = n.right; transplant(root, &n, n.right); // caso 1 e 2 } else if (n.right == nullptr) { nt2 = n.left; transplant(root, &n, n.left); // caso 3 } else { nt = bst_min(n.right); black = nt->black; nt2 = nt->right; if (nt->parent == &n) { if (nt2) nt2->parent = nt; } else { transplant(root, nt, nt->right); nt->right = n.right; nt->right->parent = nt; } transplant(root, &n, nt); nt->left = n.left; nt->left->parent = nt; nt->black = n.black; } if (black && nt2) rb_delete_fixup(root, nt2); } void rb_delete_fixup(Node *&root, Node *&n) { while (n != root && n->parent->black) { if (n == n->parent->left) { Node *nt = n->parent->right; if (!nt->black) { n->black = true; nt->parent->black = false; left_rotate(root, *n->parent); nt = n->parent->right; } if (nt->left->black && nt->right->black) { nt->black = false; n = n->parent; } else { if (nt->right->black) { nt->left->black = true; nt->black = false; right_rotate(root, *nt); nt = n->parent->right; } nt->black = n->parent->black; n->parent->black = true; nt->right->black = true; left_rotate(root, *n->parent); n = root; } } else { Node *nt = n->parent->left; if (!nt->black) { n->black = true; nt->parent->black = false; right_rotate(root, *n->parent); nt = n->parent->left; } if (nt->right->black && nt->left->black) { nt->black = false; n = n->parent; } else { if (nt->left->black) { nt->right->black = true; nt->black = false; left_rotate(root, *nt); nt = n->parent->left; } nt->black = n->parent->black; n->parent->black = true; nt->left->black = true; right_rotate(root, *n->parent); n = root; } } } } // Stampa in ordine crescente sftruttando proprietà degli alberi binari di ricerca void bst_walk(Node *n) { if (n != nullptr) { bst_walk(n->left); printf("%d ", n->val); bst_walk(n->right); } } Node* bst_search(Node *n, int val) { while (n != nullptr && val != n->val) { if (val < n->val) // se valore è più piccolo continua nel sottoalbero sinistro n = n->left; else n = n->right; // altrimenti nel sottoalbero destro return n; } } Node* bst_min(Node *n) { // Nodo con valore minimo è sempre ultimo nei vari sottoalberi sinistri while (n->left != nullptr) n = n->left; return n; } Node* bst_max(Node *n) { // Nodo con valore massimo è sempre ultimo nei vari sottoalberi destri while (n->right != nullptr) n = n->right; return n; } Node* bst_successor(Node *n) { // Successore è sempre nodo con valore minimo nel sottoalbero destro di un nodo if (n->right != nullptr) return bst_min(n->right); // A meno che il nodo sia sprovvisto di figlio destro. // In questo caso successore è il primo antenato il cui figlio destro != dal nodo // corrente man man che si risale l'albero. Node *np = n->parent; while (np != nullptr && n == np->right) { n = np; np = np->parent; } return np; } Node* bst_predeccessor(Node *n) { // Predeccessore è sempre nodo con valore massimo nel sottoalbero sinistro di un nodo if (n->left != nullptr) return bst_max(n->left); // A meno che il nodo sia sprovvisto di figlio sinistro. // In questo caso successore è il primo antenato il cui figlio sinistro != dal nodo // corrente man man che si risale l'albero. Node *np = n->parent; while (np != nullptr && n == np->left) { n = np; np = np->parent; } return np; }
Riferimenti
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] http://computerscience.unicam.it/diberardini/didattica/algoritmi/2011-12/rbtrees.pdf
[3] http://www.math.unipd.it/~baldan/Algoritmi/Slide/11-AlberiRossoNeri.pdf
[4] Strutture dati: Alberi binari di ricerca
Nessun commento:
Posta un commento