Tesina di Algoritmi e strutture dati

Tesina di Algoritmi e strutture dati Anno Accademico 2011/2012 Prof. Carlo Sansone Studente Torrico Paolo M63/000155 RB –TREE Descrizione Generale Rotazioni: descrizione e loro pseudocodice Operazioni di ricerca e inserimento:descrizione e pseudocodice Codice implementativo Analisi grafica della complessità MOLTIPLICAZIONE RICORSIVA DI MATRICI Descrizione Generale Pseudocodice Codice implementativo Analisi grafica della complessità RB -TREE Descrizione Generale Gli alberi rossoneri sono degli alberi binari di ricerca bilanciati in cui le operazioni sono modificate in modo da avere un altezza dell’albero logaritmica col numero di elementi. Un albero binario di ricerca è composto da un insieme di nodi e ciascun nodo è visto come un oggetto che contiene quattro campi: un puntatore p al nodo padre, un puntatore left al figlio sinistro del nodo, un puntatore right al figlio destro del nodo e un campo key che contiene il valore chiave del nodo. Quindi un albero rossonero è un albero binario di ricerca in cui ad ogni nodo aggiungo un campo color che contiene il colore del nodo che può essere rosso o nero. Se ad un nodo manca un padre o un figlio, il campo puntatore corrispondente punterà a null che in questa struttura verrà implementata come T.nil, il quale rappresenta una sentinella, ovvero un oggetto con gli stessi campi di un nodo ordinario dell’albero in cui il campo colore è nero mentre gli altri campi possono essere impostati a valori arbitrari. Perciò la radice dell’albero nel suo campo p avrà T.nil cioè la sentinella che sarà il padre della radice. Anche le foglie dell’albero saranno rappresentate dalla sentinella T.nil e quindi saranno viste come nodi esterni all’albero che non contengono dati. I nodi interni dell’albero sono quei nodi che contengono un valore chiave e le foglie servono semplicemente ad indicare dove finisce un albero. Gli alberi rossoneri mi garantiscono che il cammino più lungo che va dalla radice ad una foglia è al massimo lungo il doppio del cammino più breve e questo mi garantisce un albero approssimativamente bilanciato. Poiché le operazioni di dizionario, cioè inserimento, ricerca, e cancellazione hanno un tempo d’esecuzione nel caso peggiore proporzionale all’altezza dell’albero, ne segue che gli alberi rossoneri sono molto efficienti nel caso peggiore perché effettuano queste operazioni in un tempo O (logn), al contrario di quanto accade con gli alberi binari di ricerca. Vediamo ora di quali proprietà godono tali strutture dati. Innanzitutto gli alberi rossoneri sono alberi binari di ricerca e perciò hanno il vincolo per cui ogni nodo contiene un valore minore o uguale a quello di tutti i nodi del suo sottoalbero destro, e maggiore o uguale a quello di tutti i nodi del suo sottoalbero sinistro. Inoltre un albero rossonero soddisfa le seguenti proprietà: 1. Ogni nodo ha colore rosso o nero. 2. La radice è nera. 3. Ogni foglia (nil) è nera. 4. Se un nodo è rosso i s