דף 1 מתוך 1

מבחן 2002

נשלח: 23:32 19/04/2010
על ידי Brk
ב. נתונים שני עצי חיפוש בינאריים T1 עם n1 קודקודים וגובה h1 , ו- T2 עם
n2 קודקודים וגובה h2 . נתון גם כי המפתח המקסימלי ב- T1 קטן מהמפתח
המינימלי ב- T2 . השלם: ניתן למזג את שני העצים כך שיתקבל עץ חיפוש
בינארי יחיד שגובהו לכל היותר max(h1 , h2) + 1 בזמן


זה משאלה 1,בחרתם max(h1,h2) או min(h1,h2)

Re: מבחן 2002

נשלח: 11:55 20/04/2010
על ידי lironsam
נראה לי שזה המינימום בין השניים
כי אם הגובה של T1 ( עם המפתחות הקטנים יותר) הוא המינימלי - אתה לוקח בו את המקסימום בתור השורש וכך בונה את העץ שלך ( T1 ללא המקסימום תת עץ שמאלי וT2 תת עץ ימני) כלומר אתה עובר רק על T1 ולכן הזמן ריצה הוא O(h1)
ואם הגובה של T2 הוא המינימלי - אתה לוקח בו את המינימום בתור השורש וכך בונה את העץ ( על אותו עיקרון ממקודם)

בהנחה שאתה יודע מי מבין השניים הוא הגבוה יותר.... הזמן ריצה לדעתי, הוא המינימלי מביניהם

Re: מבחן 2002

נשלח: 19:37 20/04/2010
על ידי Brk
לא ידוע הגובה,עדיין ההתלבטות עומדת בעינה :shock:

Re: מבחן 2002

נשלח: 20:42 20/04/2010
על ידי lironsam
אני כמעט בטוחה שזה מינימום
בתרגול 5 שאלה 7 רשום גם:

1. How can you merge T1 and T2 into one binary search tree in time O(min(h1,h2))
so that the height of the merged tree will be minimal?

Re: מבחן 2002

נשלח: 18:35 22/04/2010
על ידי igormi
פשוט אתה עובר על העצים באותו הזמן.
על T1 אתה זז ימינה וT2 אתה זז הכי שמאלה.
כשאתה מגיעה לכך שלT1 אין בן ימני ואתה עוצר אותו הדבר עם T2 והבן השמאלי.
לכן הזמן שיקח לך הוא ((O(min(h1,h2.
אני מקווה שלא התבלבלתי עם הכיוונים.