מבנה נתונים

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

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

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

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

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

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

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

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

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

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