सी ++ बी-पेड़ विलय

Question

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

मौजूदा पेड़ (टैग, मूल्य) जोड़े संकेत दिया:

  A,0 
,----------,-------------, 
B,1  B,2   B,3 
     ,-------------, 
    C,1   C,2 

नए पेड़ विलय करने के लिए:

   A,0 
       | 
       B,3 
      ,-----------, 
     C,1   C,2 

अंतिम मर्ज किए गए पेड़:

  A,0 
,----------,-----------------, 
B,1  B,2    B,3 
     ,-------------, ,-----------, 
    C,1   C,2 C,1   C,2 

प्रश्न: वहाँ एक सुंदर है इस बी-पेड़ के सी ++ समाधान एसडी कंटेनर का उपयोग कर विलय, या बूस्ट जैसे लाइब्रेरी के साथ संभव है? धन्यवाद।

Answer 1

आप कास्पर पीटर की tree.hh लाइब्रेरी का उपयोग कर सकते हैं, यह जीपीएलवी 2 और जीपीएलवी 3 है।

यह एन-आरी पेड़ के लिए कार्यान्वयन की तरह एक एसटीएल है।

documentation कहता है कि एक म्यूटेबल एल्गोरिदम है, जिसका नाम मर्ज है, जो दो पेड़ों को विलय कर सकता है। यह भी बताता है कि यह कैसे हासिल किया जाता है।