Magazine Università

Alberi binari di ricerca

Creato il 22 giugno 2010 da Ewilly

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.

 

avatar
firma



Potrebbero interessarti anche :

Ritornare alla prima pagina di Logo Paperblog

Possono interessarti anche questi articoli :

Magazine