5
प्रत्यय पेड़ में अधिकतम और न्यूनतम संख्या में नोड्स क्या हैं? और मैं इसे कैसे साबित कर सकता हूं?प्रत्यय पेड़ में अधिकतम और न्यूनतम संख्या में नोड्स
A
उत्तर
6
लंबाई में N पात्रों में से एक इनपुट पाठ, नोड्स की न्यूनतम संख्या, रूट नोड और सभी पत्र-गांठ सहित मानते हुए,, N+1, नोड्स की अधिकतम संख्या, जड़ और पत्तियों सहित 2N-1 है।
न्यूनतम का सबूत: प्रत्येक प्रत्यय के लिए कम से कम एक पत्ता नोड होना चाहिए, और N प्रत्यय हैं। वहाँ किसी भी आंतरिक नोड्स, उदाहरण के होने की जरूरत नहीं:
इसलिए कम से कम है: अगर पाठ अद्वितीय प्रतीक, abc$ का क्रम है, वहाँ कोई शाखाओं, इसलिए जिसके परिणामस्वरूप प्रत्यय पेड़ में कोई आंतरिक नोड्स हैं N पत्तियां, 0 आंतरिक नोड्स, और 1 रूट नोड, N+1 नोड्स में। अधिकतम की
सबूत: पत्र-गांठ की संख्या N से बड़ा नहीं हो सकता है, क्योंकि एक पत्ता नोड जहां एक प्रत्यय समाप्त होता है, और आप लंबाई N की एक स्ट्रिंग में एक से अधिक N अलग प्रत्यय नहीं हो सकता। (वास्तव में, आपके पास हमेशा N विशिष्ट प्रत्यय हैं, इसलिए N पत्ती नोड्स बिल्कुल ठीक हैं।) रूट नोड हमेशा 1 है, इसलिए सवाल यह है कि आंतरिक नोड्स की अधिकतम संख्या क्या है। प्रत्येक भीतरी नोड पेड़ में एक शाखा पेश करता है (क्योंकि एक प्रत्यय पेड़ के भीतरी नोड्स में कम से कम 2 बच्चे होते हैं)। अंततः प्रत्येक नई शाखा को कम से कम एक अतिरिक्त पत्ता नोड का नेतृत्व करना चाहिए, इसलिए यदि आपके पास K आंतरिक नोड्स हैं, तो कम से कम K+1 पत्ती नोड्स होना चाहिए, और रूट नोड की उपस्थिति में कम से कम एक अतिरिक्त पत्ता की आवश्यकता होती है (जब तक कि पेड़ खाली न हो)। लेकिन पत्ती नोड्स की संख्या N से घिरा हुआ है, इसलिए आंतरिक नोड्स की अधिकतम संख्या N-2 द्वारा बाध्य है। यह कुल N पत्तियां, 1 रूट उत्पन्न करता है, और अधिकतम N-2 आंतरिक नोड्स, 2N-1 कुल मिलाकर।
यह देखने के लिए कि यह केवल सैद्धांतिक ऊपरी सीमा नहीं है, लेकिन कुछ प्रत्यय पेड़ वास्तव में इस अधिकतम तक पहुंचते हैं, उदाहरण के रूप में केवल एक बार दोहराए गए चरित्र के साथ एक स्ट्रिंग के रूप में विचार करें: 'aaa $'। पुष्टि करें कि इस के लिए प्रत्यय पेड़ 7 नोड्स है (रूट सहित और छोड़ देता है):
सारांश: के रूप में स्पष्ट है, केवल वास्तविक चर आंतरिक नोड्स की संख्या है, सभी प्रत्यय पेड़ों के लिए जड़ों और पत्तियों की संख्या 1 और N पर स्थिर है, जबकि आंतरिक नोड्स की संख्या 0 और N-2 के बीच भिन्न होती है।
+0
धन्यवाद! यह वास्तव में बहुत मदद करता है! –
स्टैक ओवरफ़्लो में आपका स्वागत है और पोस्टिंग के लिए धन्यवाद। कृपया दिखाने के लिए कुछ कोड शामिल करें [आपने जो कोशिश की] [http://whathaveyoutried.com) और [कैसे पूछें] (http://stackoverflow.com/questions/how-to-ask) पर एक नज़र डालें। –
यह इस प्रश्न का एक डुप्लिकेट है: http://stackoverflow.com/questions/12865639/maximum-and-minimum-number-of-edges-in-a-suffix-tree –
किनारों हैं, मैं इसे जानना चाहता हूं नोड्स के लिए। लागू करने के लिए कुछ भी नहीं है, मुझे सिर्फ यह जानना है कि प्रत्यय पेड़ में कितने नोड्स हो सकते हैं। –