http://geeksforgeeks.org/?p=6358 क्या कोई यह बता सकता है कि मॉरिस ट्रैवर्सल की समय जटिलता o(n) है? ट्रैवर्सल में, जब भी नोड में बाएं बच्चे होते हैं तो इसकी एक प्रति अपने पूर्ववर्ती के दाहिने बच्चे को बनाई जाती है। इतना बुरा मामला यह है कि पूर्ववर्ती प्रत्येक नोडमॉरिस ट्रैवर्सल ओ (एन) की जटिलता कैसी है?
while(pre->right != NULL && pre->right != current)
pre = pre->right;
जटिलता को बढ़ाने के लिए कौन सा है? क्या मुझे यहां कुछ याद आ रही है?
यह जटिलता में वृद्धि नहीं करेगा क्योंकि एल्गोरिदम केवल पेड़ को केवल एक दिशा में पुनर्निर्माण करता है (पुनर्निर्माण केवल ओ (एन) लेता है जिसके बाद केवल ओ (एन) उन्हें मुद्रित करने के लिए ... लेकिन वे विलय हो गए हैं दोनों कार्यक्षमताओं को एक ही समारोह में और अलगो के लिए एक विशेष नाम दिया गया है ...
यह देखने का एक और तरीका यह पता लगाने का एक और तरीका है कि पेड़ नोड कितनी बार घुमाया जाएगा। क्योंकि यह स्थिर है (3 । एक द्विआधारी पेड़ के लिए बार) हम हे (एन) को देख रहे हैं
मॉरिस ट्रेवर्सल के लिए मूल पत्र Traversing binary trees simply and cheaply है यह उस समय जटिलता हे (एन) परिचय अनुभाग में है का दावा है:।।
यह भी कुशल है, पेड़ में नोड्स की संख्या के आनुपातिक समय लेना और नोड्स में रन-टाइम स्टैक और न ही 'ध्वज' बिट्स की आवश्यकता होती है।
पूर्ण पेपर में समय जटिलता का विश्लेषण होना चाहिए। लेकिन पूर्ण पेपर को मुफ्त में एक्सेस नहीं किया जा सकता है।
Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） कुछ विश्लेषण करता है। वह प्रासंगिक भाग का अनुवाद है:
एन-नोड बाइनरी पेड़ में एन -1 किनार हैं। मॉरिस ट्रैवर्सल में, एक किनारे पर 2 बार देखा जाता है। एक नोड का पता लगाने के लिए एक यात्रा है। एक यात्रा कुछ नोड के पूर्ववर्ती की तलाश में है। निम्नलिखित बाइनरी पेड़ में, लाल धराशायी रेखा नोड का पता लगाने के लिए है। ब्लैक डैश लाइन पूर्ववर्ती नोड की तलाश में है।
बस महसूस किया कि एक द्विआधारी पेड़ में सभी नोड्स के लिए पूर्ववर्ती खोजने ओ (एन) की समय लगेगा ... –