निर्धारित करें कि क्या दो बाइनरी पेड़ बराबर हैं

Question

संरचनात्मक और सामग्री में दो दिए गए द्विआधारी पेड़ बराबर होने के लिए कुशल एल्गोरिदम क्या होगा?

Answer 1

यह एक छोटी समस्या है, लेकिन मैं पहले समाधान अनुकूलित चाहते हैं इस प्रकार है ...

eq(t1, t2) = 
    t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right) 

कारण यह है कि मीटर है आइसमैच सामान्य होने की संभावना है, और आगे बढ़ने से पहले - तुलना करना (और तुलना करना बंद करना) बेहतर है। बेशक, मैं यहां एक शॉर्ट सर्किट & & ऑपरेटर मान रहा हूं।

मैं यह भी बताउंगा कि यह संरचनात्मक रूप से अलग-अलग पेड़ों को सही तरीके से संभालने और पुनरावर्तन समाप्त करने के साथ कुछ मुद्दों पर चमक रहा है। असल में, t1.left आदि के लिए कुछ शून्य जांच होने की आवश्यकता है। यदि एक पेड़ में शून्य है। बाएं लेकिन दूसरा नहीं है, तो आपको संरचनात्मक अंतर मिला है। यदि दोनों में शून्य है। बाएं, कोई फर्क नहीं पड़ता है, लेकिन आप एक पत्ते तक पहुंच गए हैं - आगे की देखभाल न करें। केवल अगर दोनों। बाएं मान गैर-शून्य हैं तो क्या आप उप-जांच की जांच करते हैं। ठीक है, ठीक है, ठीक है।

आप उदाहरण के लिए चेक शामिल कर सकते हैं (t1.left == t2.left), लेकिन यह केवल तभी समझ में आता है जब subtrees को दो पेड़ों के लिए शारीरिक रूप से साझा किया जा सकता है (समान डेटा संरचना नोड्स)। यह जांच रिकर्सिंग से बचने का एक और तरीका होगा जहां यह अनावश्यक है - यदि t1.left और t2.left एक ही भौतिक नोड हैं, तो आप पहले से ही जानते हैं कि उन सभी उप-समान समान हैं।

एसी कार्यान्वयन हो सकती है ...

bool tree_compare (const node* t1, const node* t2) 
{ 
    // Same node check - also handles both NULL case 
    if (t1 == t2) return true; 

    // Gone past leaf on one side check 
    if ((t1 == NULL) || (t2 == NULL)) return false; 

    // Do data checks and recursion of tree 
    return ((t1->data == t2->data) && tree_compare (t1->left, t2->left) 
           && tree_compare (t1->right, t2->right)); 
} 

संपादित एक टिप्पणी के जवाब में ...

का उपयोग कर एक पूर्ण पेड़ तुलना के लिए समय से चल रहा है यह सबसे बस हे के रूप में कहा गया है (एन) जहां एन एक पेड़ का आकार थोडा है। यदि आप अधिक जटिल बाध्यता स्वीकार करने के इच्छुक हैं तो आप ओ (न्यूनतम (एन 1, एन 2)) जैसे छोटे से प्राप्त कर सकते हैं जहां n1 और n2 पेड़ के आकार होते हैं।

स्पष्टीकरण मूल रूप से है कि पुनरावर्ती कॉल केवल बाईं पेड़ में प्रत्येक नोड के लिए (अधिकतम) किया जाता है एक बार, और केवल बनाया (अधिकतम) एक बार सही पेड़ में प्रत्येक नोड के लिए है। कार्य के रूप में (रिकर्सन को छोड़कर) केवल सबसे अधिक काम की मात्रा (कोई लूप नहीं है) पर निर्दिष्ट करता है, सभी रिकर्सिव कॉल सहित कार्य केवल छोटे पेड़ के आकार के आकार के बराबर हो सकता है।

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

