$y.value \le x.value$, se $y$ è un nodo nel sottoalbero sinistro di $x$.
$y.value \ge x.value$, se $y$ è un nodo nel sottoalbero destro di $x$.
Grazie a questa interessante proprietà si possono eseguire molte operazioni in tempo $O(\log n)$ (con $n$ numero di elementi dell'albero) se si riesce a mantenere un certo grado di bilanciamento nell'albero. In questo caso $O(\log n)$ è proprio l'altezza dell'albero.
Le prestazioni dunque dipendono dal grado di bilanciamento dell'albero. Se si crea, ad esempio, un albero inserendo elementi con valori quasi sempre crescenti o decrescenti l'albero sarà totalmente sbilanciato e la sua altezza si avvicinerà ad $n$ più che a $O(\log n)$, vanificandone tutti i benefici.
Con un inserimento casuale degli elementi dell'albero, però, si può assumere un ragionevole grado di bilanciamento dello stesso e dunque assumere anche che operazioni del tipo: inserisci un nodo con valore $x$, cancella il nodo con valore $x$, ritorna l'elemento con massimo (o minimo) valore, ricerca l'elemento con valore $x$, ecc. possono essere eseguite in tempo $O(\log n)$. L'unica operazione che non può essere eseguita con questo tempo è stampare tutti gli elementi dell'albero che, naturalmente, richiede un tempo $O(n)$.
Prima di passare al codice si esaminerà brevemente la logica che sta dietro al metodo che cancella un nodo. Per gli altri metodi, invece, è sufficiente leggere il relativo codice e i commenti per comprenderne la logica implementativa.
Se si cancella un nodo $x$ si possono verificare 5 casi:
1- $x$ ha entrambi i figli nulli. In questo caso $x$ viene eliminato senza conseguenze.
2- $x$ ha il figlio sinistro nullo. In questo caso il figlio destro prende il posto di $x$.
3- $x$ ha il figlio destro nullo. In questo caso il figlio sinistro prende il posto di $x$.
4- Il figlio destro di $x$ è il successore di $x$. In questo caso il successore prende il posto di $x$.
5- Il successore di $x$ non è il figlio destro di $x$. In questo caso, prima che il successore di $x$ prenda il suo posto, bisogna settare il figlio destro del successore al figlio destro di $x$. Bisogna settare infine il figlio sinistro del figlio destro di $x$ al figlio destro del successore di $x$.
Per comprendere meglio si faccia riferimento all'immagine sopra. Volendo cancellare il nodo con valore $12$, prima che il nodo $13$ (il suo successore) prenda il suo posto, il figlio destro del nodo $13$ (nell'immagine non c'è ma facciamo finta che esista) diventa il figlio destro del nodo $12$ ed il figlio sinistro del nodo $13$ diventa figlio sinistro del nodo $15$. A questo punto il nodo $13$ può prendere il posto del nodo $12$.
/*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; }; 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 bst_insert(Node*&, Node&); void bst_delete(Node*&, Node&); int main(int argc, char *argv[], char *envp[]) { Node n12 = { 12, nullptr, nullptr, nullptr }; Node *root = nullptr; bst_insert(root, n12); Node n5 = { 5, nullptr, nullptr, nullptr }; Node n9 = { 9, nullptr, nullptr, nullptr }; Node n2 = { 2, nullptr, nullptr, nullptr }; Node n18 = { 18, nullptr, nullptr, nullptr }; Node n13 = { 13, nullptr, nullptr, nullptr }; Node n17 = { 17, nullptr, nullptr, nullptr }; Node n19 = { 19, nullptr, nullptr, nullptr }; Node n15 = { 15, nullptr, nullptr, nullptr }; bst_insert(root, n5); bst_insert(root, n9); bst_insert(root, n2); bst_insert(root, n18); bst_insert(root, n13); bst_insert(root, n17); bst_insert(root, n19); bst_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); bst_delete(root, n9); bst_delete(root, n15); bst_delete(root, n2); bst_walk(root); printf("\n"); return 0; } // 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; } // Sostituisce un sottoalbero con radice oldn con un altro con radice newn 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 bst_insert(Node *&root, Node &n) { Node *nt = nullptr; Node *nroot = root; // Scorre fino a trovare dove poter inserire il nodo rispettando // la 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; // Se nt è null allora albero era vuoto if (nt == nullptr) 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 destro di ultimo nodo valido trovato in while } void bst_delete(Node *&root, Node &n) { if (n.left == nullptr) transplant(root, &n, n.right); // caso 1 e 2 else if (n.right == nullptr) transplant(root, &n, n.left); // caso 3 else { Node *nt = bst_min(n.right); if (nt->parent != &n) { // caso 5 transplant(root, nt, nt->right); nt->right = n.right; nt->right->parent = nt; } // caso 4 transplant(root, &n, nt); nt->left = n.left; nt->left->parent = nt; } }
Riferimenti
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Algoritmi in C - Sedgewick
Nessun commento:
Posta un commento