एक पेड़ के बाएं बच्चे, दाएं-भाई का प्रतिनिधित्व क्या है? आप इसका इस्तेमाल क्यों करेंगे?

Question

कई डेटा संरचनाएं "left-child, right-sibling" प्रतिनिधित्व नामक प्रतिनिधित्व का उपयोग करके बाइनरी पेड़ के रूप में बहु-मार्ग पेड़ों को संग्रहीत करती हैं। इसका क्या मतलब है? आप इसका इस्तेमाल क्यों करेंगे?

Answer 1

बाएं बच्चे, राइट-भाई प्रतिनिधित्व (LCRS) (जिसमें प्रत्येक नोड बच्चों के किसी भी संख्या हो सकती है एक वृक्ष संरचना) एक multi-way tree एन्कोडिंग का एक तरीका में एक binary tree (एक वृक्ष संरचना का उपयोग कर रहा है जो प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं)।

प्रेरणा

कैसे इस प्रतिनिधित्व काम करता है के लिए प्रेरित करने के लिए, चलो इस एक यहाँ की तरह, एक सरल मल्टी-वे पेड़ पर विचार करके शुरू करते हैं: (! कम गुणवत्ता वाले ASCII कलाकृति के लिए क्षमा याचना)

    A 
       //|\ \ 
      // | \ \ 
       B C D E F 
       | /|\ /\ 
       G H I J K L 

इस पेड़ की संरचना में, हम पेड़ में किसी भी नोड से अपने किसी भी बच्चे को नीचे की ओर नेविगेट कर सकते हैं। उदाहरण के लिए, हम ए से बी, ए से सी, ए से डी आदि में माइग्रेट कर सकते हैं।

अगर हम इस तरह के पेड़ में नोड का प्रतिनिधित्व करना चाहते हैं, तो हम आम तौर पर कुछ प्रकार के नोड संरचना/नोड का उपयोग करेंगे इस एक यहाँ (C++ लिखित) की तरह वर्ग:

struct Node { 
    DataType value; 
    std::vector<Node*> children; 
}; 

LCRS प्रतिनिधित्व में, हम एक तरह से मल्टी-वे पेड़ प्रतिनिधित्व करते हैं जहां प्रत्येक नोड सबसे दो संकेत पर की आवश्यकता है। ऐसा करने के लिए, हम पेड़ को थोड़ा दोहराएंगे। अपने सभी बच्चों के लिए पेड़ की दुकान पॉइंटर्स में प्रत्येक नोड रखने के बजाय, हम प्रत्येक नोड को अपने बच्चों में से एक (एलसीआरएस, बाएं बच्चे में) के लिए एक सूचक को स्टोर करके थोड़ा अलग तरीके से पेड़ की संरचना करेंगे। इसके बाद हम प्रत्येक नोड को अपने दाहिनी भाई के लिए एक पॉइंटर स्टोर करेंगे, पेड़ में अगला नोड जो एक ही पैरेंट नोड का बच्चा होगा। ऊपर पेड़ के मामले में, हम निम्नलिखित तरीके से पेड़ का प्रतिनिधित्व कर सकते:

  A 
     /
     /
     /
     B -> C -> D -> E -> F 
    /  /  /
     G   H->I->J K->L 

सूचना है कि यह अभी भी संभव है इस नए ढांचे में एक माता पिता के नोड से अपने kth बच्चे को नेविगेट करने के लिए (शून्य अनुक्रमित) । ऐसा करने की प्रक्रिया निम्न है:

• वर्तमान नोड के बाएं बच्चे में उतरें। (यह अपने बच्चों की सूची में पहला नोड है)।
• उस बच्चे के सही भाई पॉइंटर के समय का पालन करें। (यह आपको नोड के केथ बच्चे को ले जाता है)।
• उस नोड को वापस करें।

उदाहरण के लिए, रूट नोड ए के तीसरे (शून्य-अनुक्रमित बच्चे) को खोजने के लिए, हम बाएं बच्चे (बी) में उतरेंगे, फिर तीन दाएं लिंक का पालन करें (बी, सी, डी, और जा रहे हैं) अंत में ई)। फिर हम ई के लिए नोड पर पहुंचते हैं, जिसमें नोड ए

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

struct Node { 
    DataType data; 
    Node* leftChild; 
    Node* rightSibling; 
}; 

इस नोड संरचना एक द्विआधारी पेड़ (डेटा और दो संकेत) में एक नोड के बिल्कुल वैसा ही आकार है। नतीजतन, एलसीआरएस प्रतिनिधित्व से नोड के केवल दो पॉइंटर्स का उपयोग करके मनमानी मल्टीवे पेड़ का प्रतिनिधित्व करना संभव हो जाता है।

विश्लेषण

हमें अब बहुमार्गीय पेड़ के दो विभिन्न अभ्यावेदन और उस पर कुछ बुनियादी आपरेशन के समय और स्थान जटिलता को देखते हैं।

प्रारंभिक "बच्चों की गतिशील सरणी" प्रतिनिधित्व के लिए आवश्यक कुल स्थान उपयोग को देखकर शुरू करें। एन-नोड पेड़ के लिए कुल मेमोरी उपयोग कितना होगा? ठीक है, हम निम्नलिखित पता:

