एन विशिष्ट तत्वों से कितने बाइनरी खोज पेड़ का निर्माण किया जा सकता है? और हम इसके लिए गणितीय रूप से साबित सूत्र कैसे प्राप्त कर सकते हैं?एन विशिष्ट तत्वों पर बाइनरी खोज पेड़ों की संख्या
उदाहरण: हम 3 अलग-अलग एलीमेंट है, तो कहते हैं कि 1, 2, 3, वहाँ 5 द्विआधारी खोज के पेड़ हैं।
को देखते हुए n तत्वों, द्विआधारी खोज के पेड़ है कि उन तत्वों से बनाया जा सकता की संख्या n वें Catalan number (निरूपित किया जाता सी n) द्वारा दिया जाता है। यह
के बराबर है Intuitively, कातालान संख्या तरीके हैं जिनसे आप n तत्वों कि निम्नलिखित तरीके से किया जाता है के बाहर एक संरचना बना सकते हैं की संख्या का प्रतिनिधित्व करते हैं:
यह पैटर्न पूरी तरह से उन तरीकों से मेल खाता है जिनमें आप एन तत्वों के सेट से बीएसटी बना सकते हैं। पेड़ की जड़ के रूप में उपयोग करने के लिए एक तत्व चुनें। सभी छोटे तत्वों को बाईं ओर जाना चाहिए, और सभी बड़े तत्वों को दाईं ओर जाना चाहिए। वहां से, आप बाएं और दाईं ओर तत्वों से छोटे बीएसटी बना सकते हैं, फिर एक समग्र बीएसटी बनाने के लिए रूट नोड के साथ उन्हें एक साथ फ्यूज करें। एन तत्वों के साथ आप इसे करने के तरीकों की संख्या सी एन द्वारा दी गई है, और इसलिए संभावित बीएसटी की संख्या एन कैटलन संख्या द्वारा दी गई है।
आशा है कि इससे मदद मिलती है!
उदाहरण के लिए नोड्स 10, 10, 10 के लिए बाइनरी खोज पेड़ की संख्या 1 है। लेकिन कैटलन संख्या 5 है। लेकिन यदि सभी तत्व अलग हैं तो यह ठीक है। –
@ सुखानोवनिस्कोले बीएसटी की संख्या अभी भी 10,10,10 के लिए 5 है। पेड़ का आकार अलग होगा। – rents
टी (एन) एन तत्वों के बीएसटी की संख्या होने दें।
एन विशिष्ट आदेशित तत्वों को देखते हुए, 1 से n क्रमांकित, हम रूट को चुनते हैं।
यह टी (i-1) संयोजनों के लिए बाएं उपट्री में (1..i-1) और (i + 1.)) टी (एन-आई) संयोजनों के दाएं उपट्री में छोड़ देता है।
इसलिए:
T(n) = sum_i=1^n(T(i-1) * T(n-i))
और पाठ्यक्रम टी की (1) = 1
यह उल्लेख करना अच्छा हो सकता है कि यह पुनरावृत्ति एनथ कैटलन संख्या में हल हो जाती है। – templatetypedef
@templatetypedef: क्या आप जानते हैं कि मैंने जो योग दिखाया है उससे शुरू होने वाला अनुमान संख्या फॉर्मूला कैसे प्राप्त करें? –
@ user1131467 यह योग वास्तव में एन + 2 नोड्स पर बहुभुज के त्रिभुज की संख्या होना चाहिए, जिस तरह से मुझे कैटलन संख्याओं के साथ पेश किया गया था। आप किनारे को ठीक करते हैं और पिवट को अन्य एन कोष्ठकों पर घूमते हैं, जो आपको दो बहुभुज आकार I-1 और n-i के साथ छोड़ देता है। –
मुझे यकीन है कि इस सवाल का सिर्फ एक गणितीय सूत्र का उपयोग कर की गणना नहीं है कर रहा हूँ .. मैं बाहर कुछ समय लिया और लिखा था कार्यक्रम और इसके लिए गणना के पीछे स्पष्टीकरण या विचार।
मैंने इसे रिकर्सन और गतिशील प्रोग्रामिंग दोनों के साथ हल करने का प्रयास किया। उम्मीद है की यह मदद करेगा।
सूत्र पिछले जवाब में पहले से ही मौजूद है:
तो अगर आप समाधान सीखने और apporach को समझने में रुचि रखते हैं तो आप हमेशा मेरे लेख की जांच कर सकते Count Binary Search Trees created from N unique elements
शायद [संबंधित] (http: // stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib)। –