מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים

חסם תחתון על אורך המסלול הארוך ביותר

שאלה

אנא הוכח שבכל עץ חיפוש בינרי המכיל $\displaystyle n$ מפתחות שונים זה מזה, יש לפחות עלה אחד כך שאורך המסלול משורש העץ לעלה הוא $\displaystyle \Omega (\log(n))$.

כדאי לדעת: שים לב להשלכה - סיבוכיות חיפוש בעץ במקרה הגרוע היא $\displaystyle \Omega (\log(n))$.

תשובה

הוכחה א'

נגדיר את אורך המסלול הארוך ביותר כ$\displaystyle h$, ונשאל את השאלה הבאה: בעץ שגובהו (אורך המסלול הארוך ביותר משורש לעלה) $\displaystyle h$, כמה צמתים אפשר לשים לכל היותר?

נשים לב שאם יש צומת שאין לו שני ילדים, אפשר לבנות עץ גדול יותר על ידי הוספת ילד אליו. מכאן נקבל שהעץ המכיל את מספר הצמתים המקסימאלי מבין הצמתים שגובהם $\displaystyle h$, הוא עץ שבו כל מסלול משורש לעלה הוא בגובה $\displaystyle h$, ולכל צומת (למעט העלים) יש שני ילדים.

בעץ כזה, ברמה הראשונה יש 1 צומת, ברמה הבאה 2 צמתים, וברמה ה$\displaystyle i$ יש $\displaystyle 2^{i-1}$ צמתים. נקבל שמספר הצמתים הוא $\displaystyle \sum _{i=1}^{h}2^{i-1}=2^{h}-1$. זה המספר המקסימאלי של הצמתים. לכן, עבור כל עץ שגובהו h ומספר צמתיו $\displaystyle n$, בהכרח מתקיים $\displaystyle n\leq 2^{h}-1\leq 2^{h}$. מלקיחת $\displaystyle \log$ משני האגפים נקבל $\displaystyle h=\Omega (\log(n))$.

הוכחה ב' (מבוססת על מגבלות דחיסה)

שקלו לדלג על נושא זה תוכל ללמוד את חומר הקורס גם בלי הוכחות מסוג זה.

נגדיר את אורך המסלול הארוך ביותר כ$\displaystyle h$

נניח ש$\displaystyle a_{1},\ldots a_{n}$ היא קבוצת שמות שידועה לשולח ולמקבל. השולח רוצה להודיע על שם אחד מתוך הקבוצה הידועה. לדוגמה, קבוצת השמות יכולה להיות רשימת המתמודדים על נשיאות ארה"ב, וכתב עיתון מעוניין לשלוח למערכת את שם הזוכה.

משפט: בכל שיטת קידוד, יש הודעה אחת לפחות שארכה $\displaystyle \Omega (\log(n))$.

(הטענה נובעת משיקולים קומבינטוריים דומים מאד לאלה של החסם התחתון על מיון מבוסס-השוואות שראינו.)

מצד שני, כל עץ חיפוש בינרי יכול לשמש לקידוד צומת. השולח מחפש את הצומת בעץ, מהצומת למטה (כפי שראינו בחיפוש בעץ בינרי). בכל צומת, אם הוא פונה שמאלה הוא מסמן 0, ואם פונה ימינה, הוא מסמן 1. השולח משדר את רצף הביטים למקבל. ברור שהמקבל יכול מתוך רצף הביטים (והעץ) למצא את הצומת המתאים.

נשים לב שמספר הביטים שנשלח הוא בדיוק מספר הקשתות מצומת השורש לצומת הנבחר. לכן, יש לפחות מסלול אחד שארכו $\displaystyle \Omega (\log(n))$.

זמני הריצה של צורות המעבר

שאלה

נתון עץ חיפוש בינרי בעל $\displaystyle n$ צמתים. אנא הוכח שכ"א מאלגוריתמי המעבר על כל צמתי העץ (לדוגמה Pre-Order) פועל בזמן $\displaystyle \Theta (n)$.

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

תשובה

מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/זמני הריצה של צורות המעבר/תשובה

תכונת מעבר In-order

שאלה

אנא הוכח שמעבר In-Order מדפיס את מפתחות העץ בסדר עולה.

תשובה

מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/תכונת מעבר In-order/תשובה

