एक सॉर्ट किए गए पूर्णांक सरणी को देखते हुए, बाइनरी सर्च पेड़ कैसे बन सकते हैं?

Question

विचार करें कि मेरे पास एक सरणी [3,18,15,25,26] है, इससे कितने संभावित बाइनरी खोज पेड़ बन सकते हैं?

Answer 1

माइक्रोसिम द्वारा लिखे गए प्रश्न को देखने के बाद, मैं अभी भी इससे संतुष्ट नहीं था, इसलिए मैंने इसे स्वयं देखना शुरू कर दिया। यहां मैं क्या आया हूं ...

प्रत्येक पेड़ को मूल पेड़ नोड के साथ दो पेड़ के रूप में माना जा सकता है। यदि आप अलग-अलग दो बच्चों की शाखाओं के संभावित संयोजनों की संख्या को जानते हैं, तो रूट नोड वाले कुल संयोजन बच्चों के संयोजन का उत्पाद है।

हम पहले निम्न गिनती उदाहरणों को हल करके उच्च गिनती समाधान का निर्माण शुरू कर सकते हैं।

मैं C(n) का उपयोग एन नोड्स, कैटलन संख्या के कुल संभावित संयोजनों का प्रतिनिधित्व करने के लिए करूंगा।

उम्मीद है कि इन दो स्पष्ट कर रहे हैं:

C(0) = 1 
C(1) = 1 

सी (2) भी काफी स्पष्ट है, लेकिन यह बनाया जा सकता है, तो चलो कि करते हैं। रूट नोड चुनने के दो तरीके हैं। एक 1:0 और अन्य 0:1 के बच्चे की गणना (बाएं: दाएं) छोड़ देता है। तो, पहली संभावना C(1)*C(0) = 1*1 = 1 है। और दूसरा C(0)*C(1) = 1*1 = 1 है। उनको सारांशित करने से हमें

कुछ भी रोमांचक नहीं है। अब चलो 3 नोड्स करते हैं। रूट नोड और इसलिए, 3 बाल समूह चुनने के 3 तरीके हैं। आपके संभावित समूह 2:0, 1:1 और 0:2 हैं।

हमारे पूर्व परिभाषाओं के आधार पर, C(3) को C(2)*C(0) + C(1)*C(1) + C(0)*C(2) = 2*1 + 1*1 + 1*2 = 2+1+2 = 5 के रूप में लिखा जा सकता है।

C(3) = 5 

4 नोड्स 3:0, 2:1, 1:2 और 0:3 के बच्चे समूहों है। तो, C(4) को C(3)*C(0) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3) = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14 के रूप में लिखा जा सकता है।

C(4) = 14 

उम्मीद है कि दो चीजें स्पष्ट होने लग रही हैं। सबसे पहले, यह जल्द ही बोझिल बनने लगेगा। दूसरा, जो मैंने वर्णन किया है, काफी लंबे समय तक चलने वाली फैशन में, विकी पेज पर पुनरावृत्ति संबंध प्रतिनिधित्व है।

मुझे नहीं पता कि इससे मदद मिलती है, लेकिन इससे मुझे व्यायाम करने में मदद मिली, इसलिए मैंने सोचा कि मैं साझा करूंगा। जब मैंने शुरू किया, तो मैं पुनरावृत्ति संबंध को फिर से बनाने की कोशिश नहीं कर रहा था, इसलिए यह अच्छा था कि मेरे परिणाम मौजूदा तरीकों में से एक से मेल खाते थे।

Answer 2

एन कुंजी के साथ बनाया जा सकता बाइनरी खोज पेड़ की संभावित संख्या एनएच catalan number द्वारा दी गई है।

इसके अलावा इस प्रश्न देखें: The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?

Answer 3

सरणी के नोड्स में से कोई एक BST की जड़ हो सकता है, और प्रत्येक जड़ के लिए, विशिष्ट खोज पेड़ों की संख्या छोड़ दिया का संयोजन (उत्पाद) और सही उपन्यास। तो,

BSTCount(0) = 1 
BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(n-i) 

आप पहले कुछ n के लिए इस समारोह का मूल्यांकन कर सकते हैं और फिर एक बंद फार्म को खोजने के लिए On-Line Encyclopedia of Integer Sequences™ (OEIS) में अनुक्रम को देखने।