1. प्रत्येक नोड, बच्चों की संख्या की परवाह किए बिना, (sizeof (डेटा)) संग्रहीत कच्चे डेटा और गतिशील सरणी के अंतरिक्ष भूमि के ऊपर के लिए अंतरिक्ष योगदान देता है। गतिशील सरणी (आमतौर पर) में एक पॉइंटर संग्रहीत होता है (जो आवंटित सरणी पर इंगित करता है), गतिशील सरणी में तत्वों की कुल संख्या के लिए एक मशीन शब्द, और (वैकल्पिक रूप से) सरणी की आवंटित क्षमता के लिए एक मशीन शब्द होता है। इसका मतलब है कि प्रत्येक नोड आकार (डेटा) + आकार (नोड *) + 2 * आकार (मशीन शब्द) स्थान लेता है।

2. पेड़ में सभी गतिशील सरणीओं में, बच्चों के लिए एन -1 पॉइंटर्स होंगे, क्योंकि उनमें से नोड्स में एन नोड्स माता-पिता हैं। यह एक अतिरिक्त (एन -1) * आकार (नोड *) कारक में जोड़ता है।

इसलिए कुल स्थान उपयोग

n & Middot है; (आकार (डेटा) + आकार (नोड *) + 2 * आकार (मशीन शब्द)) + (एन -1) * आकार (नोड *)

= एन * आकार (डेटा) + (2 एन -1) * आकार (नोड *) + 2 एन * आकार (मशीन शब्द)

अब, एलसीआरएस पेड़ के साथ इसके विपरीत है। एक LCRS पेड़ भंडार दो संकेत (2 * sizeof (नोड *)) और एक डेटा तत्व (sizeof (डाटा)) है, इसलिए इसकी कुल स्थान

n * sizeof है (डेटा) + 2n में प्रत्येक नोड * sizeof (नोड *)

और यहाँ हम जीत देखें: लगता है कि हम कर रहे हैं नहीं 2n * sizeof (मशीन शब्द) भंडारण आवंटित सरणी आकार का ट्रैक रखने के अतिरिक्त स्मृति। इसका मतलब है कि एलसीआरएस प्रतिनिधित्व नियमित मल्टीवे पेड़ की तुलना में काफी कम स्मृति का उपयोग करता है।

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

इसलिए हम डेटा संरचना भंडारण स्थान और पहुंच के समय के बीच time-space tradeoff की पेशकश के रूप में एलसीआरएस प्रतिनिधित्व के बारे में सोच सकते हैं। एलसीआरएस के प्रतिनिधित्व में मूल मल्टीवे पेड़ की तुलना में कम मेमोरी ओवरहेड है, जबकि मल्टीवे पेड़ अपने प्रत्येक बच्चों के निरंतर समय के लुकअप देता है। या

1. मेमोरी अत्यंत दुर्लभ है,
:

उपयोग मामले

समय अंतरिक्ष LCRS प्रतिनिधित्व में शामिल तालमेल की वजह से

, LCRS प्रतिनिधित्व आम तौर पर इस्तेमाल नहीं किया है जब तक कि दो मानदंडों में से एक पकड़

2. नोड के बच्चों की यादृच्छिक पहुंच की आवश्यकता नहीं है।

केस (1) उत्पन्न हो सकता है यदि आपको मुख्य स्मृति में एक बड़े पैमाने पर विशाल मल्टीवे पेड़ को स्टोर करने की आवश्यकता होती है। उदाहरण के लिए, यदि आपको phylogenetic tree स्टोर करने की आवश्यकता होती है जिसमें कई अलग-अलग प्रजातियां होती हैं जो लगातार अपडेट के अधीन होती हैं, तो एलसीआरएस का प्रतिनिधित्व उचित हो सकता है।

केस (2) विशेष डेटा संरचनाओं में उत्पन्न होता है जिसमें वृक्ष संरचना का उपयोग बहुत विशिष्ट तरीकों से किया जा रहा है। उदाहरण के लिए, कई प्रकार के heap data structures जो मल्टीवे पेड़ का उपयोग करते हैं, एलसीआरएस प्रतिनिधित्व का उपयोग करके अंतरिक्ष अनुकूलित किया जा सकता है। इसके लिए मुख्य कारण यह है कि ढेर डाटा संरचनाओं में, सबसे आम आपरेशन होने के लिए

1. एक पेड़ की जड़ निकालें जाते हैं और अपने बच्चों में से प्रत्येक की प्रक्रिया, या
2. एक पेड़ बनाकर दो पेड़ों साथ जुड़ें है दूसरे का एक बच्चा

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

ऑपरेशन (2) भी बहुत कुशलता से किया जा सकता है। ऊपर से याद रखें कि एक एलसीआरएस प्रतिनिधित्व में, एक पेड़ की जड़ में कभी सही बच्चा नहीं होता है। इसलिए, एलसीआरएस प्रतिनिधित्व में दो पेड़ों को एक साथ शामिल करना बहुत आसान है। इस तरह दो पेड़ों के साथ शुरुआत:

R1    R2 
/   /
(children 1) (children 2) 

हम इस तरह से एक साथ पेड़ फ्यूज कर सकते हैं:

   R1 
      /
      R2 
     /\ 
(children 2) (children 1) 

यह हे में किया जा सकता (1) समय है, और काफी सरल है। तथ्य यह है कि एलसीआरएस के प्रतिनिधित्व में इस संपत्ति का अर्थ है कि binomial heap या rank-pairing heap जैसे कई प्रकार की ढेर प्राथमिकता कतारों को आम तौर पर एलसीआरएस पेड़ के रूप में दर्शाया जाता है।

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