שאלה שקיבלתי לשיעורי בית !!! (מבנה נתונים)

[שייקה 84]

שאלה שקיבלתי לשיעורי בית !!! (מבנה נתונים)

3. You are given two BST. Write a pseudo-code that merge them into one BST. Analyze its time complexity. You may use find functions but may not use insert function. בתרגום חופשי: נתונים 2 עצי חיפוש ביאנרים, עליך לממש קוד שממזג אותם לעץ אחד. עכשיו הקטע פה זה שהוא לא מרשה שניקח כל פעם קודקוד ונוסיף אותו לעץ השני, כי אז זה יוצא סיבוכיות של n * log n והמרצה רוצה שזה יהיה בסיבוכיות log n יש למישהו רעיון איך לעשות את זה ???

 

[טרמפיסט]

ומה אומר על זה פרופ' דולב?

 

[שייקה 84]

איפה כל התותחים שיש פה בדר"כ ... ?

 

[gmorphus]

עובדים בשביל בובי ולנטינו

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

 

[שייקה 84]

בלתי אפשרי

חשבתי על זה, זה לא עובד. תנסה לעשות את זה עם העצים הבאים : 1 4 7 3 5 6 (תמונה מצורפת...) אתה לא יכול פשוט לשים את העץ הימני מתחת ל 7 כי יש לך מתחתיו את ה 3 שהוא קטן מ 4 אז הוא לא יכול להיות בתת-עץ הימני שלו

 

[gmorphus]

הממ... השעה השפיעה עלי ../images/Emo13.gif צודק...

 

[HaifaMan]

logn ? בטוח?

זה נשמע לי מוגזם.. אני יודע איך ניתן לעשות את זה ב-n ....

 

[שייקה 84]

כן כן ! בסיבוכיות של n. התבלבלתי....

איך עושים את זה בסיבוכיות של n ?

 

[HaifaMan]

רעיון אחד למשל -

תעשה סיור INORDER על 2 העצים ותשים כל עץ במערך. המערכים יהיו ממויינים לכן מיזוג שלהם מתבצע בO של n. אחרי שיש לך מערך אחד ממויין ארוך - תיצור עץ כמעט מלא בגודל המערך הגדול ותשים שם את האיברים, שוב בסיור inorder.

 

[שייקה 84]

לא הבנתי :/

יש עוד רעיון יותר פשוט אולי ?

 

[HaifaMan]

מה לא הבנת?

למדת מה זה סיור INORDER על עץ בינארי?