שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2018 - עץ חיפוש בינארי

ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף. א) לכל $n$ קיים עץ חיפוש בינארי של $n$ איברים שגובהו $\theta(\sqrt{n})$ ב) ברשימה מקושרת באורך $n$ כדאי לשמור גם מצביע לאיבר האמצעי, כי בהשקעה של $O(1)$ שטח, קיבלנו אפשרות לבצע חיפוש בינארי. ג) באלגוריתם של Boyer & Moore בהגדרה של $\Delta_2$, נחפש לכל סיפא מופע מוקדם יותר, אך נדרוש שהאות הקודמת לסיפא תהיה שונה. אם נוריד דרישה זאת, האלגוריתם יכול לשגות. ד) בטבלת Hash בגודל 2500 הוכנסו 1000 איברים ע"י שימוש ב־Hashing Uniform. הזמן הממוצע לחיפוש מוצלח, כאשר לכל איבר שהוכנס הסתברות שווה להופיע בחיפוש, הוא $\frac{5}{2} \ln \frac{5}{3}$. ה) נתון B-tree מדרגה $m$ שמכיל $k$ איברים. אם נכניס איבר נוסף לעץ ובשלב הבא נבטל אותו, העץ שמתקבל אחרי ביצוע שתי הפעולות יהיה תמיד זהה לעץ ממנו יצאנו. ו) החסם התחתון למיזוג 2 סדרות ממוינות, אחת באורך $n$ ואחת באורך 3 הוא $n-2$. ז) לכל $n \in \mathbb{N}$ קיים עץ AVL המכיל $n$ קודקודים שסריקת ה־post-order שלו היא סדרה ממוינת. ח) בכל רשימה מקושרת, קיים איבר אליו ניתן לגשת ב־$O(1)$ זמן. ט) לכל $n \in \mathbb{N}$ קיים עץ בינארי המכיל בדיוק $n$ עלים ו־$2n$ קודקודים פנימיים. י) זמן חיפוש איבר ברשימת דילוגים (skip-list) הוא $O(n)$ במקרה הגרוע.

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

