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

עץ פיבונצ'י מסדר $n$, שמסומן $T_n$, מוגדר ע"י: $T_0$ - העץ הריק, $T_1$ - עץ שרק מכיל קדקוד אחד, $T_n$ עבור $n>1$: עץ בינארי עם שורש ובן שמאלי שהוא $T_{n-2}$ ובן ימני שהוא $T_{n-1}$. א. צייר/י את $T_4$. ב. הוכח/י באינדוקציה על המבנה שמספר הקדקודים בעץ $T_n$ הוא $F_{n+2}-1$, כאשר $F_i$ היא סדרת פיבונצ'י המוגדרת ע"י: $$F_0=0 \quad F_1=1 \quad F_i=F_{i-1}+F_{i-2} \quad i>1$$ ג. מה הקשר בין עץ פיבונצ'י לעצי AVL?

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

פתרון: א. **עץ פיבונאצ'י** $T_4$ בנוי משורש, כאשר תת-העץ השמאלי שלו הוא $T_2$ ותת-העץ הימני שלו הוא $T_3$. נפרט את מבנה העץ: * $T_0$ הוא עץ ריק. * $T_1$ הוא עץ עם צומת בודד (עלה). * $T_2$ הוא עץ עם שורש, תת-עץ שמאלי ריק ($T_0$), ותת-עץ ימני $T_1$. * $T_3$ הוא עץ עם שורש, תת-עץ שמאלי $T_1$, ותת-עץ ימני $T_2$. תיאור טקסטואלי של $T_4$: ``` R(T4) / \ R(T2) R(T3) \ / \ R(T1) R(T1) R(T2) \ R(T1) ``` מספר הצמתים ב-$T_4$ הוא 7. ב. נוכיח באינדוקציה על $n$ כי מספר הקדקודים בעץ $T_n$, שנסמן ב-$N(n)$, הוא $F_{n+2}-1$. **בסיס האינדוקציה:** * עבור $n=0$: $N(0) = 0$ (עץ ריק). לפי הנוסחה: $F_{0+2}-1 = F_2-1 = 1-1=0$. הטענה נכונה. * עבור $n=1$: $N(1) = 1$ (צומת בודד). לפי הנוסחה: $F_{1+2}-1 = F_3-1 = 2-1=1$. הטענה נכונה. **הנחת האינדוקציה:** נניח שהטענה נכונה עבור כל $k < n$. כלומר, $N(k) = F_{k+2}-1$ לכל $k < n$. **צעד האינדוקציה:** נוכיח את נכונות הטענה עבור $n$ (כאשר $n > 1$). לפי ההגדרה הרקורסיבית של עץ פיבונאצ'י, מספר הצמתים ב-$T_n$ הוא: $N(n) = 1 + N(n-1) + N(n-2)$ כעת, מכיוון ש-$n-1 < n$ ו-$n-2 < n$, ניתן להשתמש בהנחת האינדוקציה עבור $N(n-1)$ ו-$N(n-2)$: $N(n-1) = F_{(n-1)+2} - 1 = F_{n+1} - 1$ $N(n-2) = F_{(n-2)+2} - 1 = F_{n} - 1$ נציב חזרה בנוסחה עבור $N(n)$: $N(n) = 1 + (F_{n+1} - 1) + (F_n - 1)$ $N(n) = F_{n+1} + F_n - 1$ לפי ההגדרה של סדרת פיבונאצ'י, $F_{n+2} = F_{n+1} + F_n$. לכן: $N(n) = F_{n+2} - 1$ הוכחנו את צעד האינדוקציה, ולכן הטענה נכונה לכל $n \ge 0$. $\blacksquare$ ג. הקשר בין עצי פיבונאצ'י ל**עצי AVL** הוא שעצי פיבונאצ'י מייצגים את המקרה הגרוע ביותר של עץ AVL מבחינת יחס גובה-מספר צמתים. 1. **עץ פיבונאצ'י הוא עץ AVL:** ניתן להראות (באינדוקציה) כי גובהו של עץ $T_n$ (עבור $n \ge 1$) הוא $n-1$. עבור כל צומת פנימי בעץ $T_n$ שהוא שורש של תת-עץ מהצורה $T_k$ ($k>1$), תת-העץ השמאלי שלו הוא $T_{k-2}$ (גובה $k-3$) ותת-העץ הימני שלו הוא $T_{k-1}$ (גובה $k-2$). לכן, **גורם האיזון** (Balance Factor) שלו, המוגדר כהפרש בין גובה תת-העץ הימני לגובה תת-העץ השמאלי, הוא $(k-2) - (k-3) = 1$. מכיוון שגורם האיזון של כל צומת הוא $1$ (או $0$ או $-1$), עץ פיבונאצ'י הוא עץ AVL חוקי. 2. **מקרה גרוע (Worst Case):** עצי פיבונאצ'י הם עצי ה-AVL ה"רזים" ביותר. כלומר, עבור גובה נתון $h$, עץ פיבונאצ'י $T_{h+1}$ הוא עץ AVL בעל מספר הצמתים המינימלי האפשרי. תכונה זו משמשת בהוכחת החסם הלוגריתמי על גובהו של עץ AVL. מכיוון שעץ AVL עם $N$ צמתים הוא תמיד "מלא" יותר מעץ פיבונאצ'י עם אותו גובה, ניתן להראות שגובהו של עץ AVL עם $N$ צמתים הוא $O(\log N)$.