9
Definitions et Proprietes des Arbres Huffmans
nDefinition: Un arbre Huffman est un arbre binaire qui minimise la somme des f(i)D(i) de toutes les feuilles i, ou f(i) est la frequence ou le poids de la feuille i et D(i) est la longueur du chemin allant de la
racine de l’arbre a la feuille i.
nProprietes:
nchaque node interne a deux
enfants
nLes elements ayant les frequences
les plus petites sont les elements places le plus loin de la racine,
nLes elements ayant les 2
frequences les plus petites sont frere et soeur.