טיפוס נתונים מופשט
במדעי המחשב, טיפוס נתונים מופשט (Abstract Data Type או ADT) הוא מודל מתמטי עבור קבוצה מסוימת של מבני נתונים בעלי התנהגות דומה, או עבור טיפוסי נתונים שונים בשפות תכנות להם סמנטיקה דומה, ומאפשר הפשטה שלהם. טיפוס נתונים מופשט מוגדר על ידי הפעולות שניתן לבצע עליו ועל ידי מגבלות שחלות על תוצאות הפעולות האלה (או העלות שלהן מבחינת סיבוכיות זמן ומקום).
לדוגמה, מחסנית היא טיפוס נתונים מופשט הכולל פעולת (Push) שמוסיפה איבר, פעולת (Pop) שמסירה את האיבר האחרון שנוסף למחסנית, ופעולת Peek המאפשרת גישה למידע בראש המחסנית ללא הסרתו. בהקשר של ניתוח סיבוכיות של אלגוריתמים העושים שימוש במחסנית, ניתן להוסיף דרישות המקילות את ניתוח הסיבוכיות: זמן קבוע לכל פעולה, ללא תלות בכמות הנתונים במחסנית, ושטח זיכרון קבוע עבור כל איבר.
מבני נתונים מופשטים הם ישויות מתמטיות, העוזרות לפשט תיאורים של אלגוריתמים, ובפרט לאפשר הוכחת נכונות שלהם, שעשויה להיעזר דווקא בהגבלות על הגישה למידע השמור בהם. למשל, אלגוריתם חיפוש לעומק משתמש בטיפוס הנתונים המופשט מחסנית וכך ניתן להוכיח את נכונותו באופן אלגנטי כיוון שגישה לנתונים מתבצעת אך ורק בסדר LIFO, ואין צורך להתייחס למימוש ספציפי (שעשוי לאפשר או לא לאפשר גישה אל אמצע המחסנית).
כמו כן מאפשרים מבני הנתונים המופשטים לסווג מבני נתונים, ולתאר באופן פורמלי את מערכות הטיפוסים של שפות תכנות. ניתן לממש מבני נתונים בעזרת טיפוסי נתונים או מבני נתונים שונים, בשפות תכנות שונות.
מבני נתונים מופשטים ממומשים לעיתים קרובות על ידי מודולים: ממשק המודול מכריז על הפונקציות המממשות את הפעולות של מבנה הנתונים, לעיתים בתוספת הערות המתארות את המגבלות. כך המימוש של מבנה הנתונים מוסתר מהמשתמש ומאפשר שינוי של המימוש בלי להשפיע על תוכניות המשתמש.
ניתן להתייחס למושג טיפוס נתונים מופשט כהכללה של מבנים אלגבריים כגון סריגים, חבורות וחוגים.
הגדרת מבנה נתונים מופשט
מבנה נתונים מופשט מוגדר כמודל מתמטי של עצמים של נתונים עם הפעולות המוגדרות עליהם. אין מוסכמות סטנדרטיות להגדרה שלהם. ניתן לחלק באופן בסיסי לשני סגנונות של הגדרה של מבני נתונים: ״אימפרטיבי״ ו-״פונקציונלי״.
| מבני נתונים | ||
|---|---|---|
| מבנים מופשטים | רשימה • מחסנית • קבוצה • רב קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
| גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • טריי X מהיר • טריי y מהיר• עץ WAVL | |
| הסתברותיים | מסנן בלום | |
קישורים חיצוניים
