-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.