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

מנהל: TA_Isana

שלח תגובה
halpertc
הודעות: 6
הצטרף: 15:01 29/04/2009

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

שליחה על ידי halpertc » 19:50 10/06/2009

האם הכוונה היא לבנות עץ חדש? או להשתמש בשינוי מצביעים בלבד?

TA_Lena
הודעות: 141
הצטרף: 14:46 22/04/2009

שליחה על ידי TA_Lena » 22:49 11/06/2009

הכוונה היא להחזיר עצים העומדים בדרישות שבסעיפים.

litanil
הודעות: 46
הצטרף: 12:17 24/11/2008

שליחה על ידי litanil » 08:54 14/06/2009

הניחוש שלי הוא שיש צורך בהחלפת עצים ולא ביצירת חדשים.
כי הרי זמן יצירת עץ חדש בעל n איברים (כל עץ, AVL או סתם בינארי רגיל) הוא n*log(n), ומן הסתם זה סותר מראש את הטענות בסעיפים האלה.... (בלי קשר אם הם נכונים בסוף או לא)

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

שליחה על ידי nivv » 20: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]

שלח תגובה

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