קבוצה (מבנה נתונים)

קבוצה (באנגלית Set) היא סוג של מבנה נתונים מופשט שכל ערך מופיע בו לכל היותר פעם אחת, ואין חשיבות לסדר בין הערכים. מימוש של קבוצה הוא למעשה ייצוג ממוחשב של קבוצה מתמטית סופית.

אפשר להגדיר קבוצה כמקרה פרטי של מבני נתונים אחרים: רשימה בה מתעלמים מהסדר ולא מאפשרים הוספה של ערכים קיימים, או מילון שהמפתחות שלו הם הפריטים עצמם, והערכים בו הם קבוע כלשהו.

קבוצה תיקרא סטטית, אם לא ניתן להוסיף אליה או להוריד ממנה ערכים לאחר יצירתה, או דינמית אם לפחות אחת מפעולות אלה מותרת. קבוצה סטטית מאפשרת לבדוק האם פריט מסוים נמצא בה, האם היא ריקה, מה מספר האיברים בה וכדומה. מימוש של קבוצה דינמית יאפשר, בנוסף לאלה, ליצור קבוצה חדשה בעלת תכולה מוגדרת, להוסיף פריט, להסיר פריט, לבצע פעולות איחוד וחיתוך בין קבוצות ועוד.

ניתן לממש קבוצה בדרכים רבות, ובין המימושים ישנם הבדלים בסיבוכיות של פעולות ובפשטות המימוש. בין המימושים הנפוצים של קבוצה:

• מערך הוא המימוש הפשוט ביותר.
• טבלאות גיבוב המאפשרות סיבוכיות $\ {\mathcal {O}}(1)$ במקרה הממוצע אבל $\ {\mathcal {O}}(n)$ במקרה הגרוע, ברוב ההקשרים.
• עצים המאפשרים סיבוכיות $\ {\mathcal {O}}(\log(n))$ למציאת פריט. מימוש קבוצה בעזרת עץ דורש הגדרה של סדר כלשהו בין איברי הקבוצה, אך סדר זה מוגדר במטרה לשפר יעילות ולא משנה את הגדרת הטיפוס. כמו כן, מימושים רבים של קבוצה כעץ אינם מאפשרים שינוי של פריט בקבוצה על מנת לא לפגוע בסדר שהוגדר בעץ, וכדי לשנות פריט יש להוציא אותו מהקבוצה, לשנות אותו ואז להחזיר.

קבוצה המאפשרת קיום של מספר פריטים בעלי אותו ערך נקראת מולטי קבוצה.

קישורים חיצוניים

• קבוצה, באתר MathWorld (באנגלית)