עץ דחוס

שאלה

הגדרה: נאמר שעץ הוא דחוס אם כל צומת בגובה $\displaystyle h$ הוא ראשו של תת-עץ בעל $\displaystyle \Theta (2^{h})$ איברים.

אנא הוכח שזמן חיפוש איבר בעץ דחוס הוא אופטימאלי (מבחינת סדר גדילה) במקרה הגרוע ביותר.

תשובה

זמן הריצה של Member

להלן פסוודו-קוד אפשרי לMember:

# Searches a tree (t) for a key (k).
# Returns whether the tree contains the key.
Find(t, k)
1	nd = t.root

ְ2	while nd != Nil
3		if k < nd.key
4			nd = nd.l-child
5		else if k > nd.key
6			nd = nd.r-child
7		else
8			return True
		
9	return False

אם מספר הצמתים בתת עץ בגובה $\displaystyle h$ הוא $\displaystyle \Theta (2^{h})$, אז קיים קבוע $\displaystyle c>0$, כך שמספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h}$. נשים לב שבכל איטרציה, אם הצומת לא נמצא (7-8), אז באיטרציה הבאה נמצאים בצומת שגובהו נמוך ב1(בגלל 3-4 או 5-6). לכן:

1. באיטרציה הראשונה, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h}$.
2. באיטרציה השניה, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h-1}={\frac {c}{2}}\cdot 2^{h}$.
3. באיטרציה השלישית, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h-2}={\frac {c}{4}}\cdot 2^{h}$.
4. ...

נקח $\displaystyle i=\left\lceil h+\log(c)\right\rceil$. אז $\displaystyle c\cdot 2^{h-i}=2^{h+\log(c)-\left\lceil h+\log(c)\right\rceil }\leq 1$, ולכן ב$\displaystyle \Theta (h)$ איטרציות נגיע לתת-עץ בגודל 1 (צומת יחיד).

בפרט, אם ניקח עץ בעל $\displaystyle n$ איברים, אז $\displaystyle n=\Theta (2^{h})$, ולכן $\displaystyle h=\Theta (\log(n))$.

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

אופטימאליות

כבר ראינו שMember צריך $\displaystyle O(\log(n))$ איטרציות בעץ דחוס, ולכן זהו חסם מלעיל על זמן ריצת חיפוש בעץ דחוס. מצד שני, בחסם תחתון על אורך המסלול הארוך ביותר ראינו בכל עץ חיפוש בינרי בעל $\displaystyle n$ איברים, יש מסלול אחד לפחות בעל $\displaystyle \Omega (\log(n))$ איברים, וזהו חסם תחתון כללי על חיפוש בעץ במקרה הגרוע. החסמים, לכן, מתלכדים כאן.

יחס צאצא-הורה

שאלה

נתון עץ חיפוש בינרי שבו יש צומת שהמפתח בו $\displaystyle x$ וכן צומת שהמפתח בו $\displaystyle y$. נניח $\displaystyle y<x$.

1. האם בהכרח הצומת של $\displaystyle y$ הוא צאצא של הצומת של $\displaystyle x$?
2. רוצים לפתח שיטה לקבוע חד-חד משמעית האם $\displaystyle y$ הוא צאצא של הצומת של $\displaystyle x$ בזמן $\displaystyle O(1)$. נניח בנוסף שממשק הצומת הורחב, וכולל גם את In-Order-Num(nd) המחזיר את סדרו של nd במעבר in-order,‏ Post-Order-Num(nd) המחזיר את סדרו של nd במעבר post-order, וDescendants(nd), המחזיר את מספר הצאצאים הכולל בתת העץ של nd (כולל nd עצמו; לדוגמה אם לnd אין ילדים, אז מספר הצאצאים הוא 1).
   1. אנא הראה שאף פונקציה בנפרד איננה מספיקה לקבוע חד-משמעית יחס זה.
   2. אנא מצא שילוב פונקציות שיספיק לקביעה חד משמעית.

תשובה

משפט כללי

כדי לפתור את התשובה, נוכיח ראשית את המשפט הפשוט הבא:

