का एक उप-भाग है या नहीं, दो बाइनरी पेड़ टी 1 और टी 2 हैं जो चरित्र डेटा स्टोर करते हैं, डुप्लिकेट की अनुमति है।
मुझे कैसे पता चलेगा कि टी 2 टी 1 का उप-धारा है या नहीं? ।
टी 1 में लाखों नोड्स हैं और टी 2 में सैकड़ों नोड्स हैं।पता लगाएं कि कोई पेड़ अन्य
ट्रैवर्स टी 1। यदि वर्तमान नोड टी 2 के रूट नोड के बराबर है, तो एक ही समय में दोनों पेड़ (टी 2 और टी 1 की वर्तमान उप-धारा) को पार करें। वर्तमान नोड की तुलना करें। यदि वे हमेशा बराबर होते हैं, तो टी 2 टी 1 का उप-भाग है।
गहराई को ध्यान में रखें। आपको केवल गहराई से 0 (T1_depth - T2_depth) खोजना है, मानते हुए 0 रूट गहराई और T1_depth> = T2_depth है। – schnaader
यह सच है। हालांकि, पेड़ को कैसे कार्यान्वित किया जाता है, इस पर निर्भर करता है कि टी 1 की गहराई ज्ञात नहीं हो सकती है। –
ऐसे पुराने प्रश्न को खोदने के लिए खेद है, लेकिन सवाल यह कहता है कि डेटा में डुप्लिकेट की अनुमति है। वास्तव में डुप्लीकेट्स होने पर, यह एल्गोरिदम सही ढंग से काम नहीं कर सकता है। क्या मैं कुछ भूल रहा हूँ? – Aditya
अपने पेड़ किसी भी तरह से पृथक नहीं किया जा रहे हैं, तो मैं तुलना में एक जानवर बल खोज करने के लिए किसी अन्य तरीके से नहीं दिख रहा है: पेड़ T1 के माध्यम से चलना और यदि आप एक नोड जो पहले से मेल खाता तक पहुँचने देखने के लिए जाँच पेड़ का नोड T2। यदि नहीं, तो T1 ट्रैवर्सिंग जारी रखें। यदि ऐसा है, तो जांचें कि अगले नोड्स मेल खाते हैं, जब तक आपको T2 का अंत नहीं मिलता है, इस मामले में आपके पास हिट है: आपका पेड़ T2 वास्तव में T1 का उप-सारांश है।
यदि आप T1 (पत्ती से नोड तक) के प्रत्येक नोड की गहराई को जानते हैं, तो आप किसी भी नोड्स को छोड़ सकते हैं जो उपट्री के रूप में गहरे नहीं हैं। इससे आपको बहुत सी जरूरतों को दूर करने में मदद मिल सकती है। का कहना है कि T1 और T2 अच्छी तरह से संतुलित कर रहे हैं, तो पेड़ T1 20 (2**20>1,000,000) और पेड़ T2 की कुल गहराई है 7 (2**7>100) की गहराई होगा। तुम सिर्फ 13 प्रथम परतों T1 की चलना होगा (8192 नोड्स - या यह है कि 14 परतों और 16384 नोड्स) और T1 बारे में 90% को छोड़ने के लिए सक्षम हो जाएगा ...
हालांकि, यदि उपट्री का मतलब है कि T2 के पत्ते नोड T1 के पत्ते नोड्स हैं, तो आप T1 का पहला ट्रैवर्सल कर सकते हैं और प्रत्येक नोड (पत्ता से नोड तक दूरी) की गहराई की गणना कर सकते हैं और फिर केवल उपट्रीज़ की जांच कर सकते हैं T2 के समान गहराई।
मैं एक एल्गोरिथ्म सुझाव है कि पूर्व प्रसंस्करण का उपयोग करता है:
1) पूर्व प्रक्रिया टी 1 पेड़, हर संभव सबट्री जड़ों की सूची रखने (कैश सूची प्रविष्टियों की एक लाखों होगा);
2) रूट में रखे गए डेटा के अवरोही क्रम से जड़ों की कैश की गई सूची को क्रमबद्ध करें। आप अधिक सुरुचिपूर्ण सॉर्टिंग फ़ंक्शन चुन सकते हैं, उदाहरण के लिए, स्ट्रिंग में एक वर्ण पेड़ को पार्स करें।
3) आवश्यक उप-पेड़ का पता लगाने के लिए बाइनरी खोज का उपयोग करें। आप नोड्स की संख्या के साथ subtrees को जल्दी से अस्वीकार कर सकते हैं, नोड्स की टी 2 संख्या (या विभिन्न गहराई के साथ) के बराबर नहीं।
ध्यान दें कि चरण 1) और 2) केवल एक बार किया जाना चाहिए, फिर आप एक ही प्रीप्रोसेस्ड परिणाम का उपयोग करके कई उप-वृक्ष उम्मीदवारों का परीक्षण कर सकते हैं।
मुझे यकीन नहीं है कि मेरा विचार सही है या नहीं। फिर भी, आपके निरंतर के लिए।
यदि आप मेमोरी/स्टोरेज बाध्य हैं (यानी वैकल्पिक रूपों में पेड़ों को प्री-मैनिपुलेट और स्टोर नहीं कर सकते हैं), तो शायद आप किसी अन्य द्वारा सुझाए गए ब्रूट फोर्स सर्च से बेहतर कुछ भी नहीं कर पाएंगे उत्तर (पी 2 के मिलान की जड़ की तलाश में ट्रैवर्स पी 1, दोनों यह पता लगाने के लिए कि क्या नोड वास्तव में मिलान करने वाले उप-पेड़ की जड़ है, मूल ट्रैवर्सल के साथ जारी है यदि यह एक मैच नहीं है)। यह खोज ओ (एन * एम) में संचालित होती है जहां n पी 1 का आकार होता है और एम पी 2 का आकार होता है। आपके द्वारा उपलब्ध पेड़ डेटा के आधार पर गहराई से जांच और अन्य संभावित अनुकूलन के साथ, इस आदमी को थोड़ा अनुकूलित किया जा सकता है, लेकिन यह अभी भी आम तौर पर ओ (एन * एम) है। आपकी विशिष्ट परिस्थितियों के आधार पर, यह एकमात्र उचित दृष्टिकोण हो सकता है।
यदि आप स्मृति/भंडारण बाध्य नहीं हैं और जटिलता को ध्यान में रखते हैं, तो मेरा मानना है कि generalized suffix tree की सहायता से longest common substring समस्या को कम करके ओ (एन + एम) में इसे बेहतर किया जा सकता है। इसी तरह की समस्या के लिए इस पर कुछ चर्चा here मिल सकती है। हो सकता है कि मेरे पास अधिक समय हो, मैं वापस आऊंगा और कार्यान्वयन पर अधिक विशिष्टताओं के साथ संपादित करूंगा।
मैं दोनों पेड़ को क्रमबद्ध कर दूंगा और यह पता लगाऊंगा कि दूसरा पहले की उप-स्ट्रिंग है या नहीं। हमारे पास लोकप्रिय भाषाओं में उपलब्ध सभी प्रकार के अनुकूलित उप-स्ट्रिंग खोज एल्गोरिदम हैं। – shuva
यदि दोनों पेड़ों की जड़ दिया, और यह देखते हुए कि नोड्स एक ही प्रकार के कर रहे हैं, क्यों फिर बस पता लगाने की है कि टी 2 की जड़ के लिए पर्याप्त नहीं T1 में है?
मुझे लगता है कि "एक पेड़ टी दिया गया" का अर्थ है टी की जड़ और नोड के डेटा प्रकार के लिए एक सूचक।
सम्मान।
मुझे लगता है कि हम जानवर बल द्वारा जाने की जरूरत है, लेकिन आप के पेड़ से मिलान करने के आप टी 1 में टी 2 की अपनी जड़ को खोजने के बाद की जरूरत क्यों है। यह वही नहीं है जब हमें नहीं पता कि पेड़ समान है या नहीं। (फिर केवल हमें पूरे पेड़ की तुलना करने की आवश्यकता है)
आपको पेड़ टी 1 और टी 2, पॉइंटर्स, मान नहीं दिए गए हैं।
तो नोड टी 2 (जो एक सूचक है), टी 1 पेड़ में मौजूद है।
तब ट्री टी 2 टी 1 की उप-धारा है।
संपादित करें:
सिर्फ अगर इसके ने कहा कि टी 2 वास्तव में वस्तु द्वारा एक अलग ट्री बुद्धिमान है, और हम यह पता लगाने की जरूरत है अगर वहाँ टी 1 में एक सबट्री, जो टी 2 के समान है है।
फिर यह काम नहीं करेगा।
और हम कोई अन्य विकल्प समाधान पहले से ही यहाँ पर चर्चा के लिए जाने के लिए की तुलना में है।
हम कहते हैं कि हम माता पिता के पेड़ और टी 2 एक पेड़ जो T1 का एक सबट्री हो सकता है के रूप में के रूप में टी 1 चला रहे हैं। निम्न कार्य करें। अनुमान लगाया गया है कि टी 1 और टी 2 बिना बाध्यकारी कारक के बाइनरी पेड़ हैं।
1) टी 1 में टी 2 की जड़ खोजें। यदि नहीं मिला टी 2 एक उप-धारा नहीं है। बीटी में तत्व खोजना ओ (एन) समय लेगा।
2) यदि तत्व पाया जाता है, कर टी 2 की नोड मूल तत्व से T1 के प्री-ऑर्डर ट्रेवर्सल पाया जाता है। यह ओ (एन) समय ले जाएगा। टी 2 के पूर्व-आदेश ट्रैवर्सल भी करें। ओ (एन) समय ले जाएगा। प्री-ऑर्डर ट्रैवर्सल का परिणाम स्टैक में संग्रहीत किया जा सकता है। ढेर में सम्मिलन केवल ओ (1) ले जाएगा।
3) दो ढेर के आकार के बराबर नहीं है, तो टी 2 एक सबट्री नहीं है।
4) प्रत्येक ढेर से एक तत्व पॉप करें और समानता की जांच करें। अगर विसंगति होती है, तो टी 2 एक उप-धारा नहीं है।
5) यदि सब elments का मिलान नहीं हुआ टी 2 एक सबट्री है।
मुझे लगता है कि अपने पेड़ अपरिवर्तनीय पेड़ तो आप किसी भी सबट्री (आप योजना की भाषा में set-car! ऐसा नहीं करते हैं) कभी नहीं रहे हैं, लेकिन केवल आपके पत्तियों से या मौजूदा पेड़ से नए पेड़ का निर्माण कर रहे हैं।
तब मैं करने की सलाह देंगे प्रत्येक नोड (या सबट्री) एक हैश कोड उस नोड के में रहते हैं। सी भाषा में, घोषित पेड़ रों
struct tree_st {
const unsigned hash;
const bool isleaf;
union {
const char*leafstring; // when isleaf is true
struct { // when isleaf is false
const struct tree_st* left;
const struct tree_st* right;
};
};
};
तो निर्माण समय में हैश की गणना, और जब समानता के लिए नोड्स की तुलना पहले समानता के लिए उनके हैश तुलना हो, अधिकांश समय हैश कोड अलग होगा (और आप सामग्री की तुलना परेशान नहीं करेंगे)।
यहाँ एक संभव पत्ती निर्माण कार्य है:
struct tree_st* make_leaf (const char*string) {
assert (string != NULL);
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
t->hash = hash_of_string(string);
t->isleaf = true;
t->leafstring = string;
return t;
}
एक हैश कोड
unsigned tree_hash(const struct tree_st *t) {
return (t==NULL)?0:t->hash;
}
समारोह है दो subtrees sleft & sright से एक नोड के निर्माण के लिए गणना करने के लिए समारोह है
struct tree_st*make_node (const struct tree_st* sleft,
const struct tree_st* sright) {
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
/// some hashing composition, e.g.
unsigned h = (tree_hash(sleft)*313)^(tree_hash(sright)*617);
t->hash = h;
t->left = sleft;
t->right = sright;
return t;
}
कॉम लाभ लेने कि अगर hashcodes अलग हैं comparands हैं (दो पेड़ों tx & ty की) समारोह धीरे-धीरे कम अलग
bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
if (tx==ty) return true;
if (tree_hash(tx) != tree_hash(ty)) return false;
if (!tx || !ty) return false;
if (tx->isleaf != ty->isleaf) return false;
if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
else return equal_tree(tx->left, ty->left)
&& equal_tree(tx->right, ty->right);
}
tree_hash(tx) != tree_hash(ty) परीक्षण सफल और आप नहीं होगा अधिकांश समय recurse।
hash consing बारे में पढ़ें।
एक बार जब आप इस तरह के एक कुशल हैश आधारित equal_tree कार्य हो आप तकनीक अन्य उत्तर में वर्णित इस्तेमाल कर सकते हैं (या हैंडबुक में)।
सादा रास्ता में से एक पेड़ के लिए is_equal() विधि लिख सकते हैं और निम्नलिखित करने के लिए,
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
ध्यान दें कि is_equal() पेड़ के लिए hashCode का उपयोग करके अनुकूलित किया जा सकता है। यह पेड़ की ऊंचाई या बच्चों की संख्या या मूल्यों की सीमा हैशकोड के रूप में सरल तरीके से किया जा सकता है।
bool is_equal(TNode*other) {
if(x != other->x) return false;
if(height != other->height) return false;
if(nchildren != other->nchildren) return false;
if(hashcode() != other->hashcode()) return false;
// do other checking for example check if the children are equal ..
}
जब पेड़ किसी लिंक की गई सूची के समान होता है, तो यह ओ (एन) समय लेगा। तुलना करने के लिए बच्चों को चुनते समय हम कुछ ह्युरिस्टिक का भी उपयोग कर सकते हैं।
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
if(is_equal(other)) return true;
if(left == NULL || right == NULL) {
return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
if(left->nchildren < right->nchildren) { // find in smaller child tree first
return (left->contains_subtree(other)) || right->contains_subtree(other);
} else {
return (right->contains_subtree(other)) || left->contains_subtree(other);
}
}
एक और तरीका है स्ट्रिंग के रूप में दोनों पेड़ को क्रमानुसार और अगर दूसरी स्ट्रिंग (टी 2 से धारावाहिक) पहली स्ट्रिंग के उप-स्ट्रिंग (टी 1 से धारावाहिक) है मिल रहा है।
निम्नलिखित कोड प्री-ऑर्डर में क्रमबद्ध है।
void serialize(ostream&strm) {
strm << x << '(';
if(left)
left->serialize(strm);
strm << ',';
if(right)
right->serialize(strm);
strm << ')';
}
और अगर एक पेड़ अन्य की एक उप-वृक्ष है हम कुछ अनुकूलित एल्गोरिथ्म का उपयोग कर सकते हैं, उदाहरण के लिए, Knuth–Morris–Pratt algorithm (संभवतः हे में (एन) समय) को खोजने के लिए सब-स्ट्रिंग के अस्तित्व और अंत में लगता है ।
फिर स्ट्रिंग को Burrows-Wheeler_transform के साथ कुशलतापूर्वक संपीड़ित किया जा सकता है। और संपीड़ित डेटा में उप-स्ट्रिंग को खोजने के लिए bzgrep संभव है।
एक और तरीका पेड़ में उप-पेड़ों को ऊंचाई और बच्चों की संख्या से सॉर्ट करना है।
bool compare(TNode*other) {
if(height != other->height)
return height < other->height;
return nchildren < other->nchildren;
}
ध्यान दें कि ओ (एन^2) उप-पेड़ होंगे। संख्या को कम करने के लिए हम ऊंचाई के आधार पर कुछ सीमा का उपयोग कर सकते हैं। उदाहरण के लिए, हम केवल 1500
को ऊंचाई 1000 की उप पेड़ों के बारे में रुचि हो सकती है क्रमबद्ध डेटा उसमें द्विआधारी खोज करते हैं और अगर यह में ओ (एलजी एन) उप-समुच्चय है खोजने के लिए संभव है उत्पन्न होता है जब समय (इस बात पर विचार करते हुए कि क्रमबद्ध डेटा में कोई डुप्लिकेट नहीं है)।
क्या पेड़ के पास कुछ प्रकार का ऑर्डरिंग है? जैसे क्या यह एक बाइनरी खोज पेड़ है? –
नहीं .. यह एक बाइनरी सेराच पेड़ नहीं है – sud03r
क्षमा करें, मैंने उपर्युक्त टिप्पणियों को गलत तरीके से पढ़ने के बाद इसे पेड़ (बाइनरी-पेड़ के बजाय) के रूप में दोबारा बनाया, लेकिन फिर मुझे अपनी गलती का एहसास हुआ :-) –