עמוד 1 מתוך 1

B-Trees שאלה

הודעהפורסם: 23:38 15/07/2010
על ידי eliorar
השאלה לקוחה מהספר של קורמן (שאלה 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 קודקודים נוספים, אבל חוץ מזה לא ממש הגעתי לנוסחא כלשהי..