ट्राइ, या लोडेड ट्री

नमस्कार, हबहार। आज मैं इस तरह के एक अद्भुत डेटा संरचना के बारे में बात करना चाहता हूं जो एक लोड किए गए पेड़ पर एक शब्दकोश के रूप में जाना जाता है, जिसे एक उपसर्ग वृक्ष , या त्रिक के रूप में भी जाना जाता है।

यह क्या है

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

यह कैसे काम करता है?

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



आकृति में आप चाबियाँ सी, कैप, कार, सीडीआर, गो, इफ, इट के साथ एक भरे हुए पेड़ का एक उदाहरण देख सकते हैं।







और कार की चाबी वाला एक ही पेड़ उस पर प्रकाश डाला।







यह तुरंत स्पष्ट है कि हमारे पेड़ में "अतिरिक्त" कुंजियाँ हैं, क्योंकि पेड़ में किसी भी नोड के पास जड़ से एक अनूठा रास्ता है, और इसलिए यह कुंजी है। "अतिरिक्त" कुंजियों के साथ समस्या से बचने के लिए, एक बूलियन विशेषता को पेड़ के प्रत्येक नोड में जोड़ा जाता है, यह दर्शाता है कि क्या नोड वास्तव में मौजूदा है या सड़क पर किसी अन्य के साथ मध्यवर्ती है।

मूल संचालन

चूंकि लोड किए गए पेड़ एक साहचर्य सरणी के इंटरफ़ेस को लागू करते हैं, इसलिए तीन मुख्य कार्यों को इसमें सम्मिलित किया जा सकता है, अर्थात्, सम्मिलन, विलोपन और कुंजी खोज। कई पेड़ों की तरह, एक लोडेड पेड़ में आत्म-समानता की संपत्ति होती है, अर्थात इसके किसी भी उप-पेड़ भी पूर्ण-लोड वाले पेड़ हैं। यह नोटिस करना आसान है कि इस तरह के एक सबट्री में सभी कुंजी में एक सामान्य उपसर्ग होता है, (जो कि "प्रीफिक्स ट्री" नाम से आता है), जिसका अर्थ है कि हम इस पेड़ के लिए एक विशिष्ट ऑपरेशन को भेद कर सकते हैं - समय में दिए गए उपसर्ग के साथ पेड़ की सभी कुंजी प्राप्त करना O (! Prefix |)।

कुंजी खोज

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



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



इस एल्गोरिथ्म की समय जटिलता स्पष्ट रूप से हे (| कुंजी) है।



एल्गोरिथ्म को ब्लॉक आरेख में अधिक विस्तार से दिखाया गया है:

डालने

ट्री की कुंजी जोड़ने के लिए एल्गोरिथ्म खोज एल्गोरिथ्म के समान है।



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



कुंजी जोड़ने की समय जटिलता हे (| कुंजी |) है।



एक फ़्लोचार्ट में एल्गोरिथम चित्रण:

निष्कासन

चाबी निकालना भी बहुत आसान है।



चाबी दी जाए, जिसे पेड़ से हटा दिया जाए। हम इस कुंजी की खोज करेंगे। यदि शब्दकोश में कुंजी मौजूद है, तो जिस नोड से मेल खाती है, उसे जानने के बाद, आप इसे मध्यवर्ती के रूप में चिह्नित कर सकते हैं, जिससे बाद की खोजों के लिए यह "अदृश्य" हो सकता है।

उसके बाद, आप "डिस्कनेक्ट" नोड से रूट तक बढ़ सकते हैं, साथ ही साथ सभी नोड्स को हटा सकते हैं जो पत्ते हैं, हालांकि, इस मामले में मेमोरी बचत महत्वपूर्ण नहीं है, और प्रभावी रूप से यह निर्धारित करने के लिए कि नोड एक पत्ती है, आपको एक अतिरिक्त नोड विशेषता पेश करने की आवश्यकता है।



विलोपन एल्गोरिथ्म का एक अस्थायी मूल्यांकन पहले से ही ओ (| कुंजी |) से परिचित है।

संसाधन की आवश्यकताएं

मेमोरी / सीपीयू समय की खपत के मामले में भरा हुआ पेड़ हैश टेबल और संतुलित पेड़ों से नीच नहीं है, और कभी-कभी इन मापदंडों में उन्हें पार कर जाता है।

सीपीयू समय

डालने, हटाने और खोज कार्यों की जटिलता हे (| कुंजी |) है। हालाँकि संतुलित पेड़ O (ln (n)) में इन ऑपरेशनों को करते हैं, लेकिन स्पर्शोन्मुख व्यवहार कुंजी की तुलना करने के लिए आवश्यक समय को छुपाता है, जो कि सामान्य स्थिति में O (| Key |) है। हैश तालिकाओं के साथ, स्थिति समान है - भले ही पहुंच का समय O (1 + a) है, यह हैश लेने के लिए O (- कुंजी |) लेता है (यदि यह पहले से गणना नहीं है, तो निश्चित रूप से)।



लोड किए गए पेड़ों, हैश टेबल और लाल-काले पेड़ों के प्रदर्शन की तुलना करने वाले चार्ट अंग्रेजी विकिपीडिया पर देखे जा सकते हैं।

स्मृति

स्मृति की खपत में, एक भरा हुआ पेड़ अक्सर हैश टेबल और संतुलित पेड़ों से बेहतर प्रदर्शन करता है। यह इस तथ्य के कारण है कि एक भरे हुए पेड़ में कई चाबियाँ एक ही उपसर्ग हैं, और उनके साथ स्मृति जो वे उपयोग करते हैं। इसके अलावा, संतुलित पेड़ों के विपरीत, एक भरे हुए पेड़ में प्रत्येक नोड में एक कुंजी को संग्रहीत करने की आवश्यकता नहीं है।

अनुकूलन

एक लोड किए गए पेड़ के अनुकूलन के 2 मुख्य प्रकार हैं:

• संपीड़न। एक संपीड़ित लोडेड पेड़ को सामान्य नोड से एक एकल गैर-मध्यवर्ती नोड को हटाने के द्वारा प्राप्त किया जाता है। उदाहरण के लिए, एक , बी, सी लेबल वाले मध्यवर्ती नोड्स की एक श्रृंखला को एबीसी लेबल किए गए एक नोड द्वारा प्रतिस्थापित किया जाता है।
• पेट्रीसिया । पेट्रीसिया से लदे पेड़ को एक बच्चे के मध्यवर्ती नोड्स को हटाकर एक संपीड़ित (या साधारण) से प्राप्त किया जाता है।

यह सब क्यों जरूरी है?

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



बस इतना ही। मुझे आशा है कि पाठक इस अद्भुत डेटा संरचना के बारे में जानने के लिए इच्छुक थे, जो कि हेरेबे पर अवांछनीय रूप से शायद ही कभी उल्लेख किया गया है।