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

שימו לב: *נא להגיש רק את שאלות 1-5. שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

1

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

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

2

א'

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

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

ב'

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

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

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

3

נתון עץ חיפוש בינרי שבו יש צומת שהמפתח בו $\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. אנא מצא שילוב פונקציות שיספיק לקביעה חד משמעית.

4

נתונה סידרה $\displaystyle X=[x_{1},...,x_{n}]$ של מספרים גדולים או שווים ל1. תת-סידרה $\displaystyle X'$ של X נקראת חברותית אם היא מכילה לפחות שני איברים עוקבים של X, ובדלנית אם היא איננה חברותית.

דוגמה: נניח ש$\displaystyle X=[1,5,2,7]$. אז: $\displaystyle X'=[1,5]$ היא תת-סידרה חברותית. $\displaystyle X'=[1,7]$ היא תת-סידרה בדלנית. $\displaystyle X'=[1,5,7]$ היא תת-סידרה חברותית. $\displaystyle X'=[1]$ היא תת-סידרה בדלנית. $\displaystyle X'=[]$ היא תת-סידרה בדלנית.

אנא כתוב אלגוריתם אשר מקבל סידרה $\displaystyle X$ ומדפיס תת-סידרה בדלנית שמכפלת איבריה גדולה ככל האפשר. (הנח שמכפלת איברי תת-סידרה ריקה היא 1.) קבע את Length(X) כ$\displaystyle n$, ונתח את סיבוכיות האלגוריתם במונחי $\displaystyle n$.

דוגמה: נניח שהאלגוריתם מקבל כקלט את $\displaystyle X=[1,5,2,7]$. במקרה זה, עליו להדפיס $\displaystyle [5,7]$: זו תת-סידרה בדלנית של $\displaystyle X$,‏ $\displaystyle 5\cdot 7=35$,‏ ואין תת-סידרה בדלנית אחרת שמכפלת איבריה גדולה מ35.

5

רשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. $\displaystyle m_{1},m_{2},\ldots m_{n}$ מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:

1. מסקר שוק, הרשת מעריכה שבבית מספר $\displaystyle m_{i}$ רווחיה הצפויים יהיו $\displaystyle p_{i}$ ‏($\displaystyle p_{i}$ הוא מספר חיובי כלשהו).
2. הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ$\displaystyle k$‏ ($\displaystyle k$ הוא מספר שלם חיובי כלשהו).

דוגמה: אם $\displaystyle k=20$ והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן $\displaystyle 143-135<20$.

אנא כתוב אלגוריתם יעיל המקבל את המערך M (המכיל את מספרי הבתים), את המערך P (המכיל את הרווחים הצפויים), ואת המספר k (המציין את מגבלת המרחק), ומדפיס את מספרי הבתים שהקמת הסניפים בהם צפוייה למקסם את הרווחיות. אנא הוכח נכונות ונתח סיבוכיות.

6

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ 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))$.

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