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

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

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

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

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

אנא הוכח ש$\displaystyle T(n)=\Omega (2^{n})$, כלומר שמספר עצי החיפוש הבינריים גדל בצורה אקספוננציאלית.