שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2021 - הוכחת נכונות

עץ טרינרי מושלם הוא עץ שלכל קודקוד פנימי בו יש 3 בנים. הוכיחו את הטענות הבאות באינדוקציה על מבנה העץ: א. לעץ טרינרי מושלם תמיד מספר עלים אי זוגי. ב. לעץ טרינרי מושלם עם $n$ עלים יש $(n-1)/2$ קודקודים פנימיים.

רמז: בשני הסעיפים, השתמשו באינדוקציה על מבנה העץ. צעד האינדוקציה יתייחס לעץ שהשורש שלו הוא אב לשלושה תתי-עצים, שכל אחד מהם הוא עץ טרינרי מושלם קטן יותר.

פתרון: א. **הוכחה באינדוקציה על מבנה העץ:** **בסיס האינדוקציה:** **עץ טרינרי מושלם** הקטן ביותר הוא עץ המכיל קודקוד בודד (השורש). קודקוד זה הוא גם עלה. מספר העלים בעץ זה הוא 1, שהוא מספר אי-זוגי. לכן, הטענה מתקיימת עבור בסיס האינדוקציה. **הנחת האינדוקציה:** נניח שהטענה נכונה עבור כל עץ טרינרי מושלם $T'$ שגודלו קטן מזה של עץ $T$ כלשהו. כלומר, לכל עץ כזה יש מספר עלים אי-זוגי. **צעד האינדוקציה:** יהי $T$ עץ טרינרי מושלם. אם $T$ הוא עלה בודד, הטענה מתקיימת (לפי בסיס האינדוקציה). אם לא, לשורש של $T$ יש 3 בנים, שהם שורשים של שלושה תתי-עצים, $T_1, T_2, T_3$. מכיוון ש-$T$ הוא עץ טרינרי מושלם, גם $T_1, T_2, T_3$ הם עצים טרינריים מושלמים, וכל אחד מהם קטן מ-$T$. נסמן ב-$L(T)$ את מספר העלים בעץ $T$. העלים של $T$ הם איחוד העלים של תתי-העצים שלו, ולכן: $L(T) = L(T_1) + L(T_2) + L(T_3)$ לפי **הנחת האינדוקציה**, מספר העלים בכל אחד מתתי-העצים $T_1, T_2, T_3$ הוא אי-זוגי. כלומר, קיימים שלמים אי-שליליים $k_1, k_2, k_3$ כך ש: $L(T_1) = 2k_1 + 1$ $L(T_2) = 2k_2 + 1$ $L(T_3) = 2k_3 + 1$ נציב ונקבל: $L(T) = (2k_1 + 1) + (2k_2 + 1) + (2k_3 + 1) = 2k_1 + 2k_2 + 2k_3 + 3 = 2(k_1 + k_2 + k_3 + 1) + 1$ הביטוי האחרון הוא מהצורה $2k+1$ כאשר $k = k_1 + k_2 + k_3 + 1$, ולכן הוא מספר אי-זוגי. הוכחנו כי מספר העלים בעץ $T$ הוא אי-זוגי. $\blacksquare$ ב. **הוכחה באינדוקציה על מבנה העץ:** **בסיס האינדוקציה:** **עץ טרינרי מושלם** הקטן ביותר הוא עץ המכיל קודקוד בודד (עלה). בעץ זה יש $n=1$ עלים ו-0 קודקודים פנימיים. על פי הנוסחה, מספר הקודקודים הפנימיים הוא $(1-1)/2 = 0$. לכן, הטענה מתקיימת עבור בסיס האינדוקציה. **הנחת האינדוקציה:** נניח שהטענה נכונה עבור כל עץ טרינרי מושלם $T'$ שגודלו קטן מזה של עץ $T$ כלשהו. כלומר, אם ל-$T'$ יש $k$ עלים, אז יש לו $(k-1)/2$ קודקודים פנימיים. **צעד האינדוקציה:** יהי $T$ עץ טרינרי מושלם עם $n$ עלים. אם $n=1$, הטענה מתקיימת (לפי בסיס האינדוקציה). אם $n > 1$, אז השורש של $T$ הוא **קודקוד פנימי**. לשורש יש 3 בנים, שהם שורשים של שלושה תתי-עצים, $T_1, T_2, T_3$. כל אחד מהם הוא עץ טרינרי מושלם וקטן מ-$T$. נסמן ב-$n_1, n_2, n_3$ את מספר העלים בתתי-העצים $T_1, T_2, T_3$ בהתאמה. נסמן ב-$i_1, i_2, i_3$ את מספר הקודקודים הפנימיים בתתי-העצים $T_1, T_2, T_3$ בהתאמה. מספר העלים הכולל ב-$T$ הוא $n = n_1 + n_2 + n_3$. מספר הקודקודים הפנימיים הכולל ב-$T$, נסמנו $I(T)$, הוא 1 (השורש) ועוד סכום הקודקודים הפנימיים בתתי-העצים: $I(T) = 1 + i_1 + i_2 + i_3$ לפי **הנחת האינדוקציה**, מכיוון שכל תת-עץ קטן מ-$T$, הטענה חלה עליהם: $i_1 = (n_1 - 1)/2$ $i_2 = (n_2 - 1)/2$ $i_3 = (n_3 - 1)/2$ נציב את הביטויים הללו במשוואה עבור $I(T)$: $I(T) = 1 + \frac{n_1 - 1}{2} + \frac{n_2 - 1}{2} + \frac{n_3 - 1}{2}$ $I(T) = 1 + \frac{(n_1 - 1) + (n_2 - 1) + (n_3 - 1)}{2}$ $I(T) = 1 + \frac{n_1 + n_2 + n_3 - 3}{2}$ מכיוון ש-$n = n_1 + n_2 + n_3$, נציב ונקבל: $I(T) = 1 + \frac{n - 3}{2} = \frac{2}{2} + \frac{n - 3}{2} = \frac{2 + n - 3}{2} = \frac{n-1}{2}$ הוכחנו כי לעץ $T$ עם $n$ עלים יש $(n-1)/2$ קודקודים פנימיים. $\blacksquare$