Question

huffman

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

p_1 > p_2 > \dots > p_n > \frac{p_1}{2}

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

נניח בשלילה שלא ונסתכל על שלושה עלים עם משקלים, $p_i > p_j > p_k$ , כך ש- $p_j$ ו- $p_k$ אחים.

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

נסתכל על העץ שמתקבל על ידי החלפת $p_i$ בצומת פנימי שלו שני בנים $p_i, p_k$ , וכמו כן נחליף את האבא של $p_j$ ב- $p_j$ .

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