משפט: בעץ חיפוש בינרי בעל מפתחות שונים זה מזה, נניח שצומת $\displaystyle a$ מחזיק מפתח כלשהו. אז: הצאצאים השמאליים של $\displaystyle a$ מכילים כולם מפתחות קטנים ל$\displaystyle a$. יש עוד צמתים עם מפתחות קטנים מ$\displaystyle a$ מעבר לכך אם ורק אם $\displaystyle a$ הוא צאצא ימני (לאו דווקא ישיר) של צומת כלשהו.

להלן דוגמה למה שהמשפט אומר.

דוגמה: בתרשים הבא, $\displaystyle a$ אינו צאצא ימני של אף צומת. צמתי המפתחות הקטנים ממנו (הצבועים באפור), כולם בתת העץ הימני שלו. מיקום צמתים בעלי מפתחות קטנים מצומת נתון - לא צאצא ימני. לעומת זאת, בתרשים הבא, $\displaystyle a$ הוא צאצא ימני (לא ישיר) של $\displaystyle b$. צמתי המפתחות הקטנים ממנו (הצבועים באפור), בתת העץ הימני שלו וגם בתת העץ השמאלי של $\displaystyle b$. מיקום צמתים בעלי מפתחות קטנים מצומת נתון - צאצא ימני.

עכשיו תורכם: השתמש בתכונת הBST כדי להוכיח את המשפט.

הקשר ללא מידע נוסף

מהמשפט הכללי ברור שאי אפשר לקבוע האם הצומת של $\displaystyle y$ הוא צאצא של הצומת של $\displaystyle x$. ייתכן שהצומת של $\displaystyle y$ הוא צאצא שמאלי של הצומת של $\displaystyle x$, אך אם הצומת של $\displaystyle x$ הוא צאצא ימני של צומת כלשהו, ייתכן שהצומת של $\displaystyle y$ הוא צאצא שמאלי של אותו הצומת.

הקשר עם מידע נוסף

ראשית, ברור שכל אחד בנפרד מסדרו של צומת במעבר in-order,‏ post-order,‏ או מספר צאצאיו, אינו מספיק כדי לקבוע יחס צאצא-אב.

נתבונן שוב במקרה בו צומת $\displaystyle a$ הוא צאצא ימני של צומת $\displaystyle b$.

מיקום צמתים בעלי מפתחות קטנים מצומת נתון - צאצא ימני.

1. אם $\displaystyle y<x$, אז $\displaystyle y$ יודפס לפני $\displaystyle x$ במעבר in-order בכל מקרה. אבל אם $\displaystyle x=a$, אז $\displaystyle y$ יכול להיות צאצא שמאלי של $\displaystyle x$, או צאצא שמאלי של הורה של $\displaystyle x$ (לדוגמה $\displaystyle b$).
2. באופן דומה, אם $\displaystyle y<x$, אז $\displaystyle y$ יודפס לפני $\displaystyle x$ במעבר post-order בכל מקרה. אבל שוב, אם $\displaystyle x=a$, אז $\displaystyle y$ יכול להיות צאצא שמאלי של $\displaystyle x$, או צאצא שמאלי של הורה של $\displaystyle x$ (לדוגמה $\displaystyle b$).
3. כפי שהתרשים מראה, אם $\displaystyle x<y$, אין בהכרח שום קשר בין מספר האיברים בתת-העץ של $\displaystyle x$ לבין זה של $\displaystyle y$.

לעומת זאת, השילוב של סדר post-order וdescendants מספיק.

משפט: נגדיר: $\displaystyle p_{l}$ הוא מספר הpost-order של ילדו השמאלי של $\displaystyle x$. $\displaystyle d_{l}$ הוא מספר הdescendants של ילדו השמאלי של $\displaystyle x$. אז כל צומת בתת העץ השמאלי הוא בעל מספר post-order ב$\displaystyle \left\{p_{l}-d_{l}+1,\ldots ,p_{l}\right\}$.

הוכחה: מספרי הpost-order של ילדו השמאלי של $\displaystyle x$ הם $\displaystyle d_{l}$ מספרים עוקבים, שהאחרון שבהם הוא $\displaystyle p_{l}$.

מהמשפט האחרון ברור כיצד יש למצוא האם צומת כלשהו nd-y הוא צאצא של צומת כלשהו nd-x, בהנחה שתוכן הראשון הוא $\displaystyle y$, תוכן השני הוא $\displaystyle x$, ו$\displaystyle y<x$:

1. אם לnd-x אין ילד שמאלי - התשובה שלילית.
2. אחרת:
   1. קובעים כ$\displaystyle p_{l}$ את Postorder-Num(nd.l-child).
   2. קובעים כ$\displaystyle d_{l}$ את Descendants(nd.l-child).
   3. בודקים האם {Postorder-Num(nd-y) גדול או שווה ל$\displaystyle p_{l}-d_{l}+1$.

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

מציאת איברי קצה בעץ דחוס

שאלה

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

נניח שמספר המפתחות בקבוצה הוא $\displaystyle n$. אנא שנה את מבנה עץ החיפוש הבינרי, ובפרט את פעולת Member, כך שMember(t, x) יעבוד בזמן $\displaystyle \log(k)$ אם $\displaystyle x$ אכן איבר בקבוצה, והוא האיבר ה$\displaystyle k$ הקטן ביותר.

שים לב שתשובתך אמורה להיות נכונה לכל $\displaystyle k=1,\ldots ,n$.

תשובה

מיקום הצומת הk-קטן ביותר

משפט: הצומת ה$\displaystyle h$ בגובה במסלול השמאלי ביותר בעץ, הוא ראשו של תת-עץ המכיל את $\displaystyle \Theta (2^{h})$ האיברים הקטנים ביותר בעץ.

תת עץ של הצומת בגובה h במסלול השמאלי.

הוכחה: היות שהעץ הוא דחוס, אז צומת בגובה $\displaystyle h$ (בפרט אחד במסלול השמאלי ביותר בעץ), מכיל $\displaystyle \Theta (2^{h})$ איברים.

כעת נוכיח שהאיברים בתת-עץ הם האיברים הקטנים ביותר בעץ.

אם הצומת הוא ראש העץ, אז ברור שאין איברים גדולים מהם (כי אין איברים אחרים מהם).

אם הצומת אינו ראש העץ, אז יש לו אב, $\displaystyle a$.

מיקום צמתים בעלי מפתחות קטנים מצומת נתון - לא צאצא ימני.

נשים לב ש$\displaystyle a$ אינו צאצא ימני של אף צומת (מדוע?), ולכן כל האיברים הקטנים ממנו נמצאים בתת עץ השמאלי שלו.

מהמשפט הקודם נובע שהאיבר ה$\displaystyle k$ הקטן ביותר נמצא בתת עץ שראשו הוא צומת בגובה $\displaystyle \Theta (\log(k))$ במסלול השמאלי ביותר.

שינויים בעץ

נוסיף לעץ עוד (מצביע ל)צומת הקטן ביותר, min:

Binary-Search-Tree
	# The root (shoresh).
1	root	
	# Number of nodes.
2	size
	# The smallest node.
3	min

נדאג לעדכן איבר זה בפעולות Insert וDelete (הדבר אינו מסובך במיוחד, ולא נציג את הפסוודו-קוד כאן).

שינויים בMember

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

Member(t, x)
	# Loop upward starting from the leftmost node.

1	nd = t.min

2	while nd.parent != Nil and nd.parent.key < x
3		nd = nd.parent

	# Now loop down again.

4	while nd != Nil
5		if k < nd.key
6			nd = nd.l-child
7		else if k > nd.key
8			nd = nd.r-child
9		else
10			return True

11	return False

עץ Foo-Bar

שאלה

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ Foo-Bar מוגדר כך:

1. כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
   1. צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
   2. צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
2. העץ מקיים את את תכונת הFoo-Bar - לכל צומת x:
   1. כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
   2. כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
3. כל המסלולים משורש העץ לעלה ריק (Nil) בעל אותו אורך בדיוק.

דוגמה: צומת Bar צומת Bar.

דוגמה: צומת Foo צומת Foo.

דוגמה: עץ Foo-Bar להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2. עץ Foo-Bar.

אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו $\displaystyle n$ מפתחות וגבהו הוא $\displaystyle h$, אז $\displaystyle h=O(\log(n))$.

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

תשובה

הפתרון דומה מאד להוכחת הטענה שעצים אדומים-שחורים הם לוגריתמיים. נניח שגובה העץ הוא $\displaystyle h$. מה מספר המפתחות הקטן ביותר היכול להיות בעץ? קל לראות שזה המספר המתקבל כאשר כל אחד מהצמתים הוא מסוג Bar. במצב זה, היות שעל פי הנתונים כל המסלולים משורש לעלה הם בעלי אותו אורך, נקבל שמספר המפתחות הוא לכל הפחות $\displaystyle \sum _{i=1}^{h}\left[2^{i-1}\right]=2^{h}-1$. הפתרון, לכן, מתקבל על ידי פתירת אי-השוויון $\displaystyle n\geq 2^{h}-1$:

$\displaystyle n\geq 2^{h}-1\Rightarrow$
$\displaystyle n\geq 2^{h}/2\Rightarrow$
$\displaystyle \log(n)\geq h-1\Rightarrow$
$\displaystyle h=O\left(\log(n)\right)$

זמן הריצה של הפונקציות למעבר על כל הצמתים

שאלה

אנא הוכח שכל אחת מהפעולות למעבר על כל איברי העץ שראינו Post-Order In-Order, וIn-Order), פועלת בזמן לינארי במספר האיברים בעץ.

