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