क्या पेड़ घूर्णन का उपयोग करके एक बीएसटी को दूसरे में बदलना हमेशा संभव है?

Question

मूल्यों के एक सेट को देखते हुए, उन मूल्यों से कई अलग-अलग संभव बाइनरी खोज पेड़ बन सकते हैं।

1  1  2  3  3 
\  \ /\ / /
    2  3 1 3 1  2 
    \ /   \ /
    3 2    2 1 

कई डाटा संरचनाओं कि संतुलित द्विआधारी खोज पेड़ का उपयोग tree rotations के लिए एक आदिम रूप पर आधारित हैं: उदाहरण के लिए, मान 1, 2, और 3 के लिए, वहाँ पाँच BSTs हम उन मूल्यों से बना सकते हैं आवश्यक बाइनरी खोज वृक्ष invariants तोड़ने के बिना एक बीएसटी reshaping।

   rotate 
     u  right   v 
     /\  ----->  /\ 
     v C     A u 
    /\  <-----   /\ 
    A B  rotate   B C 
       left 

एक BST मानों का एक सेट से युक्त को देखते हुए, उसी के लिए किसी भी मनमाने ढंग से अन्य BST में है कि BST कन्वर्ट करने के लिए यह हमेशा संभव है: पेड़ रोटेशन, जैसा कि यहाँ दिखाया अपनी मूल ऊपर एक नोड ऊपर खींचने के लिए इस्तेमाल किया जा सकता मूल्यों का समूह? उदाहरण के लिए, क्या हम पेड़ घूर्णन का उपयोग कर किसी भी अन्य बीएसटी में से किसी भी पांच बीएसटी में से किसी के बीच परिवर्तित कर सकते हैं?

Answer 1

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

इसका कारण यह है कि बीएसटी में नोड्स का इनऑर्डर ट्रैवर्सल इस बात पर ध्यान दिए बिना कि कितने पेड़ रोटेशन किए जाते हैं। नतीजतन, एक बीएसटी से दूसरे में परिवर्तित करना संभव नहीं है यदि नोड्स के इनऑर्डर ट्रैवर्सल अलग-अलग आ जाएंगे। एक बहुत ही साधारण मामले के रूप में, मान लीजिए कि आपके पास बीएसटी नंबर 1 की दो प्रतियां हैं, जिनमें से प्रत्येक को एक अलग मूल्य (कहें, ए या बी) के साथ एनोटेट किया गया है।

 1:a   1:b 
     \    \ 
     1:b   1:a 

आप के द्वारा ही संभव पेड़ आप के साथ कर सकते हैं जानवर-मजबूर कर (! बहुत छोटा) सेट इस जाँच कर सकते हैं: उस मामले में, वहाँ कोई रास्ता नहीं है के बाद इन दोनों के पेड़ एक और का उपयोग कर पेड़ रोटेशन चालू करने के लिए है रोटेशन। हालांकि, यह ध्यान देने योग्य है कि पहले पेड़ का एक अवरोध ट्रैवर्सल 1: ए, 1: बी और दूसरे पेड़ के एक इनऑर्डर ट्रैवर्सल देता है 1: बी, 1: ए। नतीजतन, पेड़ों के बीच परिवर्तित करने के लिए कोई भी घूर्णन पर्याप्त नहीं होगा।

दूसरी ओर, यदि सभी मान अलग हैं, तो पेड़ घूर्णन की सही संख्या लागू करके दो बीएसटी के बीच परिवर्तित करना हमेशा संभव है। मैं इसे नोड्स की संख्या पर एक अपरिवर्तनीय तर्क का उपयोग करके साबित करूंगा।

एक साधारण आधार मामले के रूप में, यदि पेड़ में कोई नोड्स नहीं हैं, तो केवल एक संभावित बीएसटी उन नोड्स को पकड़ रहा है: खाली पेड़। इसलिए, उन दोनों में शून्य नोड्स के साथ दो पेड़ों के बीच परिवर्तित करना हमेशा संभव है, क्योंकि प्रारंभ और अंत पेड़ हमेशा एक जैसा होना चाहिए।

अपरिवर्तनीय चरण के लिए, आइए मान लें कि 0, 1, 2, .., एन नोड्स के समान दो मानों के साथ, घूर्णन का उपयोग करके एक बीएसटी से दूसरे में परिवर्तित करना हमेशा संभव है। हम साबित करेंगे कि एक ही एन + 1 मानों से बने किसी भी दो बीएसटी दिए गए हैं, पहले पेड़ को दूसरे में परिवर्तित करना हमेशा संभव है।

