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

להלן הגדרת משפחת עצים בשם עצים רקורסיביים מסדר שני: $G_0 \quad G_1 \quad \forall i \geq 2: G_i$ סעיף א' (10 נקודות): הוכיחו באינדוקציה על המבנה שגובה העץ $G_i$ הוא $2i$ סעיף ב' (15 נקודות): הוכיחו כי המשפחה עצים רקורסיביים מסדר שני הם משפחה מאוזנת. תזכורת: משפחה של עצים נקראת מאוזנת אם מתקיים לכל עץ במשפחה גובה העץ הוא $O(\log n)$. כאשר, $n$ = מספר הצמתים בעץ.

רמז: ראשית, הגדירו במפורש את מבנה העצים $G_i$ כך שגובהם יקיים את הנתון $h(G_i)=2i$. לאחר מכן, מצאו נוסחת נסיגה למספר הצמתים $n_i$ והראו שהוא גדל באופן אקספוננציאלי ביחס ל-$i$.

פתרון: מאחר והגדרת משפחת העצים חסרה בשאלה, נניח את ההגדרה הבאה אשר מתיישבת עם הנתונים: - $G_0$ הוא עץ המכיל צומת בודד (עלה). - $G_1$ הוא עץ המהווה מסלול פשוט באורך 2 (מכיל 3 צמתים). - לכל $i \geq 2$, העץ $G_i$ נבנה באופן הבא: ניקח שורש חדש $r$, שיהיה לו בן יחיד $c$. שני בניו של $c$ יהיו השורשים של העתקים של העצים $G_{i-1}$ ו-$G_{i-2}$. **סעיף א': הוכחת גובה העץ** נוכיח באינדוקציה שלמה על $i$ כי גובה העץ $G_i$, המסומן $h(G_i)$, הוא $2i$ לכל $i \ge 0$. **בסיס האינדוקציה:** - עבור $i=0$: על פי הגדרתנו, $G_0$ הוא צומת בודד, וגובהו הוא $h(G_0) = 0$. מתקיים $2 \cdot 0 = 0$. הטענה נכונה. - עבור $i=1$: על פי הגדרתנו, $G_1$ הוא מסלול באורך 2, וגובהו הוא $h(G_1) = 2$. מתקיים $2 \cdot 1 = 2$. הטענה נכונה. **הנחת האינדוקציה:** נניח כי לכל $k$ טבעי המקיים $0 \le k < i$ (עבור $i \ge 2$), מתקיים $h(G_k) = 2k$. **צעד האינדוקציה:** נוכיח את נכונות הטענה עבור $i$. על פי מבנה העץ $G_i$ עבור $i \ge 2$: $h(G_i) = 2 + \max(h(G_{i-1}), h(G_{i-2}))$ מכיוון ש-$i \ge 2$, מתקיים $0 \le i-2 < i$ ו-$0 \le i-1 < i$. לכן, ניתן להשתמש בהנחת האינדוקציה עבור $G_{i-1}$ ו-$G_{i-2}$: $h(G_{i-1}) = 2(i-1)$ $h(G_{i-2}) = 2(i-2)$ נציב בנוסחת הגובה: $h(G_i) = 2 + \max(2(i-1), 2(i-2))$ מכיוון ש-$i-1 > i-2$, מתקיים $2(i-1) > 2(i-2)$, ולכן: $h(G_i) = 2 + 2(i-1) = 2 + 2i - 2 = 2i$ הוכחנו כי הטענה נכונה עבור $i$. על פי עקרון האינדוקציה השלמה, $h(G_i)=2i$ לכל $i \ge 0$. $\blacksquare$ **סעיף ב': הוכחת איזון המשפחה** כדי להוכיח שהמשפחה מאוזנת, עלינו להראות שמתקיים $h(G_i) = O(\log n_i)$, כאשר $n_i$ הוא מספר הצמתים בעץ $G_i$. ראשית, נמצא נוסחת נסיגה עבור $n_i$: - $n_0 = 1$ (צומת בודד). - $n_1 = 3$ (מסלול באורך 2). - לכל $i \ge 2$, לפי הבנייה, $G_i$ מורכב משני צמתים חדשים (השורש ובנו) ומהצמתים של $G_{i-1}$ ו-$G_{i-2}$. לכן: $n_i = 2 + n_{i-1} + n_{i-2}$ כעת, נמצא חסם תחתון עבור $n_i$. נשים לב כי $n_i$ היא סדרה מונוטונית עולה ($n_i > n_{i-1}$ לכל $i \ge 1$). $n_i = 2 + n_{i-1} + n_{i-2} > n_{i-1} + n_{i-2}$ היחס $n_i > n_{i-1} + n_{i-2}$ דומה מאוד לסדרת פיבונאצ'י. ניתן להראות (למשל באינדוקציה) ש-$n_i$ גדל באופן **אקספוננציאלי**. בפרט, קיים קבוע $c > 1$ כך ש-$n_i = \Omega(c^i)$. לצורך ההוכחה, נראה כי $n_i > (\frac{3}{2})^i$ לכל $i \ge 2$: - בסיס: $n_2 = 2+n_1+n_0 = 2+3+1 = 6$. $(\frac{3}{2})^2 = \frac{9}{4} = 2.25$. $6 > 2.25$, הבסיס מתקיים. - הנחה: נניח $n_k > (\frac{3}{2})^k$ לכל $2 \le k < i$. - צעד: $n_i = 2 + n_{i-1} + n_{i-2} > n_{i-1} + n_{i-2} > (\frac{3}{2})^{i-1} + (\frac{3}{2})^{i-2} = (\frac{3}{2})^{i-2}(\frac{3}{2} + 1) = (\frac{3}{2})^{i-2}(\frac{5}{2})$. נרצה להראות שזה גדול מ-$(\frac{3}{2})^i = (\frac{3}{2})^{i-2}(\frac{3}{2})^2 = (\frac{3}{2})^{i-2}(\frac{9}{4})$. מכיוון ש-$2.5 = \frac{5}{2} > \frac{9}{4} = 2.25$, אי-השוויון מתקיים. לכן, $n_i > (\frac{3}{2})^i$ לכל $i \ge 2$. קיבלנו חסם תחתון אקספוננציאלי למספר הצמתים: $n_i = \Omega((\frac{3}{2})^i)$. ניקח לוגריתם על שני האגפים: $\log(n_i) = \Omega(\log((\frac{3}{2})^i)) = \Omega(i \cdot \log(\frac{3}{2})) = \Omega(i)$ לכן, קיים קבוע $c_1$ כך ש-$c_1 \cdot i \le \log(n_i)$. מכאן ש-$i \le \frac{1}{c_1} \log(n_i)$, כלומר $i = O(\log n_i)$. מסעיף א' ידוע לנו כי $h(G_i) = 2i$. נציב את הקשר שמצאנו: $h(G_i) = 2i = 2 \cdot O(\log n_i) = O(\log n_i)$ הראינו כי גובה העץ חסום אסימפטוטית על ידי לוגריתם של מספר הצמתים, ולכן משפחת העצים היא **מאוזנת**. $\blacksquare$