आलसी मिट्टी एक बाइनरी पेड़ या लिंक्ड सूची के लिए फायदेमंद/हानिकारक कैसे है?

Question

हाल ही में, एक डेटा संरचना वर्ग के लिए, मुझे सवाल पूछा गया था कि कैसे आलसी हटाना (यानी, एक विलोपन जो पहले आइटम को हटाए जाने के लिए आवश्यक वस्तुओं को चिह्नित करता है, और फिर कुछ समय बाद सभी चिह्नित वस्तुओं को हटा देता है) एक सरणी, लिंक्ड सूची, या बाइनरी पेड़ के लिए फायदेमंद/हानिकारक। यहाँ है कि मैं क्या के साथ आए हैं:

• यह सरणियों में मदद मिलेगी क्योंकि आप समय है कि सरणी हर बार एक सूचकांक एल्गोरिदम सरणी पार करने के लिए जरूरत है कि में हालांकि हटा दी जाती है शिफ्ट करने के लिए लिया जाता है की बचत होगी, वहाँ सकता है अक्षमता हो।
• यह लिंक सूचियों की सहायता नहीं करेगा क्योंकि किसी भी आइटम को किसी भी तरह से हटाने के लिए आपको O (n) को पार करने की आवश्यकता है।
• मुझे बाइनरी पेड़ के बारे में पूरी तरह से यकीन नहीं है, लेकिन यदि यह एक के लिंक किए गए सूची कार्यान्वयन थे तो मुझे लगता है कि यह लिंक की गई सूची की तरह है?

Answer 1

मुझे लगता है कि यह सब परिस्थितियों और आवश्यकताओं पर निर्भर करता है। इस विधि का उपयोग करते हुए एक सामान्य अर्थ में जहां उन्हें चिह्नित किया जाता है और फिर बाद में हटा दिया जाता है, उनके पास बहुत सारे समान पेशेवर और विपक्ष होते हैं।

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

इसी तरह के विपक्ष: -Waste हटाए गए आइटम के लिए अंतरिक्ष की, क्योंकि वे सिर्फ वहाँ -have बैठे हैं, दो बार अनुप्रस्थ के लिए एक आइटम को हटाने के लिए एक बार यह चिह्नित करने के लिए और एक बार फिर यह -कई विलोपन डेटा खोजें बनाने संरचना को प्रदूषित होगा के लिए आइटम चिह्नित नष्ट करने के लिए हटाए गए सामानों की खोज के बाद से अधिक समय लें।

Answer 2

शायद आपको लिंक की गई सूचियों के कार्यान्वयन पर थोड़ा गहराई से सोचने की आवश्यकता है। आप इंगित करते हैं कि आलसी हटाना किसी भी तरह से मदद नहीं करेगा क्योंकि खोज करने का समय हर समय हटाना निष्पादित करना आवश्यक है।

इस बारे में सोचें कि वास्तव में किसी लिंक किए गए सूची से किसी आइटम को हटाने के लिए क्या होता है। नोट: यह एक सिंगल लिंक्ड सूची (डबल लिंक्ड सूची नहीं) मानता है 1) आइटम को हटाने के लिए खोजें (क्योंकि यह एक सिंगल लिंक्ड सूची है, आपको हमेशा खोजना है, क्योंकि आपको PREV आइटम की आवश्यकता है) 2) रखें PREV और NEXT तत्वों के लिए पॉइंटर्स 3) NEXT तत्व को इंगित करने के लिए "PREV" तत्व को ठीक करें - इस प्रकार, एक डबल लिंक्ड सूची में वर्तमान तत्व 3.5) को अलग करना, आपको पीछे दिए गए शीर्ष तत्व का भी ध्यान रखना होगा PREV तत्व के लिए। 4) CURRENT तत्व

से संबंधित स्मृति को जारी करें अब आलसी हटाने की प्रक्रिया क्या है? --- बहुत कम 1) हटाने के लिए आइटम ढूंढें (आपको एक खोज करने की भी आवश्यकता नहीं हो सकती है, क्योंकि आपके पास पहले से ही उस ऑब्जेक्ट को पॉइंटर है जिसे आप हटा देना चाहते हैं?) 2) आइटम को हटाने के लिए चिह्नित करें।

*) "कचरा संग्रहण" धागा चलाने के लिए और वास्तव में जब सिस्टम है शेष चरणों को पूरा करने के लिए प्रतीक्षा करें "निष्क्रिय"

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

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

Answer 3

मुझे लगता है कि उत्तर विभिन्न कारणों से "यह निर्भर करता है" होगा, लेकिन मुझे लगता है कि आप सही रास्ते पर हैं।

1) मैं एरे के बारे में आपके उत्तर से सहमत हूं, यह मानते हुए कि आपकी सरणी में कोई छेद नहीं है। यदि आपको प्रत्येक डिलीट पर चारों ओर सरणी को स्थानांतरित करने की आवश्यकता नहीं है, तो अब प्रस्तावित चिह्न, बाद के दृष्टिकोण को हटाएगा, बिल्कुल मदद नहीं करेगा।किसी भी तरह से, आप एल्गोरिदम के लिए ओ (एन) बनाम (2 ओ (एन) = ओ (एन)) से निपट रहे हैं, जो बराबर हैं। इसके बारे में सोचने की असली बात यह है कि "एक बार बनाम सभी विलोपनों को पुन: व्यवस्थित करता है, प्रत्येक विलोपन को व्यक्तिगत रूप से आपको किसी भी समय बचाता है?" मान लीजिए एम हटाने की संख्या है, आपके सरणी में पहली बार हटाने के बाद प्रत्येक तत्व को पुन: व्यवस्थित किया जाता है, ओ (एम) को हटाने के लिए ओ (एम) के तुरंत बाद ओ (1) की तुलना में दृष्टिकोण के लिए, बाद के दृष्टिकोण को हटा दें।

2) मैं लिंक की गई सूचियों के आपके उत्तर से सहमत हूं।

3) बाइनरी ट्री के लिए, मुझे लगता है कि यह निर्भर करेगा कि यह किस प्रकार है। यदि आप एक क्रमबद्ध, संतुलित बाइनरी पेड़ का उपयोग कर रहे हैं, तो आपको ऊपर दिए गए प्रश्न 1) पर विचार करना होगा, लेकिन यदि नहीं, तो आपके विचार सही हैं, और इसे एक लिंक की गई सूची की तरह व्यवहार करना चाहिए।