Curs Algoritmul Huffman si procedura Merge

Algoritmul lui Huffman construieste un arbore binar de codificare optim. Demonstratie: Prin inductie dupa n = |E|. Pentru n  2 avem un singur arbore posibil si teorema e evident adevarata. Sa presupunem ca n  3. Notam cu TH arborele construit cu algoritmul lui Huffman pentru ponderile w1  w2  · · ·  wn. Algoritmul leaga intre ele frunzele e1 si e2 corespunzatoare ponderilor w1 si w2 si creeaza un arbore cu ponderea w1 + w2. Fie T0 H arborele construit de algoritmul lu Huffman din ponderile w1 + w2,w3, · · · ,wn. Avem relatia Cost(TH) = Cost(T0 H) + w1 + w2.

Conform ipotezei de inductie, T0Heste arbore optim pentru n - 1 frunze cu ponderile w1 + w2,w3, · · · ,wn. Fie Topt un arbore de codificare optim ce satisface Lema 2, adica frunzele e1 si e2 sunt frati in Topt. Fie T0 arborele obtinut din Topt inlocuind frunzele e1 si e2 si pe tatal lor cu o singura frunza de pondere w1 + w2. Apicand ipoteze de inductie Cost(T0 H ) Cost(T0)