Domanda su Alberi

[Kleidemos]

Ma gli alberi sono delle liste con 2 puntatori (prev e next)????


Tnk 1k

[Icedguardian]

Dipende.

Es. albero binario ha elementi con due puntatori che puntano al figlio sinistro e figlio destro. Però è proprio la forma che cambia in un albero rispetto ad una lista.

Poi ci sono altri tipi di alberi.

[Kleidemos]

cioe una lista bilaterale nn è un albero???
E che tipo di alberi ci sono???


P.s: ma sono utili nei programmi reali queste strutture?

[Icedguardian]

Dovrebbero ma non mi è mai capitato di usarli per il momento

Classico esembio del albero binario di ricerca:

Nodo ( valore, figlioSx, figlioDx)

Un nodo del albero ha un valore (es. un intero)
e può avere al max due figli (cioè due puntatori a nodi figli).
Ogni figlio Sx ha il valore <= al valore del padre mentre ogni figlio Dx ha il valore maggiore (ecco perchè li chiamano di ricerca ).

Un albero ha tre tipi di nodi:

Un nodo radice, cioè senza padre
Nodi interni e
Nodi foglie, cioè senza figli.

Adesso sai tutto quelli che ti serve per creare un albero binario di ricerca.

Ci sono anche i B+ alberi, alberi generici, ecc...

Ciao

[Kleidemos]

na cosa tipo:

typedef struct SAlbero
{
    int data;
    SAlbero *figlioSx; 
    SAlbero *figlioDx;   
}Albero;

Se ho ben capito.

P.S: come hai imparato tu?

[bsummer]

Originariamente inviato da Kleidemos
cioe una lista bilineare nn è un albero???
E che tipo di alberi ci sono???


P.s: ma sono utili nei programmi reali queste strutture?

Un albero per essere definito tale deve:

- avere un nodo, detto radice, che non possiede nessun nodo padre

- avere dei nodi, detti foglie, che non posseggono nessun nodo figlio

- qualsiasi nodo X che non è radice nè foglia, possiede un nodo padre (cioè esiste un nodo di cui il figlio è il nodo X) e dei nodi figli (cioè esistono dei nodi di cui il nodo X è padre)

La lista semplice può essere vista come un tipo di albero in cui ogni nodo ha al più un figlio.

Le strutture ad alberi sono varie: si va dai semplici alberi binari (bilanciati o non) ad alberi aventi strutture molto più complesse (n°variabile di figli).

Il loro utilizzo spazia un po' in tutti i campi: si va dalla computer graphics a banali applicazioni matematiche. Cmq basta un po' di inventiva: sono strutture molto versatili che si adattano bene a diversi scopi...

Aloha!

[Kleidemos]

ma la disposizione delle directory di un filesystem possono essere considerati alberi?

[mjordan]

Originariamente inviato da Kleidemos
ma la disposizione delle directory di un filesystem possono essere considerati alberi?

Certo, ma non alberi binari. In genere per la costruzione di filesystem si adottano un particolare tipo di alberi detti BB trees, una particolare struttura ad albero che viene impiegata in genere in file di archivio. Poichè i nodi possono avere anche centinaia di figli, si possono trovare i dati molto velocemente perchè l'altezza dell'albero rimane piccola, pur contenendo una grande quantità di informazioni.

[mjordan]

Dimenticavo. Varianti di BB alberi molto sofisticate vengono usate per esempio nei DBMS ...

[Kleidemos]

ma il reiserFs nn ha una struttura B*Tree..............e una di quelle varianti di cui parli?

[mjordan]

Originariamente inviato da Kleidemos
ma il reiserFs nn ha una struttura B*Tree..............e una di quelle varianti di cui parli?

Se ne analizzi a fondo le proprietà vedi che tutto da li parte. Il resto sono tecniche per implementare caratteristiche e migliorare gli accessi R/W

[Kleidemos]

Originariamente inviato da mjordan
Se ne analizzi a fondo le proprietà vedi che tutto da li parte. Il resto sono tecniche per implementare caratteristiche e migliorare gli accessi R/W

quindi gli alberi( e le liste ) sono importanti nel mondo software?

[mjordan]

Direi che dire importanti è riduttivo.
Tutto si costruisce sulle strutture dati. . . E alberi (binari semplici) e liste (lineari singole) sono le + semplici e le meno efficienti . . .

[Kleidemos]

Originariamente inviato da mjordan
Tutto si costruisce sulle strutture dati. . . E alberi (binari semplici) e liste (lineari singole) sono le + semplici e le meno efficienti . . .

Cosa c'è d'altro??

[mjordan]

Originariamente inviato da Kleidemos
Cosa c'è d'altro??

Tabelle hash, alberi red black, albery splay, patricia, heap, heap binomiali, heap di fibonacci, deap, B alberi, grafi ciclici, aciclici, bipartiti rappresentati con matrici di adiacenza o liste di adiacenza. Poi ci sono tutti gli algoritmi che operano su di esse e le varie tecniche matematiche per analizzarne le prestazioni (complessità computazionale)....

[Kleidemos]

Originariamente inviato da mjordan
Tabelle hash, alberi red black, albery splay, patricia, heap, heap binomiali, heap di fibonacci, deap, B alberi, grafi ciclici, aciclici, bipartiti rappresentati con matrici di adiacenza o liste di adiacenza. Poi ci sono tutti gli algoritmi che operano su di esse e le varie tecniche matematiche per analizzarne le prestazioni (complessità computazionale)....

[mjordan]

Come vedi l'informatica è ben altro che conoscere un misero linguaggio di programmazione ...

[Kleidemos]

Originariamente inviato da mjordan
Come vedi l'informatica è ben altro che conoscere un misero linguaggio di programmazione ...

e per questo che mi piacie

[mjordan]

Originariamente inviato da Kleidemos
e per questo che mi piacie

A te ti piacie, a me ... me piace ...

[Kleidemos]

ma all'uni si fa ?