बाघ बांधने का एक तरीका दोनों पेड़ों में नोड्स के पथों के सेट पर विचार करना है। प्रत्येक चरण या तो एक एल (बाएं उपट्री) या एक आर (दाएं उपट्री) है। तो रूट एक खाली पथ के साथ निर्दिष्ट है। रूट के बाएं बच्चे का सही बच्चा "एलआर" है। एक पेड़ में वैध पथ के सेट का प्रतिनिधित्व करने के लिए "पथ (टी)" (गणितीय रूप से - कार्यक्रम का हिस्सा नहीं) को परिभाषित करें - प्रत्येक नोड के लिए एक पथ।

तो हम हो सकता है ...

paths(t1) = { "", "L", "LR", "R", "RL" } 
paths(t2) = { "", "L", "LL", "R", "RR" } 

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

ऊपर वृक्ष संरचना के लिए

, हम निम्नलिखित पथ के लिए recursions कर ...

paths(t1) intersection paths(t2) = { "", "L", "R" } 

तो इस मामले में हमारे काम सबसे तीन बार में घिरा है में गैर पुनरावर्ती काम का अधिकतम मूल्य tree_compare समारोह।

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

Answer 2

आप जो संभवतः पूरा करने की कोशिश कर रहे हैं उसके लिए एक और सामान्य शब्द graph isomorphism है। उस पृष्ठ पर ऐसा करने के लिए कुछ एल्गोरिदम हैं।

Answer 3

Modulo ढेर अतिप्रवाह, जैसे

eq(t1, t2) = 
    eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right) 

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

Answer 4

मैं इसे निम्नानुसार लिखूंगा। निम्नलिखित कोड सबसे कार्यात्मक भाषा में काम करेंगे, और यहां तक ​​कि अजगर में अगर आपके डेटाटाइप्स hashable हैं (उदाहरण के लिए नहीं शब्दकोशों या सूचियों):

• संस्थानिक समानता (, संरचना में एक ही यानी Tree(1,Tree(2,3))==Tree(Tree(2,3),1)):

  tree1==tree2 मतलब है set(tree1.children)==set(tree2.children)

• आदेश दिया समानता:

  tree1==tree2 मतलब है tree1.children==tree2.children

क्योंकि समानता उनके लिए पहले से ही परिभाषित किया गया है तुम्हें पता है, आधार मामलों (पत्ते) को संभालने की जरूरत नहीं है (Tree.children बच्चों की एक आदेश दिया सूची है)।

Answer 5

हम दो ट्रैवर्सल (प्री ऑर्डर, पोस्ट ऑर्डर या इन-ऑर्डर) में से कोई भी कर सकते हैं और फिर दोनों पेड़ों के परिणामों की तुलना कर सकते हैं। यदि वे समान हैं, तो हम उनके समकक्षता के बारे में सुनिश्चित हो सकते हैं।

Answer 6

चूंकि यह एक सिद्ध तथ्य यह है कि है - यह रूप में लंबे समय के रूप में हमारे पास एक द्विआधारी पेड़ पुन: बनाने के लिए निम्न संभव है:

1. नोड्स एक इन-आदेश Traversal में सामना होता है के अनुक्रम।
2. नोड्स के अनुक्रम है कि एक प्री-ऑर्डर या बाद आदेश Traversal

दो द्विआधारी पेड़ में आदेश में एक ही और है, तो [प्री-ऑर्डर या बाद आदेश] अनुक्रम में सामना होता है, तो वे संरचनात्मक रूप से और मूल्यों के संदर्भ में दोनों बराबर होना चाहिए।

प्रत्येक ट्रैवर्सल ओ (एन) ऑपरेशन है। ट्रैवर्सल कुल में 4 गुना किया जाता है और उसी प्रकार के ट्रैवर्सल के परिणामों की तुलना की जाती है। O (n) * 4 + 2 => हे (एन) हे इसलिए, समय-जटिलता की कुल आदेश होगा (एन)