सेट - एल्गोरिदम, पेड़, उपट्री से नोड्स युक्त न्यूनतम उपट्री

एक पेड़ की संरचना है, उदा।

   1
/ 
/   
2     3
|    / 
|   /   
4  5     6

और नोड्स (लीफ़्स) का सेट, जो सबट्री में होना चाहिए, उदा।

[5, 6]

न्यूनतम सबट्री कैसे प्राप्त करें जिसमें ये सभी नोड शामिल हैं और रूट तत्व से शुरू होता है? ऐशे ही:

   1


3
/ 
/   
5     6

उत्तर:

जवाब के लिए 2 № 1

मूल रूप से, आप पत्तियों को पुन: प्राप्त कर सकते हैं, और पा सकते हैं, प्रत्येक पत्ती के लिए, चाहे इसकी आवश्यकता हो या नहीं। जब पुनरावृत्ति फिर से ऊपर जाती है, तो आप देख सकते हैं कि क्या किसी वंशज की आवश्यकता थी।

यहाँ छद्म कोड है जो ऐसा करता है:

def mark_needed_nodes(node, given_nodes):
# If a leaf, check if it is in given_nodes
if node is leaf:
node.needed = node in given_nodes
return node.needed

# It is not a leaf; check if any of the descendants is needed.
node.needed = False
for child in node.children:
node.needed = needed or mark_needed_nodes(child, given_nodes)
return node.needed

आप फोन करेंगे mark_needed_nodes(root, given_nodes).

---

यह मानते हुए given_nodes एक हैश-आधारित शब्दकोश है, जटिलता पेड़ में नोड्स की संख्या में रैखिक है।

---

उत्तर № 2 के लिए 1

मुझे लगता है, पूरे वृक्ष को लांघने की कोई जरूरत नहीं है। हम दिए गए पत्ती नोड्स में से प्रत्येक से "लाइनों को खींच सकते हैं" जड़ तक।

कुछ इस तरह:

1. आवश्यकतानुसार रूट नोड चिह्नित करें।
2. पहले ली गई लीफ नोड को संसाधित न करें। यदि कोई नहीं हैं, तो हम कर रहे हैं।
3. वर्तमान नोड की जरूरत है।
4. वर्तमान नोड के जनक पर जाएं।
5. यदि वर्तमान नोड पहले से ही आवश्यक है, तो 2 पर जाएं, अन्यथा 3 पर जाएं।

---

जवाब के लिए 0 № 3

मान लें कि आपके क्वेरी सेट में k नोड्स हैं, और nपेड़ में नोड्स। यदि आपको एक ही पेड़ पर कई प्रश्न करने की आवश्यकता है, और पेड़ एक विशिष्ट क्वेरी सेट से बहुत बड़ा है, तो आप निम्नलिखित समाधान पर विचार कर सकते हैं।

एक जटिल ओ (एन) -प्रोसेसिंग-टाइम, ओ (के) -क्वेरी-टाइम समाधान

आप पहले कर सकते हैं अपने पेड़ को रैखिक समय में प्रीप्रोसेस करें ताकि आप निरंतर समय में एक जोड़ी नोड्स के सबसे कम सामान्य पूर्वज को निर्धारित कर सकें। फिर, दिए गए क्वेरी के लिए, आप तब पा सकते हैंदो क्वेरी नोड्स के सबसे कम सामान्य पूर्वज, फिर उस नोड के सबसे कम सामान्य पूर्वज और आपकी क्वेरी में तीसरे नोड, आदि, कुल मिलाकर O (k) समय में आपके क्वेरी में सेट सभी नोड्स के निम्नतम सामान्य पूर्वज निर्धारित करने के लिए। हालाँकि प्रीप्रोसेसिंग और क्वेरी करना दोनों ही जटिल हैं, और यह तब तक सबसे तेज़ तरीका होने की संभावना नहीं है जब तक कि आपका पेड़ आपके क्वेरी आकार की तुलना में विशाल न हो और आपके पास एक ही ट्री पर कई अलग-अलग क्वेरीज़ हों (ताकि समय पूर्व-भुगतान बंद हो जाए)।

---