מבחן 2002

מנהלים: TA_Isana, TA_Isana

שלח תגובה
Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

מבחן 2002

שליחה על ידי Brk » 23:32 19/04/2010

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


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

lironsam
הודעות: 25
הצטרף: 23:12 04/12/2009

Re: מבחן 2002

שליחה על ידי lironsam » 11:55 20/04/2010

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

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

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

Re: מבחן 2002

שליחה על ידי Brk » 19:37 20/04/2010

לא ידוע הגובה,עדיין ההתלבטות עומדת בעינה :shock:

lironsam
הודעות: 25
הצטרף: 23:12 04/12/2009

Re: מבחן 2002

שליחה על ידי lironsam » 20:42 20/04/2010

אני כמעט בטוחה שזה מינימום
בתרגול 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?

igormi
הודעות: 7
הצטרף: 00:28 12/11/2009

Re: מבחן 2002

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

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

שלח תגובה

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