2005 סמס' א' מועד א' - שאלה 3

מנהלים: TA_nimrod, TA_Igor, TA_Adi

שלח תגובה
sheknabs
הודעות: 31
הצטרף: 17:03 12/11/2009

2005 סמס' א' מועד א' - שאלה 3

שליחה על ידי sheknabs » 23:36 21/01/2010

זו השאלה:
שאלה זאת עוסקת במחלקה BST שנלמדה בכיתה. המחלקה BST יורשת מהמחלקה BTree ומייצגת עץ חיפוש בינארי. להזכירכם, המחלקה הפנימית BSN יורשת מ-BNode ומייצגת צומת בעץ חיפוש בינארי. קוד המחלקה הרלוונטי לשאלה זו נתון בנספח של מבחן זה(עמ' 11,12).

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

בחלקים א' ו-ב' של שאלה זו תוסיפו למחלקה BST, ולמחלקה הפנימית BSN, את השיטה kElement המחזירה את האיבר ה-k בגדלו בעץ. פתרונות המבצעים סריקה מלאה של העץ יזכו בניקוד נמוך. להזכירכם, כל האיברים בעץ חיפוש בינארי שונים זה מזה.
הפתרון במחלקה BSN הוא:

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

int rightsize = 0;
if (right != null)
    rigthsize = right.size();
if (rightsize >= k)
    return right.kElement(k);
else if (rightsize + 1 == k)
    return this.data;
else
    return left.kElement(k - rightsize - 1);
אשמח אם מישהו מהמתרגלים/מרצים יוכל להסביר לי למה הפתרון שלהם בכלל עובד?

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

Re: 2005 סמס' א' מועד א' - שאלה 3

שליחה על ידי TA_Yoni » 00:00 22/01/2010

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

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

if (right != null)
    rigthsize = right.size();
( במידה וקיים תת עץ ימני - במידה ולא מיד אסביר מה קורה) . כעת , אם גודל תת העץ הימני גדול ממש מ K אני יודע כי האיבר ה K נמצא בתת העץ הימני ולכן מתבצעת קריאה רקורסיבית עבור תת העץ הימני :

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

if (rightsize >= k)
    return right.kElement(k);
במידה ו K שווה לגודל תת העץ הימני + 1 אני יודע כי עצם המפתח הוא האיבר ה K בגודלו בעץ ( כי הוא האיבר הגדול ביותר שקטן מכל איברי תת העץ הימני ) ולכן אני אחזיר אותו ( את ה DATA שלו ):

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

else if (rightsize + 1 == k)
    return this.data;
במידה וכל התנאים הנ"ל לא התקיימו אני יודע כי גודל תת העץ הימני קטן ממש מ K-1 ולכן האיבר ה K בגודלו נמצא בתת העץ השמאלי.
כמה איברים כבר "בדקנו"? בדיוק גודל תת העץ הימני + 1 ( עצם המפתח ). ולכן יש קריאה רקורסיבית עבור האיבר ה(k - rightsize - 1) בגודלו בתת העץ השמאלי.

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

else
    return left.kElement(k - rightsize - 1);
(*) במידה ולא קיים תת העץ ימני אז גודלו הוא 0 והתוכנית עדין נכונה.


מקווה שעזר במשהו :)

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

Re: 2005 סמס' א' מועד א' - שאלה 3

שליחה על ידי sheknabs » 19:58 22/01/2010

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

תודה.

שלח תגובה

חזור אל “- מבוא למדעי המחשב 2010”