פתרון: א) **נכון**. ניתן לבנות עץ כזה. למשל, ניקח שרשרת (עץ מנוון) באורך $\lceil \sqrt{n} \rceil$. לכל אחד מקודקודי השרשרת (פרט אולי לאחרון) נחבר תת-עץ חיפוש בינארי מאוזן לחלוטין בגודל $\approx \sqrt{n}$. הגובה הכולל יהיה סכום גובה השרשרת וגובה העץ הקטן, כלומר $\theta(\sqrt{n} + \log(\sqrt{n})) = \theta(\sqrt{n})$. ב) **לא נכון**. מצביע לאיבר האמצעי אכן תופס מקום של $O(1)$. עם זאת, כדי לבצע **חיפוש בינארי**, לאחר הגישה הראשונה לאמצע, יש צורך לגשת לאמצע של החצי הראשון או השני של הרשימה. ברשימה מקושרת, פעולה זו דורשת מעבר סדרתי על $\approx n/4$ איברים, ולכן זמן הגישה אינו $O(1)$. לכן, חיפוש בינארי יעיל אינו אפשרי. ג) **נכון**. כלל הסיומת הטובה (good-suffix rule) באלגוריתם **Boyer-Moore** מחפש הופעה קודמת של הסיומת שתאמה. הדרישה שהתו הקודם להופעה זו יהיה שונה מהתו שגרם לאי-התאמה היא קריטית. אם נשמיט דרישה זו, במקרים מסוימים (למשל, דפוס `baba` בטקסט `...ababa...`), האלגוריתם עלול לבצע הזזה שתוביל לאותה אי-התאמה בדיוק, וכך להיכנס ללולאה אינסופית. ד) **נכון**. השאלה מתארת **גיבוב אחיד (uniform hashing)**, והנוסחה הנתונה, $\frac{1}{\alpha} \ln \frac{1}{1-\alpha}$, היא זמן החיפוש המוצלח הממוצע בשיטת **כתובות פתוחות (open addressing)** תחת ההנחה של מישוש אחיד (uniform probing). מקדם המילוי (load factor) הוא $\alpha = \frac{n}{m} = \frac{1000}{2500} = \frac{2}{5}$. הצבה בנוסחה נותנת: $\frac{1}{2/5} \ln \frac{1}{1-2/5} = \frac{5}{2} \ln \frac{1}{3/5} = \frac{5}{2} \ln \frac{5}{3}$. ה) **לא נכון**. פעולות ההכנסה והמחיקה ב-**B-tree** אינן בהכרח הופכיות זו לזו. למשל, הכנסת איבר יכולה לגרום לפיצול צומת. מחיקת אותו איבר לאחר מכן יכולה לגרום לצומת להיות בתת-תכולה, מה שיוביל לפעולת איזון. פעולת האיזון עשויה להיות מיזוג עם צומת שכן (שמחזיר למצב המקורי), אך גם עלולה להיות "השאלה" (rotation) מאיבר שכן, אם לשכן יש מספיק מפתחות. בחירה ברוטציה, כאשר היא אפשרית, יכולה להוביל למבנה עץ שונה מהמבנה המקורי. ו) **לא נכון**. החסם התחתון למיזוג שתי סדרות ממוינות בגודל $n$ ו-$k$ (כאשר $n \ge k$) הוא $k-1$. במקרה זה, $n$ ו-3, ולכן החסם הוא $3-1=2$. לחלופין, ניתן לראות כי במקרה הגרוע ביותר נצטרך לבצע $n+3-1=n+2$ השוואות. ז) **נכון**. עץ **AVL** שכל צומת פנימי בו מכיל רק ילד שמאלי הוא למעשה רשימה מקושרת "שמאלית". עץ כזה הוא עץ AVL חוקי (גובה כל תת-עץ ימני הוא -1, וגובה תת-עץ שמאלי יורד ב-1 בכל רמה, כך שהפרש הגבהים תמיד 1). סריקת **post-order** בעץ כזה תבקר תחילה בכל תת-העץ השמאלי (עד לעלה), תדפיס את ערך הצומת, ואז תעלה למעלה. תהליך זה יוביל להדפסת האיברים מהקטן לגדול, כלומר סדרה ממוינת. ח) **נכון**. בכל רשימה מקושרת (לא ריקה), ניתן לגשת לאיבר הראשון (ה-**head**) בזמן של $O(1)$, מכיוון שתמיד נשמר מצביע אליו. ט) **לא נכון**. בעץ בינארי (לא ריק), מספר העלים $L$ ומספר הקודקודים הפנימיים בעלי שני בנים $N_2$ קשורים על ידי הנוסחה $L = N_2 + 1$. מספר הקודקודים הפנימיים הכולל $N_{internal}$ הוא $N_1 + N_2$ (בעלי בן אחד ובעלי שני בנים). אם $n$ הוא מספר העלים, אז $n=N_2+1$. אם מספר הקודקודים הפנימיים הוא $2n$, אז $N_1+N_2=2n$. מהצבת $N_2=n-1$ נקבל $N_1 + (n-1) = 2n$, כלומר $N_1 = n+1$. זה אפשרי. אבל השאלה היא "בכל עץ בינארי". בעץ בינארי *מלא* (full binary tree), כל קודקוד פנימי הוא בעל שני בנים ($N_1=0$), ולכן מספר הקודקודים הפנימיים הוא $N_2=n-1$, לא $2n$. לכן הטענה לא נכונה באופן כללי. אם הכוונה לעץ בינארי כלשהו, אז הטענה נכונה, אך לרוב בהקשר זה הכוונה לעצים מלאים או שלמים. בהינתן הניסוח, התשובה המדויקת היא שהקשר אינו מתקיים לכל עץ. י) **נכון**. **רשימת דילוגים (skip-list)** מספקת ביצועים ממוצעים של $O(\log n)$ לפעולות חיפוש, הכנסה ומחיקה. עם זאת, במקרה הגרוע ביותר (worst-case), המבנה ההסתברותי של הרשימה עלול להתנוון למצב בו כל האיברים נמצאים רק ברמה התחתונה, ללא "קיצורי דרך" ברמות הגבוהות. במצב זה, הרשימה מתנהגת כרשימה מקושרת רגילה, וחיפוש ידרוש מעבר סדרתי על כל $n$ האיברים, כלומר זמן של $O(n)$.