מבנה נתונים

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

יש להבחין בין מבנה נתונים לבין מבנה נתונים מופשט (ADT - abstract data type). מבנה נתונים מופשט מגדיר ממשק והוא חסר מימוש, ויכולים להיות מבני נתונים אחדים שמממשים את הממשק שהוא מציע. לדוגמה, מחסנית היא מבנה נתונים מופשט, שמערך ורשימה מקושרת הם מימושים אפשריים שונים שלו.

העיסוק במבני נתונים הוא חלק מהתפתחותם של מדעי המחשב בחצי השני של המאה העשרים.

מבני נתונים נפוצים

• מערך - מבנה שמורכב מאוסף של תאים שסדרם בדרך כלל בעל חשיבות. ניתן לגשת לכל תא בעזרת מיקומו הסידורי. מערכים יכולים להיות בעלי גודל קבוע או בעלי גודל משתנה.
• רשומה - מבנה שמורכב מאוסף קבוע של תאים בסדר מסוים הנקראים לעיתים שדות או איברים, המכילים מידע. לתאים אלה בדרך כלל פונים לפי שמות ברורים הניתנים להם.
• רשימה (List) - מבנה נתונים מופשט המגדיר אוסף סדרתי של איברים.
  • רשימה מקושרת (Linked List) - רשימה שבה כל איבר מצביע על האיבר הבא אחריו.
• קבוצה - מבנה נתונים מופשט שכל ערך מופיע בו לכל היותר פעם אחת, ואין חשיבות לסדר בין הערכים. מימוש של קבוצה הוא למעשה ייצוג ממוחשב של קבוצה מתמטית סופית.
• מילון (Dictionary, Map) - מבנה נתונים מופשט המאפשר מיפוי בין מפתחות לערכים. נקרא גם "מערך אסוציאטיבי".
  • טבלת גיבוב (Hash Table) - מימוש של מילון המשתמש בפונקציית גיבוב על-מנת להקטין את תחום המפתחות ולשמרם במערך לצורך שליפה מהירה.
• מחסנית (Stack): מבנה נתונים מופשט שמזכיר מחסנית של רובה: האיבר שנכנס ראשון למחסנית יוצא ממנה אחרון (נכנס אחרון יוצא ראשון - LIFO).
• תור (Queue) - מבנה נתונים מופשט שמזכיר תור של בני אדם: האיבר שנכנס ראשון לתור יוצא ממנו ראשון (נכנס ראשון יוצא ראשון - FIFO).
• דו-תור (Deque) - משלב את התכונות של תור ושל מחסנית.
• גרף (Graph)
• עץ סיפות (Suffix Tree) - עץ המחזיק סיומות של מחרוזות ומאפשר ביצוע פעולות כגון מציאת תתי-מחרוזות בצורה יעילה.
• עץ חיפוש (Tree) - עץ מכוון וממוין.
  • עץ מאוזן - עץ חיפוש בינארי השומר על גובה מינימלי תחת פעולות הכנסה והוצאה של צמתים, בין העצים המאוזנים ניתן למנות את
    • עץ AVL - עץ חיפוש בינארי שמתקן את עצמו תוך כדי בנייה באמצעות "גלגולים" כך שגובהו יישאר נמוך יחסית למספר האיברים בו.
    • עץ אדום שחור - עץ חיפוש בינארי הבנוי לפי הגבלות מצמצמות גובה הבנויות סביב חלוקה של צמתיו לשתי קבוצות.
  • עץ B+ - עץ חיפוש שבו לכל צומת מספר גדול של בנים, כך שגובהו קטן יחסית למספר האיברים שהוא מכיל.
• ערימה (heap) - עץ שבו כל צומת גדול (ערימת מקסימום) או קטן (ערימת מינימום) מבניו.
• איחוד קבוצות זרות (Union Find) - מבנה נתונים המאפשר מעקב אחר קבוצות זרות וביצוע איחוד שלהם, וחיפוש הקבוצה המתאימה לאיבר ביעילות גבוהה מאוד.
• Inode

שיקולים בבחירת מבנה נתונים

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

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

קישורים חיצוניים

• קורס באלגוריתמים ומבני נתונים ב־ArsDigita (הרצאות מוקלטות וחומרים)
• מאגר המידע השלם במבנה נתונים: הרצאות, מצגות וסיכומים, תרגילים. (עברית)