תשובה

עלינו להראות שיש שני קבועים, $\displaystyle c_{0}$ ו$\displaystyle c_{1}$ המקיימים $\displaystyle c_{1}\cdot n\leq T(n)\leq c_{0}\cdot n$ עבור ערכי $\displaystyle n$ גדולים מספיק.

הטענה שקיים $\displaystyle c_{1}$ $\displaystyle T(n)\geq c_{1}\cdot n$ (כלומר $\displaystyle T(n)=\Omega (n)$) ברורה, מפני שאנו יודעים שהפונקציה עוברת על כל אחד מהצמתים, ויש $\displaystyle n$ צמתים עפ"י ההגדרה. נוכיח לכן רק את הטענה לגבי קיומו של $\displaystyle c_{0}$.

הוכחה: (בסיס האינדוקציה) נבחר את בסיס האינדוקציה כ$\displaystyle n=1$.

ונסמן ב$\displaystyle k$ את זמן הריצה של הפונקציה על קלט בגודל 1. מכאן נקבל את האילוץ על $\displaystyle c_{0}$: $\displaystyle k\leq c_{0}\cdot 1=c_{0}$. בוודאי שקיים $\displaystyle c_{0}$ המקיים אילוץ זה.

(מעבר האינדוקציה) נניח שהטענה מתקיימת לכל $\displaystyle n'<n$.

נזכר שראינו כבר את נוסחת הנסיגה המתאימה לבעיה $\displaystyle T(n)=T(n')+O(1)+T(n-n'-1)$ (קל לראות זאת גם מהתרשים הבא).

מעבר האינדוקציה.

הנוסחה אומרת שקיים $\displaystyle k'$ כך שמתקיים $\displaystyle T(n)\leq T(n')+k'+T(n-n'-1)$.

נשתמש בנוסחת הנסיגה ובהנחת האינדוקציה, ונקבל

