किसी दिए गए सरणी के कितने क्रमिक परिणाम बीएसटी की ऊंचाई 2 में होते हैं?

Question

सेट से 1,2,3,4,5,6,7} सेट के प्रत्येक क्रमपरिवर्तन से एक बीएसटी उत्पन्न होता है (नोड्स के लगातार सम्मिलन से)। कितने क्रमिक ऊंचाई ऊंचाई के पेड़ निर्धारित करते हैं?

मैं कुछ समय के लिए इस सरल प्रश्न पर फंस गया हूं। कोई भी संकेत देता है।

वैसे जवाब 80

Answer 1

विचार करें कि वृक्ष की ऊंचाई 2 होगा?

-यह कैसे आ 4 जड़ है बाईं बच्चे, 6 सही बच्चे, आदि

के रूप में रूट के रूप में 4, 2 की जरूरत है?

-इसे पहले डालने की आवश्यकता है। तो अब हमारे पास एक नंबर है, 6 अभी भी क्रमपरिवर्तन में चारों ओर स्थानांतरित कर सकते हैं।

और?

- पहले डालने के बाद अभी भी 6 स्थान शेष हैं, बाईं ओर 3 और दाएं उपट्री के लिए 3 हैं। यह 6 = 3 विकल्प चुनते हैं।

अब क्या?

- बाएं और दाएं उपट्री के लिए, उनकी जड़ों को पहले डालने की आवश्यकता है, तो बच्चों का आदेश पेड़ को प्रभावित नहीं करता है - 2, 1, 3 और 2, 3, 1 एक ही पेड़ देता है। यह प्रत्येक subtree के लिए 2 है, और बाएं और दाएं subtrees के लिए 2 * 2 = 4।

तो?

अंत में: सी (6, 3) * 2 * 2 = 20 * 2 * 2 = 80.

Answer 2

नोट वहाँ केवल एक ही संभव इस पेड़ के लिए आकार है कि - यह अच्छी तरह से संतुलित हो गया है । इसलिए यह पेड़ होना चाहिए:

  4 
    / \ 
     2  6 
    /\ /\ 
    1 3 5 7 

इसके लिए पहले 4 को सम्मिलित करने की आवश्यकता है। इसके बाद, सम्मिलन को उचित क्रम में 1, 2, 3 और 5, 6, 7 वाले उपट्री बनाने की आवश्यकता होती है। इसका मतलब है कि हमें 1 और 3 से पहले 2 डालने की आवश्यकता होगी और 5 और 7 से पहले 6 डालने की आवश्यकता होगी। इससे कोई फर्क नहीं पड़ता कि हम किस सापेक्ष क्रम में 1 और 3 डालते हैं, जब तक कि वे 2 के बाद होते हैं, और इसी तरह इससे कोई फर्क नहीं पड़ता कि हम 5 साल के बाद तक 5 और 7 डालते हैं। आप इसलिए सोच सकते हैं कि हमें 2 एक्सएक्स और 6 वाई वाई के रूप में डालने की क्या ज़रूरत है, जहां एक्स 2 के बच्चे हैं और वाई 6 के बच्चे हैं। फिर हम उपरोक्त पेड़ को 2 एक्सएक्स और 6 वाई वाई के सभी इंटरलीवों को ढूंढकर उपरोक्त पेड़ को वापस पाने के सभी संभावित तरीकों को ढूंढ सकते हैं, फिर चार से गुणा करके (एक्स और वाई को मानने के तरीकों की संख्या 1 , 3, 5, और 7)।

तो इंटरलीव करने के लिए कितने तरीके हैं? खैर, आप इसे एल एल एल आर आर आर अनुक्रमित करने के तरीकों की संख्या के रूप में सोच सकते हैं, क्योंकि एल एल एल आर आर आर के प्रत्येक क्रमपरिवर्तन हमें बताता है कि वाम अनुक्रम या दायां अनुक्रम से कैसे चुनें। 6 हैं!/3! 3! = ऐसा करने के 20 तरीके। चूंकि उन बीस इंटरलीव्स में से प्रत्येक चार संभव सम्मिलन अनुक्रम देता है, कुल 20 × 4 = ऐसा करने के संभावित तरीके हैं।

आशा है कि इससे मदद मिलती है!

Answer 3

मैंने 12 से ऊंचाइयों के साथ 1 - 12 तत्वों के साथ क्रमपरिवर्तन की संख्या के लिए एक तालिका बनाई है, और किसी भी व्यक्ति को मैन्युअल प्रक्रिया की जांच करने का प्रयास करने के लिए प्रति रूट ब्रेक डाउन शामिल है (अन्य उत्तरों में वर्णित) वास्तविक मूल्यों से मेल खाता है।

http://www.asmatteringofit.com/blog/2014/6/14/permutations-of-a-binary-search-tree-of-height-x