Testo completo
ESERCIZIO DI ASD DEL 15 DICEMBRE 2008
Da Vettore Ordinato a Binary Search Tree
Sia A un vettore di interi ordinato di lunghezza n. Si consideri il problema di creare un BST T contenente gli elementi di A ed avente altezza O(log n).
1 Si scriva lo pseudocodice di una procedura per risolvere tale problema.
2 Si dimostri la correttezza della procedura proposta.
3 Si determini la complessit`a della procedura proposta.
Date: 15 Dicembre 2008.
1
Documenti correlati
Con una scansione del vettore A possia- mo riempire il vettore C, esattamente come si fa in CountingSort, con l’unica differenza che per ogni elemento di A che consideriamo
1 Si scriva lo pseudocodice di un algoritmo in place che permette di deter- minare se L `e ciclica, nel caso in cui L contenga solo interi maggiori di zero.. Si noti che L
Suggerimento: Modificare i puntatori degli elementi della lista, in modo da riconoscere gli elementi gi` a visitati e nel frattempo copiare gli elementi in una nuova lista.. Si noti
Siano L 1 ed L 2 due liste concatenate ordinate le cui chiavi sono numeri interi.. Si consideri il problema di fondere le due liste ottenendo un’unica
Evitare di scrivere un’unica procedura, ma scrivere separatamente le procedure per l’inserimento e la cancellazione nelle liste.. Se necessario utilizzare anche il
Suggerimento: Mettere l’elemento centrale del vettore nella radice e poi procedere ricorsivamente sul sottovettore di sinistra per costruire il sot- toalbero sinistro e sul
Se il vettore A ` e ordinato, la procedura Rec Array to BST(A, i, j, y) termina sempre restituendo un nodo x che ` e radice di un binary search tree conte- nente tutti e soli
Si consideri il problema di determinare se T pu` o essere un RBT con radice di colore C ed altezza nera h.. 1 Si scriva lo pseudocodice di una procedura per risolvere
