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

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

רמז: חשבו על שילוב של שני מבני נתונים: אחד שמספק סיבוכיות ממוצעת של $O(1)$ ואחר שמבטיח סיבוכיות של $O(\log n)$ במקרה הגרוע לפעולות הנדרשות.

פתרון: נשתמש ב**טבלת גיבוב (Hash Table)** בגודל $m=O(n)$, כאשר כל תא בטבלה (bucket) אינו רשימה מקושרת, אלא **עץ חיפוש בינארי מאוזן** (למשל, עץ AVL או עץ אדום-שחור). **ניתוח המבנה המוצע:** 1. **סיבוכיות מקום:** טבלת הגיבוב עצמה דורשת שטח של $O(m) = O(n)$. בנוסף, כל אחד מ-$n$ האיברים מאוחסן בדיוק באחד מהעצים המאוזנים. כל צומת בעץ דורש שטח של $O(1)$, ולכן כלל העצים יחד דורשים שטח של $O(n)$. סך כל המקום הנדרש הוא $O(n) + O(n) = O(n)$, כנדרש. 2. **סיבוכיות זמן (חיפוש, הוספה, מחיקה):** פעולה כלשהי (חיפוש, הוספה או מחיקה) עבור איבר $x$ מתבצעת בשני שלבים: א. חישוב ערך הגיבוב $h(x)$ כדי למצוא את התא המתאים בטבלה. שלב זה לוקח $O(1)$. ב. ביצוע הפעולה הנדרשת על העץ המאוזן שנמצא בתא $h(x)$. * **במקרה הממוצע:** בהנחה של פונקציית גיבוב טובה (למשל, גיבוב אחיד פשוט), אנו מצפים שהאיברים יתפזרו באופן אחיד בין התאים בטבלה. אם יש $n$ איברים ו-$m=O(n)$ תאים, גודלו המצופה של כל עץ מאוזן הוא $E[size] = n/m = O(1)$. פעולה על עץ מאוזן בגודל קבוע $k=O(1)$ לוקחת זמן של $O(\log k) = O(\log 1) = O(1)$. לכן, סיבוכיות הזמן הממוצעת הכוללת היא $O(1) + O(1) = O(1)$. * **במקרה הגרוע:** המקרה הגרוע ביותר מתרחש כאשר כל $n$ האיברים מתנגשים וממופים לאותו תא בטבלת הגיבוב. במצב זה, העץ המאוזן באותו תא יכיל את כל $n$ האיברים. מכיוון שהעץ מאוזן, פעולות חיפוש, הוספה ומחיקה עליו לוקחות זמן של $O(\log n)$. לכן, סיבוכיות הזמן הכוללת במקרה הגרוע היא $O(1) + O(\log n) = O(\log n)$. לסיכום, מבנה הנתונים המוצע עומד בכל הדרישות של השאלה. $\blacksquare$