עדכון בעבודה 3 + הבהרה

מנהל: TA_Isana

שלח תגובה
TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

עדכון בעבודה 3 + הבהרה

שליחה על ידי TA_Yoni » 17:50 14/04/2010

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

כמו כן הבהרה:

במשימה 3 עליכם למחוק איבר מהעץ. הכוונה במשפט : "על שיטה זו להחזיר את האבא של האיבר אותו אנו מסירים מהעץ" היא להחזיר את האבא של הקודקוד שיוצא מהעץ . כלומר אם לאיבר שאותו אנו רוצים להסיר מהעץ יש שני בנים בעץ הרי שע"פ האלגוריתם יש לחליף אותו עם ה successor שלו ואז יש להחזיר את האבא של ה successor (כי הוא הקודקוד שיוצא מהעץ)


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


הכוונה בלהעדיף רוטציה אחת על שתיים : היא שאם נוצר מצב שיש חוסר איזון [גם כמקרה 1 וגם כמקרה 3] או [כמקרה 2 וגם כמקרה 4] (בהתאם למקרים שבשקפים ) אזי להעדיף את מקרה 1 ו 2 ( רוטציה בודדת על פני שתי רוטציות )
נערך לאחרונה על ידי TA_Yoni ב 12:23 15/04/2010, נערך 2 פעמים בסך הכל.
המתרגל יוני

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי בר כהן » 18:17 14/04/2010

איפה היית שלשום איפה?? :mrgreen:

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי TA_Yoni » 19:42 14/04/2010

שוב בר, סליחה אישית. תודה על שהפנת את תשומת ליבנו.
המתרגל יוני

kes6
הודעות: 25
הצטרף: 12:14 22/09/2008

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי kes6 » 20:13 16/04/2010

בקשר להערה האחרונה לגבי כמות הרוטציות -

מה המשמעות של חוסר איזון כמקרה 1 או כמקרה 2? הרי בכל מקרה של חיסור איזון, יהיה מדובר באחד המצבים, ובהתאם לכך כמות הרוטציות, הלא כן?

חן חן ושבת שלום

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי TA_Yoni » 21:04 16/04/2010

הכוונה למצב כזה (אנסה לסרטט) :

קוד: בחירת הכל

     
                             *
                              \
                               *
                              / \
                            *     *
המתרגל יוני

kes6
הודעות: 25
הצטרף: 12:14 22/09/2008

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי kes6 » 12:43 17/04/2010

על הכיפאק, תודה. עוד שאלה קטנה בשרותך -

אם אני מבין נכון, השיטה remove במחלקה AVLSearchTree, שאותה מממשים במשימה 3, אמורה להתבסס על remove של BST שמימשנו במשימה 3 - להוריד, ואז לתקן את העץ.
אך בהרצאה ראינו שבניגוד להוספת איבר לעץ, שלב ההורדה מתנהג בצורה שונה בין עץ חיפוש רגיל ועץ AVL (ובפרט, במקרה של בן יחיד ההוצאה מסובכת יותר, ודורשת את מציאת ה - predeccessor).

אם כך, האם צריך להוסיף פונקציית remove ספציפית עבור AVLSearchNode?

תודה רבה.

Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי Brk » 14:13 17/04/2010

TA_Yoni כתב:הכוונה למצב כזה (אנסה לסרטט) :

קוד: בחירת הכל

     
                             *
                              \
                               *
                              / \
                            *     *
תגיד לי אם אני מבין,אתה רוצה שבבחירת הx,y,z,אני אבחר במתאימים שיתנו לי רק רוטציה אחת במקום 2?
הרי המצב שאתה תיארת פה לא יתרחש אצלי לפחות כי לאחר הכנסת שורש ועוד שני קודוקים מימין לשורש,נקבל מצב לא מאוזן-שיש צורך ברוטציה אחת שאותה נבצע לאחר ההכנסה.אז בכלל נגיע לא למצב אתה מתאר,אם זה יהיה מאוזן לאחר הכנסה של שלושה קודקדים רצוף ימין ימין ימין,או ימין ימין שמאל

matandro
הודעות: 68
הצטרף: 15:16 26/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי matandro » 20:41 17/04/2010

וואו טוב שאמרת אז זה כי פספסתי מקרה בעייתי
טיפלתי בroot עם שני בנים בעץ ואז לא איזנתי כמו שצריך את האבא של ה-succ
ולמרות הבעיה הזאת קיבלתי תוצאות זהות לבדיקה שננתם כי אין שם הסרה שכזאת

מה שמדגיש שמומלץ להוסיף עצי בדיקה שמתעסקים בהם בפעולות על השורש ומקרי קיצון שכאלה

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי TA_Yoni » 21:20 17/04/2010

המצב שתארתי יכול להתרחש בעת הוצאת איבר
המתרגל יוני

Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי Brk » 23:33 17/04/2010

TA_Yoni כתב:המצב שתארתי יכול להתרחש בעת הוצאת איבר
תודה עזרת לי :o

sheknabs
הודעות: 31
הצטרף: 17:03 12/11/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי sheknabs » 22:22 18/04/2010

האם ההבהרה הזו זה משהו שכתוב בעבודה באיזשהו אופן סמוי או משהו כזה?
הכוונה בלהעדיף רוטציה אחת על שתיים : היא שאם נוצר מצב שיש חוסר איזון [גם כמקרה 1 וגם כמקרה 3] או [כמקרה 2 וגם כמקרה 4] (בהתאם למקרים שבשקפים ) אזי להעדיף את מקרה 1 ו 2 ( רוטציה בודדת על פני שתי רוטציות )
כי חיפשתי ולא מצאתי ואם לא האם חובה לעשות כך? או שרק מומלץ?
אני שואל כי אני יודע שהבדיקה היא אוטומטית ולכן אתם תשוו פלטים ולכן אם לא נעשה בדיוק לפי איך שאתם מצפים שנעשה למרות שגם הפלט שלנו יהיה נכון הניקוד בבדיקות הספציפיות שנוגעות למקרה זה יזכו ב0 נקודות.

אשמח לתשובה ממתרגל או מרצה.

תודה.

TA_Raz
הודעות: 12
הצטרף: 11:34 21/03/2010

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי TA_Raz » 08:31 19/04/2010

חובה, כי הבדיקה היא אוטומטית.
המתרגל רז

shaysw
הודעות: 78
הצטרף: 16:23 08/11/2008

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי shaysw » 17:14 27/04/2010

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

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי TA_Yoni » 19:59 27/04/2010

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

shaysw
הודעות: 78
הצטרף: 16:23 08/11/2008

Re: עדכון בעבודה 3 + הבהרה

שליחה על ידי shaysw » 20:04 27/04/2010

לא יכולתי לבקש תשובה טובה יותר, תודה

שלח תגובה

חזור אל “- מבני נתונים 2010”