ओ (1) सहायक भंडारण स्थान का उपयोग कर एक बाइनरी पेड़ में सभी नोड्स को हटा रहा है?

Question

एक binary tree में सभी नोड्स को हटाने के लिए मानक एल्गोरिथ्म एक postorder traversal इन पंक्तियों के साथ नोड पर उपयोग करता है:

if (root is not null) { 
    recursively delete left subtree 
    recursively delete right subtree 
    delete root 
} 

इस एल्गोरिथ्म हे (ज) सहायक भंडारण स्थान है, जहां ज पेड़ की ऊंचाई है का उपयोग करता है , रिकर्सिव कॉल के दौरान स्टैक फ्रेम को स्टोर करने के लिए आवश्यक स्थान की वजह से। हालांकि, यह समय ओ (एन) में चलता है, क्योंकि प्रत्येक नोड बिल्कुल एक बार दौरा किया जाता है।

क्या रनटाइम बलि किए बिना केवल ओ (1) सहायक स्टोरेज स्पेस का उपयोग करके बाइनरी पेड़ में सभी नोड्स को हटाने के लिए कोई एल्गोरिदम है?

Answer 1

यह वास्तव में tree rotations पर आधारित एल्गोरिद्म का उपयोग करके हे (एन) और हे (1) सहायक संग्रहण स्थान का उपयोग एक द्विआधारी पेड़ में सभी नोड्स को हटाने के लिए संभव है।

निम्नलिखित आकार के साथ एक द्विआधारी पेड़ को देखते हुए:

  u 
     /\ 
     v C 
     /\ 
     A B 

इस पेड़ का एक सही रोटेशन नोड ऊपर नोड वी खींचती यू और निम्नलिखित पेड़ में परिणाम:

 v 
    /\ 
     A u 
     /\ 
     B C 

ध्यान दें कि ओ पेड़ की जड़ को बदलकर ओ (1) समय और स्थान में एक वृक्ष रोटेशन किया जा सकता है, जिससे आप अपने बाएं बच्चे को वी के पूर्व दाहिने बच्चे के रूप में स्थापित कर सकते हैं, फिर वी के सही बच्चे को स्थापित कर सकते हैं।

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

 v 
     \ 
     A 

फिर हम यह एक बहुत ही सरल की ओर जाता है, नोड वी को हटाने तो इसकी सबट्री ए में सभी नोड्स हटा कर पेड़ में सभी नोड्स हटा सकते हैं पेड़ में सभी नोड्स को हटाने के लिए एल्गोरिथ्म:

while (root is not null) { 
    if (root has a left child) { 
     perform a right rotation 
    } else { 
     delete the root, and make the root's right child the new root. 
    } 
} 

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

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

यदि यह मदद करता है, तो मेरे पास a C++ implementation of this algorithm है, साथ ही एल्गोरिदम के व्यवहार के अधिक गहन विश्लेषण के साथ।इसमें एल्गोरिदम के सभी चरणों के लिए शुद्धता के औपचारिक प्रमाण भी शामिल हैं।

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

Answer 2

मुझे एक गंभीर मजाक से शुरू करने दें: यदि आप बीएसटी की जड़ को शून्य पर सेट करते हैं, तो आप पेड़ में सभी नोड्स को प्रभावी ढंग से हटा देते हैं (कचरा कलेक्टर अंतरिक्ष को उपलब्ध कराएगा)। जबकि शब्द जावा विशिष्ट है, विचार अन्य प्रोग्रामिंग भाषाओं के लिए है। यदि आप नौकरी साक्षात्कार में थे या परीक्षा ले रहे थे तो मैं इसका जिक्र करता हूं।

अन्यथा, तुम सब करने की है DSW algorithm का एक संशोधित संस्करण का उपयोग कर रहा है। मूल रूप से एक रीढ़ में पेड़ की बारी है और फिर आप एक linked list होगा के रूप में हटा दें। अंतरिक्ष ओ (1) और समय ओ (एन)। आपको किसी भी पाठ्यपुस्तक या ऑनलाइन में डीएसडब्ल्यू की वार्ता मिलनी चाहिए।

असल में डीएसडब्ल्यू एक BST संतुलित करने के लिए प्रयोग किया जाता है। लेकिन आपके मामले के लिए, एक बार जब आप बैकबोन प्राप्त कर लेते हैं, तो संतुलन के बजाय, आप एक लिंक की गई सूची की तरह हटा देते हैं।