דף 1 מתוך 1

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

נשלח: 23:36 21/01/2010
על ידי sheknabs
זו השאלה:
שאלה זאת עוסקת במחלקה 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);
אשמח אם מישהו מהמתרגלים/מרצים יוכל להסביר לי למה הפתרון שלהם בכלל עובד?

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

נשלח: 00:00 22/01/2010
על ידי TA_Yoni
צריך להאמין ברקורסיה כדי להבין את הפתרון:
ראשית, כדי שיהיה איבר 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 והתוכנית עדין נכונה.


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

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

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

תודה.