अतिरिक्त स्मृति

Question

एक पूर्णांक के साथ एक द्विआधारी पेड़ को देखते हुए बिना हे (एन) समय में एक द्विआधारी पेड़ पार करने के लिए कैसे, वाम & सही संकेत, कैसे एक पेड़ हे में पार कर सकते हैं (एन) समय और हे (1) अतिरिक्त स्मृति (कोई ढेर/कतार/रिकर्सन)?

This guy ने एक समाधान दिया जो ओ (एन) कुल समय नहीं है जो वर्तमान पथ को एक पूर्णांक के रूप में एन्कोड किया गया है (और इस प्रकार सीमित गहराई के पेड़ों के लिए काम करता है)।

मैं शास्त्रीय समाधान

(spoiler)

है कि बच्चों में प्रत्येक नोड के माता-पिता इनकोडिंग के लिए देख रहा हूँ।

Answer 1

किसी भी अच्छा एल्गोरिथ्म किताब इस एल्गोरिथ्म होगा, उदा देखो Knuth में (TAOCP I.2.3.1 बाइनरी पेड़ ट्रैवर्सिंग, व्यायाम 21)। हालांकि, क्योंकि यह एल्गोरिदम पेड़ को जगह में संशोधित करता है, इसलिए आपको बहु-थ्रेडेड वातावरण में चरम सावधानी बरतनी चाहिए।

आपको थ्रेडेड पेड़ का उपयोग कर सकते (नुथ में देखें)।

Answer 2

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

इस देखने के लिए, पूछते हैं कि अधिक से अधिक 2^32-1 नोड्स के साथ एक पेड़ भंडारण की एक एकल पूर्णांक (32-बिट प्लेटफॉर्म पर) का उपयोग कर चल जा सकता है।

Answer 3

उपयोग हे (1) भंडारण एक "अंतिम नोड का दौरा किया" सूचक को याद है। आप इसे 0 या कुछ अज्ञात मान में प्रारंभ कर सकते हैं।

पेड़ पर चलने के लिए, रूट नोड पर शुरू करें। दोनों नोड के बच्चों को देखो। यदि आपका "अंतिम बार देखा गया नोड" दाएं नोड के बराबर है, तो पैरेंट नोड पर जाएं। यदि "अंतिम बार देखा गया" बाएं नोड के बराबर है, तो दाएं नोड पर जाएं। बाएं नोड के लिए अन्य कदम।

होने तक दोहराएं पूरे वृक्ष चलने पूरा कर लें। एकमात्र असली चतुरता एक वैरिएबल का उपयोग कर याद रखती है कि आप कहां से आ रहे हैं यह तय करने के लिए कि आप कहां जा सकते हैं। यह ट्रैवर्सल निर्धारिती बनाता है।

आप ओ (एन) चरणों को ले लेंगे। आप तीन बार प्रत्येक मध्य नोड और प्रत्येक पत्ते को एक बार देखेंगे, इसलिए आप अभी भी ओ (एन) हैं। भंडारण ओ (1) है।

Answer 4

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

विचार है कि आप रास्ते पर संकेत फ्लिप कर सकते हैं नीचे पेड़ ऊपर की ओर इंगित करने के लिए है। समस्या यह है कि - और यह वह जगह है जहां आप सूची उलटा एल्गोरिदम से बदलते हैं - जब आप बैकट्रैक आपको पता होना चाहिए कि बाएं पॉइंट अप या दाएं बिंदुएं हैं या नहीं; जिस बिंदु पर हम हैक का उपयोग करते हैं।

छद्म कोड इस प्रकार है:

current = root->left 
next = current 
while (current != null) { 
    next = current->left 
    current->left = static_cast<int>(prev) + 1 // ugly hack. 
    current = next 
} 
status = done 
while (current != root or status != done) { 
    if (status = done) { 
    if (static_cast<u32>(current->left) %4 = 1) { 
     next = static_cast<u32>(current->left) -1 
     current->left = prev 
     status = middle 
    } 
    else { 
     next = current->right 
     current->right = prev 
     status = done 
    } 
    prev = current 
    current = next 
    } 
    else if (status == left) { 
    if (current->left) { 
     prev = current->left 
     current->left = static_cast<u32>(next) +1 
     next = current 
    } 
    else 
     status = middle 
    } 
    else if (status == right) { 
    if (current->right) { 
     prev = current->right; 
     current ->right = next; 
     next = current 
    } 
    else 
     status = done 
    } 
    else {// status == middle 
    work_on_node(current) 
    status = right 
    } 
} 

Answer 5

यहाँ एक और समाधान

http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

है लेकिन अगर, जिसमें संकेत है नहीं जावा जैसी भाषाओं में यह करने के लिए एक रास्ता है मैं सोच रहा था सच्ची भावना