מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/נוסחת נסיגה למספר עצי שונים/שאלה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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



דוגמה:

נניח שעץ החיפוש מכיל את המפתחות . יש 2 עצים מתאימים:

עצי חיפוש בינריים בעלי המפתחות 1 ו2.

נניח שעץ החיפוש מכיל את המפתחות . יש 5 עצים מתאימים:

עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.



מהדוגמה נוכל להסיק כי

, , .


אנא הוכח את המשפט הבא.



משפט:

אם , אז .