[c/c++] utilità degli alberi binari

[Gen.Web]

Qualcuno mi può dire l'utilità di queste strutture? Perchè senza una ragione non riesco a studiarli :muro:

[cionci]

Ad esempio sono utili in algoritmi di ordinamento (heap sort)... Nelle strutture di memorizzazione dei database (BTree, B+Tree)...
Vengono usati anche in alcuni algoritmi di codifica/compressione...codifica di Huffman...algoritmo usato in praticamente tutti i sistemi di compressione delle informazioni...
E poi chi più ne ha più ne metta...non è certo una struttura poco usata !!!

[Luc@s]

filesystem:D

[jonson]

Originariamente inviato da Gen.Web
Qualcuno mi può dire l'utilità di queste strutture? Perchè senza una ragione non riesco a studiarli :muro:

concordo :cincin:

è senza dubbio una delle parti più rognose, almeno del mio corso

[Gen.Web]

ragazzi qualcuno ha qualche guida FATTA BENE sugli alberi? Ci hanno fatto comprare un libro sul c++ dove praticamente non c'è traccia di code, alberi, pile, ecc...
Il 22 ho l'esame :mc: :cry:

[jonson]

Originariamente inviato da Gen.Web
ragazzi qualcuno ha qualche guida FATTA BENE sugli alberi? Ci hanno fatto comprare un libro sul c++ dove praticamente non c'è traccia di code, alberi, pile, ecc...
Il 22 ho l'esame :mc: :cry:

io uso un libro in Inglese dove ci sono tutte le strutture dati principali. il prof del mio corso ha ricopiato ogni capitolo del libro in presentazioni powerpoint. se ti interessano dimmelo che ti spedisco quello che ti serve e sono complete di codice e di analisi per tutte le funzioni implementate . :D

[Luc@s]

Originariamente inviato da jonson
io uso un libro in Inglese dove ci sono tutte le strutture dati principali. il prof del mio corso ha ricopiato ogni capitolo del libro in presentazioni powerpoint. se ti interessano dimmelo che ti spedisco quello che ti serve e sono complete di codice e di analisi per tutte le funzioni implementate . :D


kleidemos@altervista.org

Tnk 1000000000000000000000000000000000000000000000000000

[jonson]

Originariamente inviato da Luc@s
kleidemos@altervista.org

Tnk 1000000000000000000000000000000000000000000000000000

ti interessano solo gli alberi binari? non per niente ma ogni presentazione è sui 500-600 k e io con il 56K:cry:
cmq dimmi cosa ti interessa che cerco di spedirtelo al + presto

[Luc@s]

Originariamente inviato da jonson
ti interessano solo gli alberi binari? non per niente ma ogni presentazione è sui 500-600 k e io con il 56K:cry:
cmq dimmi cosa ti interessa che cerco di spedirtelo al + presto

alberi binari.
Tnk 10000000000000000000000000000000000 ancora

[Gen.Web]

mi accodo... alberi binari :D
simgames@libero.it

[Luc@s]

Originariamente inviato da Gen.Web
mi accodo... alberi binari :D
simgames@libero.it

Se me li manda poi te le passo io(ADSL rulez :D )

[jonson]

Originariamente inviato da Luc@s
Se me li manda poi te le passo io(ADSL rulez :D )

adesso ti mando quella degli alberi binari e alberi binari di ricerca che è tutto in 1

ah dimenticavo di dirvi che è tutto in inglese, cmq molto semplice e nn ci sono paroloni

[Gen.Web]

Originariamente inviato da jonson
adesso ti mando quella degli alberi binari e alberi binari di ricerca che è tutto in 1

ah dimenticavo di dirvi che è tutto in inglese, cmq molto semplice e nn ci sono paroloni


tutto di guadagnato, si impara :cool:

[Mezzetti0903]

Mi posso aggregar??

gian.mezz@tin.it



grazie!!!

[jonson]

chiedi a luc@s, è lui che sta smistando :D

[mardeg]

guardate questo programma qualcuno mi sa spiegare bene le istruzioni evidenziate in rosso


#include <iostream>
using namespace std;

class tree
{
private:
int dato;
tree *left;
tree *right;

public:
tree(void);
~tree(void);
void set(int numero);
int get(void);
tree *get_left(void);
tree *get_right(void);
void point_at_left(tree *where_to_point);
void point_at_right(tree *where_to_point);
};

tree::tree(void)
{
dato=1;
left=NULL;
right=NULL;
}

tree::~tree(void)
{
dato=0;
left=NULL;
right=NULL;
}

void tree::set(int numero)
{
dato=numero;
}

int tree::get(void)
{
return dato;
}

tree *tree::get_left(void)
{
return left;
}

tree *tree::get_right(void)
{
return right;
}

void tree::point_at_left(tree *where_to_point)
{
left=where_to_point;
}

void tree::point_at_right(tree *where_to_point)
{
right=where_to_point;
}

tree *rootPtr=NULL;

void inserisci(tree *startPtr,int numero);
void simmetrica(tree *startPtr);

void inserisci(tree *startPtr,int numero)
{
tree *newPtr;

if(numero<startPtr->get())
{
if ((startPtr->get_left())==NULL)
{
newPtr=new(tree);
newPtr->set(numero);
startPtr->point_at_left(newPtr);
}

else
inserisci(startPtr->get_left(),numero);
}

else if(numero>startPtr->get())
{
if((startPtr->get_right())==NULL)
{
newPtr=new(tree);
newPtr->set(numero);
startPtr->point_at_right(newPtr);
}

else
inserisci(startPtr->get_right(),numero);
}

else
cout << "Elemento duplicato NON INSERITO" << endl;
}

