עזרה במבני נתונים

[aviaderi]

במסגרת הקורס באוניברסיטה נתנו לנו את השאלה הזאת:

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

יש לתמוך בפעולות הבאות: הכנסה, מחיקה לפי מספר זהות, חיפוש לפי שם.

תאר מבנה נתונים יעיל למימוש הפעולות הללו.

חשבתי על שימוש ב-MAP, אבל MAP ממיין ומכניס איברים לפי מפתח אחד שבוצע עליו HASHCODE.

השאלה שלי היא האם יש מבנה דומה לMAP שיכול למיין לפי 2 מפתחות?

תודה מראש,

אביעד

[Boomerang]

יש לך טעות. Map, כ- ADT - לא ממיין. הוא רק מאפשר שליפות לפי מפתח.

אתה יכול להחזיק שני Maps. באחד ה- key זה השם, ובשני ה- key זה מספר ת"ז.

בהכנסה - אתה מכניס לשני ה- maps.

במחיקה - אתה מחפש ב- map השני, מוצא את השם, מחפש אותו ב- map הראשון, ומוחק את שניהם.

[k-o-b-y]

אתה יכול להשתמש בשני map-ים, אחד עם ת.ז כמפתחות ואחד עם השם כמפתח. כשאתה מבצע הכנסה אתה מכניס את האובייקט לשני ה הmap-ים.

עריכה: בדיוק כשהגבתי גם Boomerang הציע את אותו הפתרון.

[aviaderi]

נכון, התכוונתי מאפשר שליפות לפי מפתח ולא מיון. טעות שלי.

הבנתי את הרעיון שלכם, ואני אראה איך אני מממש אותו.

בכל מקרה, הסיבוכיות נשארת (O(1 נכון?

[Boomerang]

בכל מקרה, הסיבוכיות נשארת (O(1 נכון?

כן, בתנאי שחישוב ה- Hash הוא (O(1 ומספר ה- hash collisions שלך חסום ע"י קבוע.

[aviaderi]

חישוב ההאש יהיה ללא תלות במספר האיברים,

hash collisions - לא זוכר שנתקלתי במושג הזה, תוכל לפרט קצת?

[adamshar]

מדובר באיברים שמתמפים לאותו מס' (תא) ע"י פונקצית ההאש.

התנגשויות נפתרות ע"י עץ אדום שחור בתאים שמחזיר ערך בזמן logN

[aviaderi]

תודה רבה לכם על העזרה,

אני יותר מאוחר אתחיל לממש את זה ואם יהיו לי בעיות אני אתיעץ איתכם.