דף 1 מתוך 1

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

נשלח: 19:50 10/06/2009
על ידי halpertc
האם הכוונה היא לבנות עץ חדש? או להשתמש בשינוי מצביעים בלבד?

נשלח: 22:49 11/06/2009
על ידי TA_Lena
הכוונה היא להחזיר עצים העומדים בדרישות שבסעיפים.

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

נשלח: 20:57 15/06/2009
על ידי nivv

קוד: בחירת הכל

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]