תרגיל 4 שאלה 2 הוכח או הפרך סעיף ב,ג

מנהל: TA_Isana

תרגיל 4 שאלה 2 הוכח או הפרך סעיף ב,ג

הודעהעל ידי halpertc » 18:50 10/06/2009

האם הכוונה היא לבנות עץ חדש? או להשתמש בשינוי מצביעים בלבד?
halpertc
 
הודעות: 6
הצטרף: 14:01 29/04/2009

הודעהעל ידי TA_Lena » 21:49 11/06/2009

הכוונה היא להחזיר עצים העומדים בדרישות שבסעיפים.
TA_Lena
 
הודעות: 141
הצטרף: 13:46 22/04/2009

הודעהעל ידי litanil » 07:54 14/06/2009

הניחוש שלי הוא שיש צורך בהחלפת עצים ולא ביצירת חדשים.
כי הרי זמן יצירת עץ חדש בעל n איברים (כל עץ, AVL או סתם בינארי רגיל) הוא n*log(n), ומן הסתם זה סותר מראש את הטענות בסעיפים האלה.... (בלי קשר אם הם נכונים בסוף או לא)
litanil
 
הודעות: 46
הצטרף: 12:17 24/11/2008

הודעהעל ידי nivv » 19:57 15/06/2009

קוד: בחר הכל
maybe it is possible to do it in O(n+m)
1. pull n keys from tree to a heap - cost O(n)
2. same for m keys - cost O(m)
3. merge the two heaps - cost O(m+n)
4. build a new tree from a sorted heap - cost O(n+m)

now my only problem is making sure I can get 4. done.
suppose I go to the center on the sorted heap and choose it as the root for the new tree, then swing right and left to create the right and left childs.

[b]DOES THIS MAKE ANY SENSE?[/b]

[/b]
nivv
 
הודעות: 5
הצטרף: 19:48 03/12/2008


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד