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

קורס: מבני נתונים

אוניברסיטה: אוניברסיטת בר-אילן

שנה: 2026

סמסטר: א

נושאים: רקורסיה, נוסחת נסיגה, הוכחת נכונות, סימון אסימפטוטי, Big-O, עצים בינאריים

רמת קושי: בינוני

להלן הגדרת משפחת עצים בשם **עצים רקורסיביים מסדר שני** $G_0, G_1, G_2, \ldots$ (ראו תרשים): [IMAGE] **סעיף א' (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$ בעל שני בנים, $r_L$ ו-$r_R$. לבן השמאלי $r_L$ יש בן יחיד שהוא השורש של עותק של העץ $G_{i-2}$, ולבן הימני $r_R$ יש בן יחיד שהוא השורש של עותק של העץ $G_{i-1}$. **סעיף א': הוכחת גובה העץ** נוכיח באינדוקציה שלמה על $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$, מהשורש $r$ יורדים שתי קשתות עד לשורש של תת-עץ רקורסיבי (קשת אל הבן $r_L$ או $r_R$, ומשם קשת אל שורש העץ הרקורסיבי). לכן: $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$ מורכב משלושה צמתים חדשים (השורש $r$ ושני בניו $r_L, r_R$) ומהצמתים של העתקי $G_{i-1}$ ו-$G_{i-2}$. לכן: $n_i = 3 + n_{i-1} + n_{i-2}$ כעת, נמצא חסם תחתון עבור $n_i$. נשים לב כי $n_i$ היא סדרה מונוטונית עולה ($n_i > n_{i-1}$ לכל $i \ge 1$). $n_i = 3 + 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 = 3+n_1+n_0 = 3+3+1 = 7$. $(\frac{3}{2})^2 = \frac{9}{4} = 2.25$. $7 > 2.25$, הבסיס מתקיים. - הנחה: נניח $n_k > (\frac{3}{2})^k$ לכל $2 \le k < i$. - צעד: $n_i = 3 + 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$

להלן הגדרת משפחת עצים בשם עצים רקורסיביים מסדר שני

G_{0}, G_{1}, G_{2}, \dots

(ראו תרשים):

תרשים לשאלה

סעיף א' (10 נקודות)
הוכיחו באינדוקציה על המבנה כי גובה העץ

G_{i}

הוא

2 i

.

סעיף ב' (15 נקודות)
הוכיחו כי משפחת העצים הרקורסיביים מסדר שני היא משפחה מאוזנת.

תזכורת: משפחה של עצים נקראת מאוזנת אם לכל עץ במשפחה גובה העץ הוא

O (lo g n)

, כאשר

n

הוא מספר הצמתים בעץ.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2026 · סמסטר א

★★★★★

רקורסיהנוסחת נסיגההוכחת נכונותסימון אסימפטוטיBig-Oעצים בינאריים

ראשית, הגדירו במפורש את מבנה העצים

G_{i}

כך שגובהם יקיים את הנתון

h (G_{i}) = 2 i

. לאחר מכן, מצאו נוסחת נסיגה למספר הצמתים

n_{i}

והראו שהוא גדל באופן אקספוננציאלי ביחס ל-

i

על פי התרשים, משפחת העצים מוגדרת כך:

$G_{0}$ הוא עץ המכיל צומת בודד (עלה).
$G_{1}$ הוא מסלול פשוט באורך 2 (מכיל 3 צמתים).
לכל $i \geq 2$ , העץ $G_{i}$ נבנה כך: שורש $r$ בעל שני בנים, $r_{L}$ ו- $r_{R}$ . לבן השמאלי $r_{L}$ יש בן יחיד שהוא השורש של עותק של העץ $G_{i - 2}$ , ולבן הימני $r_{R}$ יש בן יחיד שהוא השורש של עותק של העץ $G_{i - 1}$ .

סעיף א': הוכחת גובה העץ

נוכיח באינדוקציה שלמה על

i

כי גובה העץ

G_{i}

, המסומן

h (G_{i})

, הוא

2 i

לכל

i \geq 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 \leq k < i

(עבור

i \geq 2

), מתקיים

h (G_{k}) = 2 k

.

צעד האינדוקציה:
נוכיח את נכונות הטענה עבור

i

. על פי מבנה העץ

G_{i}

עבור

i \geq 2

, מהשורש

r

יורדים שתי קשתות עד לשורש של תת-עץ רקורסיבי (קשת אל הבן

r_{L}

או

r_{R}

, ומשם קשת אל שורש העץ הרקורסיבי). לכן:

h (G_{i}) = 2 + max (h (G_{i - 1}), h (G_{i - 2}))

מכיוון ש-

i \geq 2

, מתקיים

0 \leq i - 2 < i

ו-

0 \leq 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 + 2 i - 2 = 2 i

הוכחנו כי הטענה נכונה עבור

i

. על פי עקרון האינדוקציה השלמה,

h (G_{i}) = 2 i

לכל

i \geq 0

■

סעיף ב': הוכחת איזון המשפחה

כדי להוכיח שהמשפחה מאוזנת, עלינו להראות שמתקיים

h (G_{i}) = O (lo g n_{i})

, כאשר

n_{i}

הוא מספר הצמתים בעץ

G_{i}

.

ראשית, נמצא נוסחת נסיגה עבור

n_{i}

$n_{0} = 1$ (צומת בודד).
$n_{1} = 3$ (מסלול באורך 2).
לכל $i \geq 2$ , לפי הבנייה $G_{i}$ מורכב משלושה צמתים חדשים (השורש $r$ ושני בניו $r_{L}, r_{R}$ ) ומהצמתים של העתקי $G_{i - 1}$ ו- $G_{i - 2}$ . לכן:

n_{i} = 3 + n_{i - 1} + n_{i - 2}

כעת, נמצא חסם תחתון עבור

n_{i}

. נשים לב כי

n_{i}

היא סדרה מונוטונית עולה (

n_{i} > n_{i - 1}

לכל

i \geq 1

n_{i} = 3 + 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} = Ω (c^{i})

.

לצורך ההוכחה, נראה כי

n_{i} > (\frac{3}{2})^{i}

לכל

i \geq 2

בסיס: $n_{2} = 3 + n_{1} + n_{0} = 3 + 3 + 1 = 7$ . $(\frac{3}{2})^{2} = \frac{9}{4} = 2.25$ . $7 > 2.25$ , הבסיס מתקיים.
הנחה: נניח $n_{k} > (\frac{3}{2})^{k}$ לכל $2 \leq k < i$ .
צעד: $n_{i} = 3 + 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 \geq 2

.

קיבלנו חסם תחתון אקספוננציאלי למספר הצמתים:

n_{i} = Ω ((\frac{3}{2})^{i})

.
ניקח לוגריתם על שני האגפים:

lo g (n_{i}) = Ω (lo g ((\frac{3}{2})^{i})) = Ω (i \cdot lo g (\frac{3}{2})) = Ω (i)

לכן, קיים קבוע

c_{1}

כך ש-

c_{1} \cdot i \leq lo g (n_{i})

. מכאן ש-

i \leq \frac{1}{c _{1}} lo g (n_{i})

, כלומר

i = O (lo g n_{i})

.

מסעיף א' ידוע לנו כי

h (G_{i}) = 2 i

. נציב את הקשר שמצאנו:

h (G_{i}) = 2 i = 2 \cdot O (lo g n_{i}) = O (lo g n_{i})

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

■

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