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