void simmetrica(tree *startPtr)
{
if (startPtr!=NULL)
{
simmetrica(startPtr->get_left());
cout << "Nodo-> " << startPtr->get() << endl;
simmetrica(startPtr->get_right());
}
}


int
main(void)
{
int elem=9;
tree *tempPtr;

do{
cout << "Inserisci elemento(-1 per terminare) -> ";
cin >> elem;
if(elem!=-1)
{
if(rootPtr==NULL)
{
tempPtr=new(tree);
tempPtr->set(elem);
rootPtr=tempPtr;
}

else
inserisci(rootPtr,elem);
}

}while(elem!=-1);

simmetrica(rootPtr);

system("pause");
return 0;
}

[banryu79]

Per prima cosa: usa il tag "CODE" per pubblicare del codice, serve per non perdere l'dentazione:

[cut]

// definizione metodo "inserisci"
void inserisci(tree *startPtr,int numero)
{
tree *newPtr;

if(numero<startPtr->get())
{
if ((startPtr->get_left())==NULL)
{
newPtr=new(tree);
newPtr->set(numero);
startPtr->point_at_left(newPtr);
}
else
inserisci(startPtr->get_left(),numero);
}
else if(numero>startPtr->get())
{
if((startPtr->get_right())==NULL)
{
newPtr=new(tree);
newPtr->set(numero);
startPtr->point_at_right(newPtr);
}
else
inserisci(startPtr->get_right(),numero);
}
else
cout << "Elemento duplicato NON INSERITO" << endl;
}


// definizione metodo "simmetrica"
void simmetrica(tree *startPtr)
{
if (startPtr!=NULL)
{
simmetrica(startPtr->get_left());
cout << "Nodo-> " << startPtr->get() << endl;
simmetrica(startPtr->get_right());
}
}
[cut]


Detta in due parole: la funzione "inserisci" implementa l'inserimento di un elemento in un albero binario, evitando l'inserimento di elementi duplicati.

Parte controllando se l'elemento da inserire è minore o maggiore dell'elemento del nodo indicato (startPtr): se è minore e startPtr non ha un figlio sinistro allora crea un nuovo nodo che contiene l'elemento da inserire e lo collega come figlio sinistro di startPtr; se invece stratPtr ha già un figlio sinistro, "inserisci" chiama ricorsivamente se stesso passando come nodo di riferimento il figlio sinistro di startPtr.
Allo stesso modo, se l'elemento da inserire risulta maggiore di startPtr e startPtr non ha un figlio destro allora crea un nuovo nodo che contiene l'elemento da inserire e lo collega come figlio destro di startPtr; se invece stratPtr ha già un figlio destro, "inserisci" chiama ricorsivamente se stesso passando come nodo di riferimento il figlio destro di startPtr.
Infine, se l'elemendo da inserire non è ne minore ne maggiore dell'elemento di startPtr, allora "inserisci" non lo inserisce (niente duplicati) e stampa un messaggio.

La funzione "simmetrica" invece stampa il valore di tutti i nodi figli a partire da un nodo radice (quello passato come parametro alla funzione) esplorando l'albero con una visita inorder (nodo figlio sinistro, nodo padre, nodo figlio destro). Anche questa funzione è ricorsiva.

Per saperne di più sulle modalità di tree traversal, qui c'è qualcosa (http://en.wikipedia.org/wiki/Tree_traversal).

[fero86]

Qualcuno mi può dire l'utilità di queste strutture? Perchè senza una ragione non riesco a studiarli :muro: nel caso generale servono a rappresentare dati che hanno quel tipo di correlazione, cioé dati organizzati gerarchicamente dove ciascuna entitá é legata ad altre due.

nelle loro varianti hanno anche delle grosse utilitá algoritmiche: esistono infatti gli alberi binari ordinati che permettono nel caso migliore di trovare un'informazione in tempo logaritmico anziché lineare; poi siccome quello é solo il caso migliore, mentre nel caso peggiore il tempo é sempre lineare, esistono gli alberi AVL anche noti come autobilancianti, per i quali il tempo di ricerca é logaritmico in ogni caso. infine esiste una generalizzazione degli alberi AVL che sono gli alberi RB (red-black) e permettono una maggiore efficienza in fase di inserzione e rimozione al costo di potenziali rallentamenti molto contenuti in fase di ricerca.



filesystem:D pietá! :asd:
per i filesystem si usano tutt'al piu i B-trees.

[fero86]

altra utilitá degli alberi binari: esiste una notazione che permette ad essi di rappresentare alberi N-ari. infatti un albero N-ario puó essere rappresentanto come un grafo in cui ogni nodo fa riferimento al primo dei suoi figli ed ogni figlio da riferimento al prossimo dei suoi fratelli (quindi per memorizzare i figli si usa una lista linkata). di conseguenza ogni nodo fa riferimento ad altri due nodi, il primo figlio e il fratello, e quindi si tratta di un albero binario.

l'algoritmo di traduzione appena descritto é praticamente una biezione tra l'insieme degli alberi binari e quello degli alberi N-ari.

[banryu79]

Che fai fero, necoposting? :D
Comunque ottime le tue integrazioni, almeno se in futuro qualcuno incapperà nel topic troverà molte indicazioni. A tal proposito, aggiungo alla tua descrizione dei vari tipi di albero un articolo di Robert Sedgewick su una variante che lui chiama Left Leaning Red-Black Trees (http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf).

[fero86]

Che fai fero, necoposting? :D oh Gesu, non avevo minimamente guardato la data del post originale :asd: