Alberi e altre strutture

Materie:Appunti
Categoria:Informatica
Download:91
Data:29.05.2007
Numero di pagine:2
Formato di file:.txt (File di testo)
Download   Anteprima
alberi-altre-strutture_1.zip (Dimensione: 1.09 Kb)
trucheck.it_alberi-e-altre-strutture.txt     2.27 Kb
readme.txt     59 Bytes


Testo

albero : struttura dati non lineare,ha le stesse caratteristiche della lista
un predecessore,+ successori
radice : unico elemento dell'albero senza predecessori (uno solo!)
nodo : elemento caratteristico dell'albero
foglie : nodo senza successori
ramo : segmento che unisce 2 nodi
cammino : insieme di rami k si devono attraversare per passare dal nodo A al nodo B
altezza di un albero : lunghezza del cammino massimo (numero di livelli di un albero)
livello di un nodo : associato alla lunghezza del cammino che lo collega alla radice
grado di un nodo : numero di figli del nodo stesso
grado di un albero : grado massimo tra i suoi nodi
albero bilanciato : livello delle foglie differisce al MAX di 1
perfettamente bilanciato : tutte le foglie sullo stesso livello
lunghezza del cammino : numero dei rami del cammino
figli : successori di un nodo
metodi di attraversamento : criterio x esaminare tutti i nodi dell'albero senza trascuarne nessuno
-anticipato RSD
-simmetrico SRD
-posticipato SDR
albero binario : alberoin cui ogni nodo puт avere al MAX 2 figli e si distringue tra sottoalbero sinistro e sottoalbero destro
ABR : alberi binari di ricerca
la Kr и la chiave di informazione contenuta nella radice,il sottoalbero sinistro contiene tutte le informazioni con chiavi minori a Kr,il sottoalbero di destra quelle con la chiave maggiore.
grafi : struttura dati NON lineare,ogni elemento puт avere + successori e + predecessori
un grafo si dice PESATO se ad ogni arco (ramo) и associata una informazione
un grafo si dice ORIENTATO se esiste almeno un ramo in cui si и fissato il verso (usando il segno +\-)
matrice quadrata : numero colonne = numero righe
matrice simmetrica : aij=aji
matrice trasposta : si ottiene cambiando le righe con le colonne
matrice sparsa : matrice con informazioni inutili
archivio : insieme di informazioni su memoria di massa
chiave primaria Kp : consente di identificare univocamente un singolo record
chiave secondaria Ks : identifica + record
sequanziale : informazioni memorizzate una di seguito all'altra
le modalitа di accesso non dipendono dall'informazione ma dal supporto di memorizzazione
ricerca con successo : (n+1)/2
ricerca senza successo : n
costo di una ricerca : numero di accesso su memoria di massa
merge : fusione di 2 vettori

Esempio