Esercizi su Alberi Binari (esercitazioni canale P-D) ____________________________________________________ struct albin{ int info; struct albin *sin; struct albin *des; } typedef struct albin albin; (I) Semplici Ricorsioni ======================= * Conta numero di foglie ------------------------ int foglie(albin *a){ if (a==NULL) return 0; if ((a->sin==NULL)&&(a->des==NULL)) return 1; return foglie(a->sin)+foglie(a->des); } * Numero di nodi a livello h ---------------------------- int ampiezza(albin *a, int h){ if (a==NULL) return 0; if (h==0) return 1; else return ampiezza(a->sin, h-1) + ampiezza(a->des, h-1); } (II) Semplici problemi di decisione =================================== * heap: ------- un albero binario è detto uno "heap decrescente" se l'etichetta di ogni nodo padre è maggiore uguale dell'etichetta di ciascuno dei figli. int isHeap(albin *a){ if (a==NULL) return 1; if ((a->sin!=NULL) && (a->info < a->sin->info)) return 0; if ((a->des!=NULL) && (a->info < a->des->info)) return 0; return (isHeap(a->sin) && isHeap(a->des)); } * completo: ----------- un albero è "completo" se tutte le foglie sono allo stesso livello e ogni nodo interno ha due figli. equivalentemente in ogni nodo le profondità del sottoalbero sinistro e destro coincidono. usando una funzione altezza(albin *a) che calcola l'altezza dell'albero, un algoritmo di decisione per la completezza si può scrivere così: int isComplete(albin *a){ if (a==NULL) return 1; return ((altezza(a->sin)==altezza(a->des)) && isComplete(a->sin) && isComplete(a->des)); } * BST: ------ un albero è un BST (Binary Search Tree) se, per ogni nodo n dell'albero, le etichette del sottoalbero sinistro sono strettamente minori dell'etichetta di n, e le etichette del sottoalbero destro sono strettamente maggiori dell'etichetta di n. int isBST_aux(albin *a, int min, int max){ if (a==NULL) return 1; return ((a->info > min)&&(a->info < max) &&(isBST_aux(a->sin, min, a->info)) &&(isBST_aux(a->des, a->info, max))); } int isBST(tree *t){ return isBST_aux(a, INT_MIN, INT_MAX); } (III) Visite Iterative ====================== Si considerano versioni iterative delle visite di alberi binari. * attraversamento in Preordine Iterativo: ----------------------------------------- Si usa una pila. Si presuppone di avere definito il tipo pila opportunamente per avere "pile di alberi". Si inizia spingendo l'albero nella pila. Finché la pila non è vuota, si estrae la radice dell'albero in cima alla pila, si cancella la cima della pila, e si spingono i sottoalberi destro e sinistro nella pila. void preOrderIter(albin *a){ pila *p = nuovaPila(); push(p, a); while (!pilaVuota(p)){ a = pop(p); printf("%d", a->info); if (a->des!=NULL) push(p, a->des); if (a->sin!=NULL) push(p, a->sin); } } * attraversamento inOrder iterativo: ------------------------------------ void inOrderIter(albin *a){ pila *p = nuovaPila(); //costruttore di classe while(1){ while(a!=NULL){ push(&p,a); a = a->sin; } if (pilaVuota(p)) break; a = pop(&p); printf("%d", a->info); a = a->des; } } * attraversamento postOrder iterativo: -------------------------------------- ESERCIZIO * level-order: -------------- Sostituendo la pila con una coda nell'algoritmo di visita in preordine iterativa si ottiene un nuovo tipo di visita dell'albero: le etichette vengono visitate livello per livello e da destra a sinistra. Invertendo l'ordine di accodamento del sottoalbero sinistro e destro si ottiene la più usuale visita "level-order": l'albero è visitato livello per livello da sinistra a destra. void levelOrder(albin *a){ coda *c = nuovaCoda(); enqueue(&c, a); while (!codaVuota(c)){ a = dequeue(&c); printf("%d", a->info); if (a->sin!=NULL) enqueue(&c, a->sin); if (a->des!=NULL) enqueue(&c, a->des); } } (IV) Binary Search Trees (BST) ============================== Sappiamo che la ricerca in un BST è particolarmente agevole ed efficiente. * Ricerca in BST -------------- int cercaBST(albin *a, int c) { if (a == NULL) return 0; if (c == a->info) return a->info; else if (c < a->info) return cercaBST( a->sin, c ); else return cercaBST( a->des, c ); } D'altra parte, inserimento e cancellazione sono più complesse di quanto lo siano in alberi binari qualunque. * BST insertion (ricorsiva) --------------------------- void insBST(albin **a, int v){ if (*a == NULL){ *a = malloc(sizeof(albin)); if (*a != NULL){ (*a)->info=v; (*a)->sin=NULL; (*a)->des=NULL; } else{ // SEGNALA INDISPONIBILITA' MEMORIA } } else{ if (v < (*a)->dato)){ insBSTiter(&((*a)->sin),v); } else (v > (*a)->dato)){ insBSTiter(&(*a)->des),v); } } } * BST deletion (iterativa): per esercizio secondo lo schema seguente. --------------------------- Per cancellare un nodo in un BST e mantenere la proprietà di essere un BST dobbiamo trovare - nell'albero - un candidato opportuno per il nodo che cancelliamo, se questo non è una foglia. Supponiamo di voler cancellare il nodo con etichetta x nel BST T. Distinguiamo i seguenti casi. (i) x è una foglia: facile! (ii) x ha un solo figlio: facile (sostituisci il nodo x con il figlio) (iii) x ha due figli: siano y e z i figli sinistro e destro risp. di x. Dobbiamo trovare in T un valore da sostituire ad x senza perdere la proprietà BST. Abbiamo due scelte naturali: il nodo di etichetta massima nel sottoalbero sinistro radicato in x oppure il nodo di etichetta minima nel sottoalbero destro radicato in x. Come individuare questi candidati nell'albero? Ci si convince facilmente che, dato che siamo in un BST, il nodo con etichetta massima nel sottoalbero sinistro di x è il nodo più a destra nel sottoalbero sinistro di x. Dualmente, il nodo con etichetta minima nel sottoalbero destro di x è il nodo più a sinistra nel sottoalbero destro di x. Abbiamo così un algoritmo per raggiungere, da x, i nostri candidati: scorrere il sottoalbero sinistro di x scegliendo sempre il figlio destro, fino a raggiungere un nodo senza figli destri, oppure, dualmente, scorrere il sottoalbero destro di x scegliendo sempre il figlio sinistro, fino a raggiungere un nodo senza figli a sinistra. Supponiamo di scegliere come sostituto di x il nodo con etichetta massima nel sottoalbero sinistro di x. Chiamiamo c tale nodo. Distinguiamo due casi (1) c è una foglia. In questo caso dobbiamo fare le seguenti operazioni: (1.1) salvare un puntatore ad x in una variabile d'appoggio (1.2) far puntare il padre di x a c (1.3) far puntare il figlio destro del padre di c a NULL (1.4) far puntare il figlio destro di c al figlio destro di x (1.5) far puntare il figlio sinistro di c al figlio sinistro di x (1.6) liberare la variabile d'appoggio. (2) c non è una foglia. In questo caso, necessariamente per come è stato scelto c, c ha soltanto un figlio sinistro. Dobbiamo fare le seguenti operazioni: (2.1) salvare un puntatore ad x in una variabile d'appoggio (2.2) far puntare il padre di x a c (2.3) far puntare il figlio destro del padre di c al figlio sinistro di c (2.4) far puntare il figlio destro di c al figlio destro di x (2.5) far puntare il figlio sinistro di c al figlio sinistro di x (2.6) liberare la variabile d'appoggio. Si osserva facilmente che (2.3) preserva la proprietà BST: il figlio sinistro di c ha un'etichetta > dell'etichetta del padre di c, dato che c è un figlio destro. (ESERCIZIO: scrivere il codice.) * cancellazione in BST (ricorsiva) ---------------------------------- Supponiamo di possedere una operazione di "fusione" di BST che prende due BST e li combina in un nuovo BST. Chiamiamo "join" una tale operazione binaria. Allora è facile descrivere un algoritmo ricorsivo di cancellazione di un nodo da un BST. void cancBST(albin **a, int v) { int w; albin *temp; if (*a == NULL) return; w = (*a)->info; if (v < w) cancBST(&((*a)->sin), v); if (v > w) cancBST(&((*a)->des, v); if (v == w) { temp = *a; *a = join((*a)->sin), (*a)->des)); free(temp); } } Diamo ora un algoritmo ricorsivo di Join. * join di BST ------------- albin * join(albin * a, albin * b) { if (b == NULL) return a; if (a == NULL) return b; insBST(b, a->info); b->sin = join(a->sin, b->sin); b->des = join(a->des, b->des); free(a); return b; } * Rotazioni ----------- la rotazione è una operazione locale in un albero di ricerca che preserva l'ordine delle chiavi in una ricerca in-order. le rotazioni sono usate tipicamente per ribilanciare un albero. Una Rotazione Destra Singola è l'operazione che trasforma un albero di forma A B T3 T1 T2 nell'albero di forma B T1 A T1 T2 * Rotazione Destra Singola -------------------------- albin *srr(albin *a){ albin *appo; appo = a; a = a->sin; appo->sin = a->des; a->des = appo; return a; }