L'università è facile…

studia finché non lo diventa…

Alberi binari di ricerca

un albero binario di ricerca è una struttura dati puntata che è :

-vuoto

-una terna T=(r,L.R) dove r è un nodo (radice),L e R sono alberi binari di ricerca.  Un L’albero binario di ricerca sopporta 2 strutture dati astratte: code con priorità e dizionari. Esempio di un albero binario di ricerca:

image

La proprietà degli alberi binari di ricerca

Per ogni nodo x,tutti i valori del sotto albero sinistro di x sono inferiori al valore di x  e tutti i valori del sotto albero destro di x sono superiori al valore di x.

Operazioni basilari

Insert:

image

image

Search:

Ricerca di un elemento x. Si confronta x alla radice ;

-se x inferiore si ricerca nel sotto albero sinistro.

-se x è maggiore ,si ricerca nel sotto albero  destro.

Analisi:

image

Delete:

image

Min e Max

il minimo si trova nel nodo piu a sinistra e il massimo si trova nel nodo piu a destra.

image

Successore e Predecessore

image

oppure

Quando right[x]=NIL,successore di x ??

image

Verifica : x è max del sotto albero sinistro di y

Ogni operazione in un albero binario impiega come tempo di esecuzione O(h),h essendo l’altezza dell’albero.

Per risolvere questo problema abbiamo due soluzioni :

-Alberi binari costrutti casualmente.

-Alberi bilanciati

Grazie di aver letto l’articolo. Dubbi ,domande e suggerimenti ?Lo spazio per i commenti è qui sotto.

avatarfirma

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Informazione

Questa voce è stata pubblicata il 22/06/2010 da in Algoritmi e strutture dati con tag , , , , , , , .
%d blogger hanno fatto clic su Mi Piace per questo: