बाइनरी पेड़ ट्रैवर्सल की जटिलताओं

Question

डेटा संरचनाओं में बाइनरी पेड़ों के इनऑर्डर, पोस्टऑर्डर और प्रीऑर्डर ट्रैवर्सल की समय जटिलता क्या है ?? क्या यह ओ (एन) या ओ (लॉग एन) या ओ (एन^2) है ??

Answer 1

O(n), क्योंकि आप एक बार प्रत्येक नोड को पार करते हैं। या इसके बजाय - प्रत्येक नोड के लिए आप जो काम करते हैं वह स्थिर है (शेष नोड्स पर निर्भर नहीं है)।

Answer 2

ट्रैवर्सल किसी भी ऑर्डर के लिए ओ (एन) है - क्योंकि आप एक बार प्रत्येक नोड को मार रहे हैं। लुकअप वह जगह है जहां यह ओ (एन) से कम हो सकता है अगर पेड़ में कुछ प्रकार का आयोजन स्कीमा (यानी बाइनरी सर्च ट्री) है।

Answer 3

ओ (एन), मैं कहूंगा। मैं एक संतुलित पेड़ के लिए कर रहा हूं, जो सभी पेड़ों के लिए लागू होता है। , यह मानते हुए कि आप प्रत्यावर्तन का उपयोग

टी (एन) = 2 * टी (एन/2) + 1 ----------> (1)

टी (एन/2) बाएं उप-पेड़ और टी (एन/2) के लिए दाएं उप-पेड़ के लिए और बेस केस की पुष्टि के लिए '1' के लिए।

सरलीकरण (1) पर आप साबित कर सकते हैं कि ट्रैवर्सल (या तो इनऑर्डर या प्रीऑर्डर या पोस्ट ऑर्डर) ऑर्डर (ओ) है।

Answer 4

इन-ऑर्डर, प्री-ऑर्डर और पोस्ट-ऑर्डर ट्रैवर्स गहराई-प्रथम ट्रैवर्सल हैं।

एक ग्राफ के लिए, गहराई की पहली जटिलता ओ (एन + एम) की जटिलता है, जहां एन नोड्स की संख्या है, और मीटर किनारों की संख्या है।

चूंकि बाइनरी ट्री भी एक ग्राफ है, वही यहां लागू होता है। इनमें से प्रत्येक गहराई-प्रथम ट्रैवर्सल की जटिलता ओ (एन + एम) है।

चूंकि नोड से उत्पन्न किनारों की संख्या बाइनरी ट्री के मामले में 2 तक सीमित है, बाइनरी ट्री में कुल किनारों की अधिकतम संख्या एन -1 है, जहां एन नोड्स की कुल संख्या है ।

जटिलता तब ओ (एन + एन -1) बन जाती है, जो ओ (एन) है।