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:

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:

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:

Delete:

Min e Max

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

Successore e Predecessore

oppure

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

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.