मान लीजिए हमारे पास n अलग-अलग नोड्स हैं। सभी अलग हैं। हमें यह ढूंढना है कि उन्हें बाइनरी सर्च ट्री बनाने के लिए कितने तरीकों से व्यवस्थित किया जा सकता है। जैसा कि हम जानते हैं बाइनरी सर्च ट्री के लिए, लेफ्ट सबट्री हमेशा छोटे मान रखती है और राइट सबट्री बड़े मान रखती है।
इसे हल करने के लिए, हम कैटलन नंबर ढूंढेंगे। कैटलन नंबर 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
- i के लिए 0 से r - 1 तक की रेंज में, करें
- res := res *(n - i)
- res := (res/(i + 1)) का फ्लोर
- res लौटाएं
- मुख्य मेथड से, निम्न करें
- 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
