1. Definizione di Albero


Struttura Dati Astratta Albero Binario di Ricerca (ABR)



Scaricare 142.5 Kb.
Pagina5/11
21.12.2019
Dimensione del file142.5 Kb.
1   2   3   4   5   6   7   8   9   10   11

2.Struttura Dati Astratta Albero Binario di Ricerca (ABR)


La definizione di un albero binario non implica la definizione della strategia di inserimento, ricerca e cancellazione delle informazioni memorizzate in un albero. A tal proposito possono essere definite infinite strategie. Quella che presenta numerosi vantaggi è quella basata sul seguente concetto.

In genere un nodo ha un contenuto informativo appartenente ad un certo tipo (dominio). Si supponga di aver definito gli operatori "<" e ">" (minore e maggiore) per il tipo di appartenenza di ciascun elemento nel nodo.

Una particolare modalità di gestione dell'albero binario consiste nel disporre i nodi nell'albero binario, in modo che preso un qualunque nodo dell'albero, tutti i nodi del sottoalbero di sinistra contengono elementi che risultano minori, in accordo all'operatore "<", dell'elemento del nodo, e tutti i nodi del sottoalbero di destra contengono elementi che risultano maggiori, secondo l'operatore ">", dell'elemento del nodo.

Nel caso in cui un nodo contenga più elementi di tipo diverso (ad esempio si pensi ad uno struct in C), in genere la relazione di ordine tra i nodi viene compiuta su uno solo tra questi elementi, denominato chiave di ricerca. Ovviamente tutte le operazioni di inserimento, ricerca e cancellazione devono usare la stessa chiave di ricerca !



L'organizzazione appena descritta prende il nome di ALBERO BINARIO DI RICERCA. Il vantaggio principale di tale organizzazione risiede essenzialmente nell’abbattimento dei tempi necessari alla ricerca di un elemento. Ogni volta che è necessario ricercare un elemento, il confronto del valore dell'elemento con quello contenuto in un generico nodo (o con la chiave di ricerca scelta), permette di eliminare dalla ricerca o il sottoalbero corrente di destra o quello di sinistra. Visto che la ricerca di un elemento è sempre presente sia nella fase di inserimento che in quella di cancellazione, il vantaggio di utilizzare una albero binario di ricerca è notevole.




Condividi con i tuoi amici:
1   2   3   4   5   6   7   8   9   10   11


©astratto.info 2019
invia messaggio

    Pagina principale