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

בשאלה זו עליך להוכיח חסם תחתון על $\displaystyle T(n)$ , מספר עצי החיפוש הבינריים השונים בעלי $\displaystyle n$ מפתחות שונים זה מזה.

דוגמה:

נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1, 2$ . יש 2 עצים מתאימים:

נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1, 2, 3$ . יש 5 עצים מתאימים:

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

$\displaystyle T(0) = T(1) = 1$ , $\displaystyle T(2) = 2$ , $\displaystyle T(3) = 5$ .

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

משפט:

אם $\displaystyle n > 1$ , אז $\displaystyle T(n) = \sum_{i = 0}^{n - 1}[T(i) \cdot T(n - i - 1)]$ .