$\displaystyle T(n)\leq T(n')+k'+T(n-n'-1)\leq$
$\displaystyle c_{0}\cdot n'+k'+c_{0}(n-n'-1)=$
$\displaystyle c_{0}\cdot n+(k'-c_{0})$

אם נבחר $\displaystyle k'\leq c_{0}$ אז $\displaystyle (k'-c_{0})$ שלילי, ולכן בהכרח $\displaystyle T(n)\leq c_{0}\cdot n$.

נשים לב שבסיס האינדוקציה הגביל אותנו לבחור $\displaystyle k\leq c_{0}$, ומעבר האינדוקציה הגביל אותנו לבחור $\displaystyle k'\leq c_{0}$.

מכאן יוצא שאכן יש $\displaystyle c_{0}$ המתאים לבעיה (למעשה יש אינסוף כאלה) - עלינו פשוט לבחור $\displaystyle c_{0}$ המקיים

$\displaystyle c_{0}\geq \max \left\{k,k'\right\}$.

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

שאלה

בשאלה זו עליך להוכיח חסם תחתון על $\displaystyle T(n)$, מספר עצי החיפוש הבינריים השונים בעלי $\displaystyle n$ מפתחות שונים זה מזה.

דוגמה: נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2$. יש 2 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1 ו2. נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2,3$. יש 5 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.

מהדוגמה נוכל להסיק כי

$\displaystyle T(0)=T(1)=1$, $\displaystyle T(2)=2$, $\displaystyle T(3)=5$.

אנא הוכח את המשפט הבא.

משפט: אם $\displaystyle n>1$, אז $\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]$.

תשובה

הוכחה: ֲנבחר איבר כלשהו כשורש העץ, ונגדיר כ$\displaystyle i$ את גודל תת-העץ השמאלי (כלומר, האיבר שבחרנו הוא מספר $\displaystyle i+1$ בגדלו בקבוצה). לפי ההגדרה, יש $\displaystyle T(i)$ אפשרויות שונות לתת-העץ השמאלי. עבור כל אחת מאפשרויות אלה, יש $\displaystyle T(n-i-1)$ אפשרויות לסדר את תת-העץ הימני (המכיל $\displaystyle n-i-1$ איברים). כלומר, כאשר יש $\displaystyle i$ איברים בתת-העץ השמאלי, יש $\displaystyle T(i)\cdot T(n-i-1)$ עצים שונים.

נותר רק לחבר את כל האפשרויות עבור כל ערכי $\displaystyle i$ השונים, ו$\displaystyle i$ יכול לקבל את הערכים $\displaystyle 0,1,\ldots ,n-1$.

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

שאלה

בשאלה זו עליך להוכיח חסם תחתון על $\displaystyle T(n)$, מספר עצי החיפוש הבינריים השונים בעלי $\displaystyle n$ מפתחות שונים זה מזה.

דוגמה: נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2$. יש 2 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1 ו2. נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2,3$. יש 5 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.

מהדוגמה נוכל להסיק כי

$\displaystyle T(0)=T(1)=1$, $\displaystyle T(2)=2$, $\displaystyle T(3)=5$.

אנא הוכח ש$\displaystyle T(n)=\Omega (2^{n})$, כלומר שמספר עצי החיפוש הבינריים גדל בצורה אקספוננציאלית.

תשובה

כבר ראינו את נוסחת הנסיגה $\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]$. נשתמש בזאת כדי להוכיח את הטענה בשאלה באינדוקציה. נראה שקיים $\displaystyle c>0$ כך שתמיד $\displaystyle T(n)\geq c\cdot 2^{n}$.

הוכחה: (מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונראה שהיא נכונה גם ל$\displaystyle n$.

$\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]\geq$
$\displaystyle \sum _{i=0}^{n-1}[c\cdot 2^{i}\cdot c\cdot 2^{n-i-1}]=$
$\displaystyle {\frac {c^{2}}{2}}\sum _{i=0}^{n-1}[2^{n}]=$
$\displaystyle {\frac {n\cdot c}{2}}c\cdot 2^{n}$

נפתור $\displaystyle {\frac {n\cdot c}{2}}\geq 1$, ונקבל $\displaystyle c\geq {\frac {2}{n}}$. עבור $\displaystyle n\geq 5$, נקבל שמספיק שיתקיים $\displaystyle c\geq {\frac {2}{5}}$.

מבדיקת מספר העצים השונים, עולה שקיים $\displaystyle c$ מתאים גם לבסיס האינדוקציה (המקרים $\displaystyle n\leq 4$).

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

שאלה

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

א'

להלן הוכחה שגויה לכך שכל אחת מהפעולות למעבר על כל איברי העץ שראינו Post-Order In-Order, וIn-Order), פועלת בזמן ריבועי במספר האיברים בעץ.

הוכחה: ההוכחה באינדוקציה על מספר הצמתים, $\displaystyle n$.

(בסיס האינדוקציה) עבור $\displaystyle n=1$, $\displaystyle T(1)=O(1)=O(1^{2})$.

(מעבר האינדוקציה) כבר ראינו שזמן הריצה נתון ע"י נוסחת הנסיגה $\displaystyle T(n)=T(i)+T(n-i)+O(i)$. נשמתש בהנחת האינדוקציה, ונקבל

T(n) = \Theta(i^2) + \Theta((n - i)^2)

ב'

מה בעייתי בהוכחה הבאה לכך שזמן הריצה הוא לינארי?

תשובה

מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/זמן הריצה של הפונקציות למעבר על כל הצמתים - הוכח שגויה/תשובה