Question

huffman

תהא W=(w1,,wn)W = (w_1,\ldots,w_n) קבוצת תווים ותהא P=(p1,,pn)P = (p_1,\ldots,p_n) סדרת המשקלים המתאימים, המקיימת

p1>p2>>pn>p12 p_1 > p_2 > \dots > p_n > \frac{p_1}{2}

יהא TT עץ האפמן בינארי עבור PP. הוכיחו כי כל העלים בעץ נמצאים באותה רמה או בשתי רמות סמוכות.

1

Answers

נניח בשלילה שלא ונסתכל על שלושה עלים עם משקלים, pi>pj>pkp_i > p_j > p_k, כך ש-pjp_j ו-pkp_k אחים.

נסמן את העומקים שלהם ב-di,dj,dkd_i, d_j, d_k כך שמתקיים di+2dj=dkd_i + 2 \leq d_j = d_k.

נסתכל על העץ שמתקבל על ידי החלפת pip_i בצומת פנימי שלו שני בנים pi,pkp_i, p_k, וכמו כן נחליף את האבא של pjp_j ב-pjp_j.

השינוי במשקל העץ הוא לכל היותר pipkpj<0p_i - p_k - p_j < 0 - סתירה.

0
Feedback