Allegati & Link - Pagine di Luigi De Vivo 02

Sezione

Servizio

Allegati & Link

PAGINE di Luigi De Vivo/2 [11 di 12]

Generalmente si distinguono 3 ordini di visita:

	Visita in ordine anticipato, si visita prima la radice, poi il sotto-albero sinistro e poi quello destro;
	Visita in ordine simmetrico, prima si visita il sotto-albero sinistro, poi la radice e quindi il sotto-albero destro;
	Visita in ordine posticipato, si tratta di un ordine di visita che parte dalle foglie (informazioni che appartengono al livello più alto dei sotto-alberi) e risale verso la radice.

Si noti che gli algoritmi di visita sono solo degli schemi per attraversare gli alberi in un certo ordine e che gli algoritmi ricorsivi sono particolarmente adatti per manipolare informazioni la cui struttura dati è definita ricorsivamente; ad esempio per il tipo di albero definito prima :

(*Visita in ordine simmetrico*)
Procedure Visinorder(Radice : Albero);(*Radice albero*)
Begin
If (Radice<>Nil) Then
Begin
    Visinorder(Radice^.sinistro); (*visita sotto-albero sx*)
    Writeln(Radice^.Key);         (*Stampa l’informazione*)
    Visinorder(Radice^.destro);   (*visita sotto-albero dx*)
End;
End;

(*Visita in ordine posticipato*)
Procedure Vispostorder(Radice : Albero);(*Radice albero*)
Begin
If (Radice<>Nil) Then
Begin
    Vispostorder(Radice^.sinistro);(*visita sotto-albero sx*)
    Vispostorder(Radice^.destro); (*visita sotto-albero dx*)
    Writeln(Radice^.Key);          (*Stampa l’informazione*)
End;
End;

(*Visita in ordine anticipato*)
Procedure Vispreorder(Radice : Albero);(*Radice albero*)
Begin
If (Radice<>Nil) Then
Begin
    Writeln(Radice^.Key);          (*Stampa l’informazione*)
    Vispreorder(Radice^.sinistro); (*visita sotto-albero sx*)
    Vispreorder(Radice^.destro);   (*visita sotto-albero dx*)
End;
End;

Mostriamo anche una funzione che ci permette di sapere se una chiave X è presente nell’albero binario:

Function Esiste(x: Word; Radice: Albero):Boolean;
Begin
If (Radice=Nil) Then Esiste:=False
Else If (Radice^.Key=x) Then Esiste:=True
Else If Esiste(x,Radice^.sinistro) Then Esiste:=True
Else Esiste:=Esiste(x,Radice^.destro);
End;

L'Albero Binario di Ricerca (ABR) è una delle strutture dati che consente, se bilanciato in altezza, di effettuare ricerche inserimenti e cancellazioni in tempo breve: si dice bilanciato in altezza un albero se i suoi sotto alberi sinistro e destro differiscono al più di uno.

Per definizione un Albero Binario di Ricerca è un albero binario di chiavi di tipo “T” soggetto ai seguenti vincoli:

	il sotto-albero sinistro contiene solo chiavi minori della radice ed è a sua volta un ABR;
	il sotto-albero destro contiene solo chiavi maggiori della radice ed è a sua volta un ABR.

Il tipo “T” può essere qualsiasi tipo per il quale sia definita una relazione d'ordine totale.

Per gli ABR valgono le seguenti proprietà:

	è possibile condurre un tipo di ricerca (molto simile a quella binaria) la cui complessità è logaritmica (sempre che l'ABR sia bilanciato in altezza);
	gli inserimenti possono effettuarsi senza dover rimuovere alcun elemento dell'ABR, a condizione di collegare un nodo contenente la nuova chiave al posto del sotto-albero vuoto che chiude la ricerca con insuccesso;
	la procedura di cancellazione che può essere descritta come segue :“rimpiazza il nodo cancellato con il suo sotto-albero destro e poni il sotto-albero sinistro del nodo cancellato come sotto-albero sinistro del nodo più a sinistra del sotto-albero destro del nodo cancellato" ha sempre una certa complessità dell'ordine della ricerca;
	la visita in ordine simmetrico produce le chiavi in modo ordinato.

	Allegati & Link			ALBERI BINARI DI RICERCA [2 di 3]
	11 di 12

PASCAL »

^Home

Pascal|Manuali|Tabelle|Schede
Tutorial Assembly|Palestra Assembler

Aggiungi Giobe®2000 ai preferiti

Motore
Ricerca

Rendi Giobe®2000 pagina di Default