שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2024 - עצים בינאריים

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

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

פתרון: התשובה היא **לא נכון**. הטענה כי בעץ בינארי עם $n$ קודקודים פנימיים יש $n+1$ עלים נכונה **אם ורק אם** העץ הוא **עץ בינארי מלא** (עץ שבו לכל קודקוד יש 0 או 2 בנים). מכיוון שהשאלה מתייחסת לעץ בינארי כללי, אשר יכול להכיל קודקודים עם בן יחיד, הטענה אינה נכונה בהכרח. **דוגמה נגדית:** נבחן עץ בינארי המורכב משורש ולו בן יחיד. * בעץ זה יש **קודקוד פנימי** אחד (השורש), ולכן $n=1$. * בעץ זה יש **עלה** אחד (הבן), ולכן מספר העלים הוא 1. * הטענה חוזה כי מספר העלים צריך להיות $n+1 = 1+1 = 2$. * מאחר ש-$1 \neq 2$, הטענה אינה מתקיימת עבור עץ זה. **הוכחה כללית:** יהי עץ בינארי $T$. נסמן: * $n$: מספר הקודקודים הפנימיים. * $L$: מספר העלים. * $N$: מספר הקודקודים הכולל. מתקיים $N=n+L$. * $E$: מספר הקשתות. בכל עץ, $E = N-1$. ניתן לספור את הקשתות גם על ידי סכימת דרגות היציאה של כל הקודקודים. לקודקוד פנימי יכולה להיות דרגת יציאה 1 או 2. נסמן: * $N_1$: מספר הקודקודים הפנימיים עם בן יחיד. * $N_2$: מספר הקודקודים הפנימיים עם שני בנים. מתקיים $n = N_1 + N_2$. סך הקשתות הוא $E = 1 \cdot N_1 + 2 \cdot N_2$. כעת נשווה את שתי הדרכים לחישוב $E$: $N-1 = N_1 + 2N_2$ נציב $N = n+L$ ו-$n=N_1+N_2$: $( (N_1+N_2) + L ) - 1 = N_1 + 2N_2$ $N_1+N_2+L-1 = N_1+2N_2$ $L-1 = N_2$ $L = N_2+1$ התוצאה מראה שמספר העלים תלוי רק במספר הקודקודים עם שני בנים. הטענה המקורית היא $L=n+1$. אם נציב את מה שמצאנו, נקבל: $N_2+1 = n+1 \implies N_2=n$. מאחר ש-$n=N_1+N_2$, התנאי $N_2=n$ מתקיים אם ורק אם $N_1=0$. כלומר, הטענה נכונה רק עבור עצים בינאריים שאין בהם קודקודים עם בן יחיד, שהם הגדרתם של עצים בינאריים מלאים. $\blacksquare$