מבני נתונים
דומיין זה בודק בחירה ושימוש במבני נתונים: מערך, רשימה מקושרת, מחסנית, תור, עץ חיפוש בינארי, ערימה וטבלת גיבוב. השאלות כוללות מעבר ידני, פעולות הכנסה והוצאה, וניתוח סיבוכיות בכל מבנה.
כללים והשוואות
- מערך: גישה ישירה O(1), הכנסה באמצע O(n) בגלל הזזה.
- רשימה מקושרת: הכנסה בראש O(1), חיפוש O(n), אין גישה ישירה לפי אינדקס.
- מחסנית LIFO: push, pop, peek; שימושית לסוגריים מאוזנים ולקריאות רקורסיביות.
- תור FIFO: enqueue, dequeue; שימושי ל-BFS ולתור משימות.
- BST: בכל צומת, כל איבר בתת-עץ שמאלי קטן ממנו וכל איבר בימני גדול ממנו; חיפוש O(h), כאשר h הוא גובה העץ.
- ערימה: מינימום או מקסימום בשורש, הכנסה והוצאה O(log n).
- טבלת גיבוב: חיפוש ממוצע O(1), אך התנגשויות יכולות להוביל ל-O(n).
דוגמה מעובדת
הכנסה ל-BST בסדר 50, 30, 70, 20, 40: 50 שורש; 30 קטן ולכן שמאלה; 70 גדול ולכן ימינה; 20 קטן מ-50 ומ-30 ולכן שמאלה ל-30; 40 קטן מ-50, גדול מ-30 ולכן ימינה ל-30. חיפוש 40 יעבור 50→30→40, שלוש השוואות. אם העץ היה לא מאוזן, אותו חיפוש היה עלול להיות O(n).
מלכודות
- איבוד ראש הרשימה בעת מחיקה או הוספה.
- הנחה ש-BST הוא תמיד O(log n) גם כשהוא מנוון לרשימה.
- בלבול בין סדר LIFO ל-FIFO.
- שימוש במערך במקום בתור כאשר נדרש סדר הגעה.
- התעלמות מהתנגשויות בטבלת גיבוב.