מילון (מבנה נתונים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 11:
== מימושים ==
מילון הוא מבנה נתונים אבסטרקטי (כלומר, הוא מגדיר [[מנשק]] אך חסר מימוש) וישנם מספר מבני נתונים אשר ניתן להשתמש בהם כדי למממש מילון. ההבדלים בין המימושים השונים רבים, ומתפרשים על פני [[סיבוכיות]] זמן ומקום של הפעולות השונות, תמיכה או חוסר-תמיכה ב[[מיון]] המילון לפי המפתחות, זכירת הסדר של הערכים שהוכנסו, וכמות ה[[זיכרון]] שנדרשת על-מנת לאחסן את מבנה הנתונים (ב[[זיכרון פנימי|זיכרון הפנימי
* '''[[טבלת גיבוב]]''' - טבלת גיבוב היא מימוש של מילון המאפשר הוספה וחיפוש של מפתחות ב[[סיבוכיות זמן]] של <math>O\left(1\right)</math> ב[[תוחלת]] ו-<math>O\left(n\right)</math> במקרה הגרוע ביותר. טבלת גיבוב לא מאפשרת מיון, ואינה זוכרת את הסדר בו הוכנסו האיברים.
* '''[[עץ אדום שחור]]''' - עץ אדום שחור מאפשר חיפוש והוספה של מפתחות בסיבוכיות זמן של <math>O\left(\log n\right)</math> גם במקרה הגרוע. בנוסף, הוא מאפשר איטרציה ממוינת לפי סדר המפתחות.
* '''[[עץ B Plus]]''' - מימוש בעל יתרונות יחסיים עבור מילונים גדולים במיוחד (לדוגמה, מרשם האזרחים של [[משרד הפנים]], או [[מילון אבן-שושן]]).
[[קטגוריה:מבני נתונים]]
[[en:Associative array]]
[[ca:Array associatiu (estructura de dades)]]
[[cs:Asociativní pole]]
[[de:Assoziatives Array]]
[[es:Vector asociativo]]
[[fr:Tableau associatif]]
[[ko:연관 배열]]
[[nl:Associatieve array]]
[[ja:連想配列]]
[[pl:Tablica asocjacyjna]]
[[pt:Vetor associativo]]
[[ru:Ассоциативный массив]]
[[fi:Hakurakenne]]
[[th:Associative Array]]
[[uk:Асоціативний масив]]
| |||