שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2019 - ערימות

ערמה טרנרית הינה ערמה דומה לערמה בינרית אלא שלכל צומת יש (עד) 3 בנים. נניח להלן שמדובר בערמת מקסימום טרנרית. כמה עלים יש בערמה טרנרית?

רמז: עלים הם צמתים ללא בנים. בערמה בת $n$ איברים, חשבו כמה צמתים הם פנימיים (יש להם לפחות בן אחד).

פתרון: בערמה טרנרית בת $n$ איברים: הצומת האחרון (באינדקס $n$) הוא הצומת הימני ביותר ברמה התחתונה. אביו נמצא באינדקס $\lfloor(n+1)/3\rfloor$. כל הצמתים מאינדקס $\lfloor(n+1)/3\rfloor + 1$ עד $n$ הם עלים. לכן מספר העלים הוא: $$n - \left\lfloor \frac{n+1}{3} \right\rfloor$$ בקירוב, מספר העלים הוא $\lceil 2n/3 \rceil$ (כשני שלישים מהצמתים הם עלים, בדומה לחצי בערמה בינרית).