बीएसटी

Question

से संख्याओं के क्रमबद्ध क्रम को हटाएं मेरे पास एक परीक्षा के दौरान यह प्रश्न था, और मुझे त्वरित उत्तर नहीं मिला।

एक सरणी ए है जिसमें कुछ आदेशित संख्या ए = [1,3,6,9,11] और बीएसटी कुंजी के रूप में संख्याएं हैं। मुझे बीएसटी से ए में संख्याओं को हटाने के लिए एक कुशल रिकर्सिव एल्गोरिदम प्रदान करना होगा।

मेरे पास समस्या नोड्स को हटाने में नहीं है, लेकिन इस तथ्य का उपयोग कैसे करें कि सरणी को नोड्स को हटाने में आदेश दिया गया है।

क्या कोई मुझे कुछ संकेतों के साथ मदद कर सकता है?

Answer 1

यहां एक संभावित दृष्टिकोण है।

आप दोनों बीएसटी (standard recursive algorithm का उपयोग करके) और A (बाएं से दाएं) का उपयोग कर सकते हैं। प्रत्येक ट्रैवर्सल बढ़ते क्रम में तत्व पैदा करेगा। आप पेड़ से उन्हें हटाने के लिए मिलान करने वाले तत्वों की तलाश में हैं।

एक बेवकूफ एल्गोरिदम में O(size(BST)) समय जटिलता होगी।

कुछ मामलों में आप बाएं सबट्री को पूरी तरह से देखने से बच सकते हैं: पेड़ में "वर्तमान" नोड का मान आपको बाएं उपट्री में मानों पर ऊपरी बाउंड देता है, इसलिए यदि यह मान के मूल्य से छोटा है A का "वर्तमान" तत्व, बाएं उपट्री को छोड़ दें।

जैसे ही आप A समाप्त कर चुके हैं, आप एल्गोरिदम को भी रोक सकते हैं।

Answer 2

एक बीएसटी को इसके रूट नोड द्वारा दर्शाया जाना चाहिए।

तर्क array और bst साथ समारोह delete-array-from-bst है:

• अगर array या bst खाली है: वापसी
• तीन subarrays में सरणी विभाजित, मूल्यों छोटे, बराबर, और से भी बड़ा bst की रूट नोड मान
• बाएं उप-बीएसटी के साथ छोटे मानों के साथ उपरायण पर पुनर्संरचना, फिर दाएं उप-बीएसटी पर बड़े मानों के साथ उपरेय पर, आखिरकार बराबर मान हटाएं, अगर एप्ली केबल

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