arrays - deletion - what is tree in data structure in hindi




बाइनरी ट्री के लिए कुशल ऐरे संग्रहण (3)

आप फ़ाइल में बाइनरी पेड़ के in-order और pre/post-order ट्रैवर्सल को सहेज सकते हैं और इन ट्रैवर्सल से पेड़ का पुनर्निर्माण कर सकते हैं।

हमें एक फाइल में एक बाइनरी पेड़ के नोड्स लिखना है। बाइनरी पेड़ लिखने का सबसे अधिक सुविधाजनक तरीका क्या है। हम इसे i , 2i+1 में माता-पिता के साथ सरणी प्रारूप में स्टोर कर सकते हैं। लेकिन यह दुर्लभ बाइनरी पेड़ों के मामले में बहुत सी जगह बर्बाद कर देगा।


एक विधि जो मुझे पसंद है वह प्रीऑर्डर ट्रैवर्सल को स्टोर करना है, लेकिन वहां 'नल' नोड्स भी शामिल है। 'नल' नोड्स को संग्रहीत करना पेड़ के अंदरूनी हिस्से को भी स्टोर करने की आवश्यकता को हटा देता है।

इस विधि के कुछ फायदे

  • आप अधिकांश व्यावहारिक मामलों में प्री / पोस्ट + इनऑर्डर विधि से बेहतर संग्रहण कर सकते हैं।
  • सीरियलाइजेशन सिर्फ एक ट्रैवर्सल लेता है
  • Deserialization एक पास में किया जा सकता है।
  • इनऑर्डर ट्रैवर्सल पेड़ के निर्माण के बिना एक पास में प्राप्त किया जा सकता है, जो स्थिति के लिए कॉल करने पर उपयोगी हो सकती है।

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

तो अगर एन नोड्स हैं, तो स्पेस उपयोग 8 एन बाइट्स + एन -1 सूचक संकेतक + एन + 1 बिट्स नल नोड्स = 66 * एन बिट्स के लिए होगा।

प्री / पोस्ट + इनऑर्डर में आप 16 एन बाइट्स = 128 * एन बिट्स का उपयोग कर समाप्त कर देंगे।

तो आप इस पूर्व / पोस्ट + इनऑर्डर विधि पर 62 * एन बिट्स की एक जगह सहेजते हैं।

पेड़ पर विचार करें

       100
      /   \
     /     \
    /       \
   10       200
  / \       /  \
 .   .     150  300
          / \    / \
         .   .   .  .

जहां '।' नल नोड्स हैं।

आप इसे 100 10 . . 200 150 . . 300 . . रूप में क्रमबद्ध करेंगे 100 10 . . 200 150 . . 300 . . 100 10 . . 200 150 . . 300 . .

अब प्रत्येक (subtrees सहित) 'preorder traversal null' के साथ संपत्ति है जो नल नोड्स की संख्या = नोड्स + 1 की संख्या है।

यह आपको पेड़ बनाने की अनुमति देता है, धारावाहिक संस्करण को एक पास में दिया जाता है, क्योंकि पहला नोड पेड़ की जड़ है। अनुसरण करने वाले नोड्स बाएं उपट्री के बाद दाएं हैं, जिन्हें इस तरह देखा जा सकता है:

100 (10 . .) (200 (150 . .) (300 . .))

इनऑर्डर ट्रैवर्सल बनाने के लिए, जब आप नल देखते हैं तो आप एक नोड और पॉप (सूची में) देखते समय स्टैक और पुश का उपयोग करते हैं। परिणामी सूची इनऑर्डर ट्रैवर्सल है (इसके लिए एक विस्तृत स्पष्टीकरण यहां पाया जा सकता है: सी ++ / सी / जावा: एनाग्राम - मूल स्ट्रिंग से लक्ष्य तक; )।


यदि आपके पास (लगभग) पूरा पेड़ है तो 2i, 2i + 1 (बाइनरी हीप) विधि वास्तव में सबसे अच्छा तरीका है।

अन्यथा आप प्रत्येक नोड के साथ एक अभिभावक (मूल सूचकांक) को संग्रहित नहीं करेंगे।





binary-tree