मान लीजिए कि हमारे पास अलग-अलग नोड हैं। सभी अलग हैं। हमें यह पता लगाना है कि हम उन्हें कितने तरीकों से व्यवस्थित कर सकते हैं ताकि हम बाइनरी सर्च ट्री बना सकें। जैसा कि हम बाइनरी सर्च ट्री के बारे में जानते हैं, लेफ्ट सबट्री में हमेशा छोटे मान होते हैं और राइट सबट्री में बड़े मान होते हैं।
इसे हल करने के लिए, हम कैटलन संख्या ज्ञात करेंगे। कैटलन संख्या C(n) n भिन्न कुंजियों वाले बाइनरी सर्च ट्री का प्रतिनिधित्व करती है। सूत्र इस प्रकार है
$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$
इसलिए, यदि इनपुट n =3 जैसा है, तो आउटपुट 5 होगा क्योंकि
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन को परिभाषित करें ncr() । इसमें n, r लगेगा
- res :=1
- यदि r> n - r, तो
- r :=n - r
- मैं के लिए 0 से r -1 की सीमा में, करो
- res :=res *(n - i)
- res :=(res/(i + 1)) की मंजिल
- रिटर्न रेस
- मुख्य विधि से, निम्न कार्य करें
- c :=ncr(2 * n, n)
- c /(n + 1) का रिटर्न फ्लोर
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
from math import factorial def ncr(n, r): res = 1 if r > n - r: r = n - r for i in range(r): res *= (n - i) res //= (i + 1) return res def solve(n): c = ncr(2 * n, n) return c // (n + 1) n = 3 print(solve(n))
इनपुट
3
आउटपुट
5