מבני נתונים

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

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

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

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

מחסנית (Stack) מגבילה את הגישה לקצה אחד בלבד לפי עקרון LIFO — הנכנס אחרון יוצא ראשון. שלוש הפעולות שלה, דחיפה, שליפה והצצה, כולן O(1). המחסנית היא מבנה הנתונים שמאחורי מחסנית הקריאות של כל תוכנית רקורסיבית, מנגנוני ביטול פעולה, ובדיקת איזון סוגריים.

תור (Queue) מגביל את הגישה לשני קצוות לפי עקרון FIFO — הנכנס ראשון יוצא ראשון. הוא הבסיס לכל מערכת שמעבדת בקשות לפי סדר הגעה, לתזמון משימות במערכת הפעלה, ולאלגוריתם חיפוש לרוחב. מימוש נאיבי מעל מערך גורם להוצאה בעלות O(n), ולכן משתמשים בתור מעגלי או ברשימה מקושרת דו-כיוונית כדי לשמור על O(1) בשני הקצוות.

רשימה מקושרת מוותרת על הרציפות בזיכרון: כל צומת מחזיק ערך ומצביע לצומת הבא. התוצאה היא הכנסה ומחיקה ב-O(1) כשכבר מחזיקים מצביע למקום הנכון, אך גישה לפי אינדקס הופכת ל-O(n) ולוקליות הזיכרון נפגעת.

עץ חיפוש בינארי שומר על תכונה אחת בכל צומת: כל הערכים בתת-העץ השמאלי קטנים ממנו וכל הערכים בתת-העץ הימני גדולים ממנו. התכונה הזו מאפשרת לחפש ערך על ידי ירידה בענף אחד בלבד, ולפסול חצי מהאפשרויות בכל צעד — O(log n) בעץ מאוזן. יתרון נוסף הוא שמעבר In-Order מחזיר את כל הערכים ממוינים ב-O(n).

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

טבלת גיבוב נוקטת גישה שונה לגמרי: פונקציית גיבוב ממפה כל מפתח למיקום במערך, כך שהגישה אינה דורשת חיפוש כלל אלא חישוב — O(1) בממוצע. המחיר הוא התנגשויות, כששני מפתחות ממופים לאותו מיקום, ואותן פותרים בשרשור (רשימה בכל תא) או בכתובת פתוחה (חיפוש התא הפנוי הבא).

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