Codifica di Huffman implementata con Red-Black

di
FilippoNino
il
1 risposte
F
FilippoNino
Pochi posts
Iscritto da
apr, 2015
Messaggi:
14

Codifica di Huffman implementata con Red-Black

Buonasera ragazzi , mi è stato assegnato un progetto in c++ dove devo implementare una codifica di Huffman con albero Red-Black. Ho dei piccoli dubbi , non a livello di codice o implementazione , ma a livello pratico,visto che oltre al progetto dovrò presentare una relazione con un esempio. So perfettamente come funziona la codifica di huffman, e allo stesso tempo so come creare un albero Red-Black, ma non riesco a capire come farli coincidere .

http://www.comefunziona.net/arg/compressione/4

Questo che vi ho postato è un piccolo esercizio dove devo codificare la frase CIAO MAMMA. L'ho capito perfettamente ma non so come possa implementarlo anche col Red Black. Forse mentre creo l'albero per la codica di Huffman , nello stesso momento devo incominciare a colorare le foglie di nero , i figli di ciascun nodo rosso colorarli di zero e altre regole riguardanti il Red Black?

Se fosse cosi però mi risulterebbe difficile capire a cosa mi possa servire l'inserimento o la cancellazione di un elemento :\.
Grazie in anticipo e scusate la confusione f

1 Risposte

  • D
    Della
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1305

    Re: Codifica di Huffman implementata con Red-Black

    Ciao, secondo me devi creare l'albero come se fosse red-black. Per cui provi ad inserire ogni nuovo nodo come se fosse rosso, e poi se causa problemi provi a fixarli.
    L'inserimento ti serve perché la creazione dell'albero di Huffman è un procedimento incrementale, in cui ogni volta aggiungi un nuovo nodo. Dal link che hai postato non si nota perché l'autore sa già come sarà fatto l'albero per cui dispone i vari nodi in modo opportuno. In realtà seguendo l'algoritmo vero e proprio salta fuori un albero estremamente sbilanciato (tutto a destra o a sinistra), per cui il fatto di usare un albero red-black ti permette di costruire un albero decisamente più bilanciato, simile a quello presente nel link.
    La cancellazione in realtà penso che non ti serva a tanto, perché non mi pare che nell'algoritmo si ricorra mai alla cancellazione di un nodo
Devi accedere o registrarti per scrivere nel forum
1 risposte