מילון (מבנה נתונים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←פעולות מילון: הרחבה |
←מימושים: הרחבה |
||
שורה 14:
המימושים הנפוצים ביותר למילון הם:
* '''[[מערך (מבנה נתונים)|מערך]]''' - במקרה שבו המפתחות מהווים טווח צר של מספרים (או קיים מיפוי חד-ערכי פשוט מהמפתחות אל טווח צר של מספרים), וכאשר הערכים בטווח הם בעלי אותו טיפוס, ניתן לממש מילון על ידי הצבת הערכים כשהם רצופים בזיכרון, וביצוע המיפוי בזמן הגישה. כאשר המיפוי איננו מורכב יותר מפעולות חיסור או חיבור של מספר קבוע, מבנה זה נקרא מערך, והוא מקרה פרטי של טבלת גיבוב בה ידוע מראש שלא יהיו התנגשויות. מימוש זה הוא היעיל ביותר, מבחינת זמן הריצה, כאשר הוא ניתן לביצוע: זמן הגישה האסימפטוטי איננו תלוי במספר האיברים במערך. מידת היעילות בהיבט המקום עומדת ביחס ישר למידת צפיפות המפתחות בהם נעשה שימוש: עבור מפתחות צפופים מערך יהיה חסכוני במקום, ואידיאלי כאשר נעשה שימוש בכל המפתחות. עבור מפתחות מפוזרים ייתכן כי טבלת גיבוב או עץ יהיו חסכוניים יותר.
* '''[[טבלת גיבוב]]''' - מימוש של מילון הבא לפתור את הבעיה המתוארת במימוש מערך באמצעות [[פונקציית גיבוב]]. מימוש זה מאפשר הוספה וחיפוש של מפתחות ב[[סיבוכיות זמן]] של <math>O\left(1\right)</math> ב[[תוחלת]]
* '''[[עץ אדום שחור]]''' - מימוש של מילון המאפשר חיפוש והוספה של מפתחות בסיבוכיות זמן של <math>O\left(\log n\right)</math> גם במקרה הגרוע. בנוסף, הוא מאפשר איטרציה ממוינת לפי סדר המפתחות.
* '''[[עץ B Plus]]''' - מימוש בעל יתרונות יחסיים עבור מילונים גדולים במיוחד (לדוגמה, מרשם האזרחים של [[משרד הפנים]], או [[מילון אבן-שושן]]).
* '''מערך ממויין''' - אם הבניה של המילון והגישה אליו הן שתי פאזות שונות, ואם מוגדר יחס סדר על האיברים, אפשר לבנות את המילון במערך לא ממויין, למיין אותו, ואז לבצע גישות באמצעות חיפוש בינארי. זהו מימוש של [[עץ חיפוש]] בינארי בסיבוכיות מקום נוסף <math>O\left(1\right)</math>, על חשבון סיבוכיות הזמן במעבר בין הפאזות.
מימוש באמצעות עצים או מערך ממויין דורש הגדרה של [[יחס סדר]] מלא בין המפתחות. מימוש באמצעות טבלת גיבוב דורש הגדרה של פונקציית גיבוב (למציאת התא המתאים בטבלה) ושל בדיקת שוויון (בין המפתחות שבאותו תא).
מימושים בעזרת עצים אינם דורשים דבר מבחינת מספר האיברים במילון, לעומת מימושים בעזרת מערך ממויין או טבלת-גיבוב הדורשים טיפול מיוחד בשינוי גודל המערך, ולכן סיבוכיות הזמן של פעולת הכנסה בודדת איננה צפויה (שלא כמו הסיבוכיות הממוצעת). למימושים בעזרת מערך לוקליות גבוהה ביחס למימושים בעזרת טבלאות גיבוב או עצים.
כל המימושים אוסרים שינוי לא מבוקר של מפתחות הנמצאים בתוך המילון.
מילון בו המפתחות הם הערכים הוא למעשה [[קבוצה (מבנה נתונים)|קבוצה]].
| |||