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.