B-Trees שאלה

מנהל: TA_Isana

B-Trees שאלה

הודעהעל ידי eliorar » 23:38 15/07/2010

השאלה לקוחה מהספר של קורמן (שאלה 18-2.4) ואין לי מושג איך לענות עליה...
Suppose that the keys {1, 2, ..., n} are inserted into an empty B-tree with minimum degree 2.
How many nodes does the final B-tree have?

ובתרגום חופשי:
נניח שמכניסים את המפתחות {1, 2, ..., n} לעץ b ריק שדרגת המינימום שלו 2. כמה צמתים יש בעץ הסופי?

יש לזה נוסחא קבועה? כי זה ממש תלוי בסדר הכנסת האיברים, אם הם מוכנסים לפי הסדר אז אחרי כל 4 איברים מתבצע פיצול ואז בעצם נוסף קודקוד חוץ מהפעם שהקודקוד מלא ואז הפיצול יוצר 2 קודקודים נוספים, אבל חוץ מזה לא ממש הגעתי לנוסחא כלשהי..
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

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

מי מחובר

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

cron