परफेक्ट बैलेंस्ड बाइनरी सर्च ट्री

Question

मेरे पास Balanced BST के बारे में सैद्धांतिक प्रश्न है।

मैं Perfect Balanced Tree बनाना चाहता हूं जिसमें नियमित unbalanced BST से 2^k - 1 नोड्स हैं। सबसे आसान समाधान मैं सोच सकता हूं कि एक क्रमबद्ध Array/Linked list का उपयोग करना और सरणी को उप-सरणी में विभाजित करना है, और इससे Perfect Balanced BST बनाएं।

हालांकि, बहुत बड़े वृक्ष आकार के मामले में, मुझे एक ही आकार में Array/List बनाने की आवश्यकता होगी ताकि यह विधि बड़ी मात्रा में स्मृति का उपभोग करे।

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

मेरे सवाल कर रहे हैं मैं सही मेरी मान्यताओं के बारे में हूँ,? असंतुलित BST से एक परिपूर्ण BST बनाने का कोई अन्य तरीका है?

Answer 1

मैं अभी तक एक अच्छी तरह से संतुलित खोज पेड़ की आवश्यकता होगी, के लिए एक बहुत अच्छा स्थिति नहीं मिला। अगर आपके मामले को वास्तव में इसकी ज़रूरत है, तो मैं इसके बारे में सुनना चाहूंगा। आमतौर पर यह लगभग संतुलित पेड़ रखने के लिए बेहतर और तेज़ है।

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

एक AVL पेड़, एक लाल काले पेड़ या एक टेढ़ा-वृक्ष है, जो पेड़ संतुलित रखने के लिए रोटेशन की थोड़ा अलग वेरिएंट का उपयोग उदाहरण के लिए नहीं है।

यदि आपके पास वास्तव में एक असंतुलित पेड़ है तो आपको एक अलग समस्या हो सकती है। - आपके मामले में घूर्णन करने से एवीएल रास्ता शायद इसे ठीक करने का सबसे अच्छा तरीका है।

Answer 2

एवीएल और इसी तरह के पेड़ पूरी तरह से संतुलित नहीं हैं इसलिए मुझे यकीन नहीं है कि वे इस संदर्भ में कैसे उपयोगी हैं।

आप पेड़ नोड्स, forward और backward संकेत के एवज में left और right संकेत का उपयोग कर के बाहर एक दोगुना से जुड़े सूची का निर्माण कर सकते हैं। उस सूची को क्रमबद्ध करें, और नीचे से ऊपर पेड़ का निर्माण करें, सूची को बाएं से दाएं से उपभोग करें।

आकार 1 के एक पेड़ का निर्माण तुच्छ है: बस सूची से वाम-पंथी नोड काट।

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

यह 2^k-1 भी अन्य की तुलना में आकार के लिए संशोधित करने के लिए आसान है।

अद्यतन: यदि आप एक खोज के पेड़ से शुरू कर रहे हैं के बाद से, आप एक हल कर सूची इससे सीधे O(N) समय और O(log N) अंतरिक्ष (शायद एक छोटे से सरलता के साथ में भी O(1) अंतरिक्ष) में निर्माण कर सकते हैं, और यह भी पेड़ नीचे-ऊपर का निर्माण O(N) समय और O(log N) (या O(1)) स्थान में।

Answer 3

यदि आप स्मृति को बाधित कर रहे हैं, तो आप स्प्लिट का उपयोग कर सकते हैं और संचालन में शामिल हो सकते हैं जो ओ (लॉग एन) समय में एवीएल पेड़ पर किया जा सकता है, और मुझे निरंतर स्थान पर विश्वास है।

यदि आप ऑर्डर आंकड़े बनाए रखने में भी सक्षम थे, तो आप मध्यस्थ पर विभाजित हो सकते हैं, एलएचएस और आरएचएस को सही बना सकते हैं और फिर शामिल हो सकते हैं।

छद्म कोड (एक पुनरावर्ती संस्करण के लिए) हो जाएगा

यह हे (एन) समय और हे (लॉग एन) अंतरिक्ष में लागू किया जा सकता, मेरा मानना ​​है।