ऐसा करने के लिए, हम एक महत्वपूर्ण अवलोकन करके शुरू कर देंगे। बीएसटी में किसी भी नोड को देखते हुए, पेड़ की जड़ तक उस नोड को खींचने के लिए वृक्षारोपण लागू करना हमेशा संभव होता है। ऐसा करने के लिए, हम इस एल्गोरिथ्म लागू कर सकते हैं:

while (target node is not the root) { 
    if (node is a left child) { 
     apply a right rotation to the node and its parent; 
    } else { 
     apply a left rotation to the node and its parent; 
    } 
} 

कारण यह काम करता है कि यह है कि हर बार एक नोड अपने माता-पिता, एक के बाद उसकी ऊंचाई वृद्धि के साथ घुमाया जाता है। नतीजतन, उपरोक्त रूपों के पर्याप्त घूर्णन को लागू करने के बाद, हम पेड़ के शीर्ष तक रूट प्राप्त कर सकते हैं।

यह अब हमें एक बहुत ही सरल रिकर्सिव एल्गोरिदम देता है जिसे हम किसी भी बीएसटी को घूर्णन का उपयोग करके किसी अन्य बीएसटी में दोबारा बदलने के लिए उपयोग कर सकते हैं। विचार अग्रांकित है। सबसे पहले, दूसरे पेड़ के रूट नोड को देखो। पहले पेड़ में उस नोड को ढूंढें (यह बहुत आसान है, क्योंकि यह एक बीएसटी है!), फिर पेड़ की जड़ तक खींचने के लिए उपरोक्त एल्गोरिदम का उपयोग करें। इस बिंदु पर, हमने पहले पेड़ को निम्नलिखित गुणों के साथ एक पेड़ में बदल दिया है:

1. पहला पेड़ का रूट नोड दूसरे पेड़ का रूट नोड है।
2. पहले पेड़ के दाएं उपट्री में दूसरे पेड़ के दाएं उपट्री के समान नोड्स होते हैं, लेकिन संभवतः एक अलग आकार के साथ।
3. पहले पेड़ के बाएं उपट्री में दूसरे पेड़ के बाएं उपट्री के समान नोड्स होते हैं, लेकिन संभवतः एक अलग आकार के साथ।

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

1. दो पेड़ों खाली हैं, तो हम से किया जाता है:

   संक्षेप में, एल्गोरिथ्म इस प्रकार काम करता है।

2. पहले पेड़ में दूसरे पेड़ के रूट नोड को ढूंढें।
3. उस नोड को रूट पर लाने के लिए घूर्णन लागू करें।
4. दूसरे पेड़ के बाएं उपट्री के समान आकार के लिए पहले पेड़ के बाएं उपट्री को दोबारा दोहराएं।
5. दूसरे पेड़ के दाएं उपट्री के समान आकार के लिए पहले पेड़ के दाएं उपट्री को दोबारा दोहराएं।

इस एल्गोरिदम के रनटाइम का विश्लेषण करने के लिए, ध्यान दें कि चरण 1 - 3 को लागू करने के लिए अधिकांश ओ (एच) चरणों की आवश्यकता होती है, जहां एच पहले पेड़ की ऊंचाई है। प्रत्येक नोड को एक बार कुछ सबट्री की जड़ तक लाया जाएगा, इसलिए हम इसे कुल ओ (एन) बार करते हैं। चूंकि एन-नोड पेड़ की ऊंचाई ओ (एन) से अधिक नहीं होती है, इसका मतलब है कि एल्गोरिदम अधिकतर ओ (एन) पूरा करने के लिए समय लेता है। यह संभव है कि यह बहुत बेहतर होगा (उदाहरण के लिए, यदि दोनों पेड़ों में पहले से ही एक ही आकार है, तो यह समय ओ (एन) में चलता है, लेकिन यह एक अच्छा सबसे खराब मामला बाध्य करता है।

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

Answer 2

द्विआधारी खोज पेड़ों के लिए यह वास्तव में ओ (एन) में किया जा सकता है।

कोई भी पेड़ "सीधा हो सकता है", यानी एक रूप में डाला जा सकता है जिसमें सभी नोड्स रूट या बाएं बच्चे हैं।

• कोई अधिकार बच्चे के लिए, खुद के बारे में छोड़ दिया रोटेशन प्रदर्शन:

  यह फार्म है अद्वितीय

  एक पेड़ बाहर सीधा निम्नानुसार है (जड़ से नीचे पढ़ने तत्वों का आदेश देता है)।इससे तक सही बच्चों की संख्या कम हो जाती है, इसलिए पेड़ ओ (एन) घूर्णन में सीधे हो गया है।

एक में हे हे (एन) रोटेशन में (एन) घुमाना और एस में बी, तब से रोटेशन हैं प्रतिवर्ती एक चालू कर सकते हैं एस में बाहर सीधा किया जा सकता है एक -> एस -> बी ओ (एन) घूर्णन में बी।