टर्नरी सर्च ट्री
| Ternary Search Tree (TST) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | ||||||||||||
| Time complexity in big O notation | |||||||||||||
| |||||||||||||
कंप्यूटर विज्ञान में, टर्नरी सर्च ट्री ट्राइ का प्रकार है (जिसे कभी-कभी प्रीफिक्स ट्री भी कहा जाता है) जहां नोड्स को बाइनरी सर्च ट्री के समान विधि द्वारा व्यवस्थित किया जाता है, किन्तु बाइनरी ट्री दो की सीमा के अतिरिक्त तीन बच्चों तक होता है। अन्य प्रीफिक्स ट्री की भाँति, टर्नरी सर्च ट्री का उपयोग वृद्धिशील स्ट्रिंग सर्च की क्षमता के साथ सहयोगी मानचित्र संरचना के रूप में किया जा सकता है। यद्यपि, गति के मूल्य पर, टर्नरी सर्च ट्री मानक प्रीफिक्स ट्री की तुलना में अधिक स्थान कुशल हैं। टर्नरी सर्च ट्री के सामान्य अनुप्रयोगों में वर्तनी-अन्वेषण और स्वत: पूर्णता सम्मिलित है।
विवरण
टर्नरी सर्च ट्री का प्रत्येक नोड एकल कैरेक्टर (कला), ऑब्जेक्ट (या कार्यान्वयन के आधार पर किसी ऑब्जेक्ट के लिए पॉइंटर (कंप्यूटर प्रोग्रामिंग)) को संग्रहीत करता है, और इसके तीन बच्चों के लिए पॉइंटर्स को पारंपरिक रूप से समान किड, लो किड और हाय किड नाम दिया गया है, जिन्हें क्रमशः मध्य (बच्चा), निचला (बच्चा) और उच्चतर (बच्चा) भी कहा जा सकता है।[1] नोड में अपने मूल नोड के लिए पॉइंटर के साथ संकेतक भी हो सकता है कि नोड किसी शब्द के अंत को चिह्नित करता है या नहीं करता है।[2] लो किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर मान वर्तमान नोड से कम है। हाय किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर वर्तमान नोड से बड़ा है।[1] समान किड शब्द में अग्र कैरेक्टर की ओर संकेत करता है। नीचे दिया गया चित्र क्यूट, कप, एट, एज़, ही, यूएस और आई स्ट्रिंग के साथ टर्नरी सर्च ट्री दिखाता है:
c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s
अन्य ट्राई डेटा संरचनाओं की भाँति, टर्नरी सर्च ट्री में प्रत्येक नोड संग्रहीत स्ट्रिंग्स के उपसर्ग का प्रतिनिधित्व करता है। किसी नोड के मध्य सबट्री में सभी स्ट्रिंग उस उपसर्ग से प्रारम्भ होते हैं।
संचालन
इंसर्शन
टर्नरी सर्च में मान इन्सर्ट करने को लुकअप परिभाषित करने के समान ही रिकर्सिव या पुनरावृत्त रूप से परिभाषित किया जा सकता है। इस रिकर्सिव विधि को कुंजी दिए जाने पर ट्री के नोड्स पर निरंतर कॉल किया जाता है जो कुंजी के सामने से कैरेक्टरों को विभक्त करने पर उत्तरोत्तर छोटा होता जाता है। यदि यह विधि किसी ऐसे नोड तक पहुँचती है जो नहीं बनाया गया है, तो यह नोड बनाता है और उसे कुंजी में प्रथम कैरेक्टर का कैरेक्टर मान निर्दिष्ट करता है। कोई नया नोड बनाया गया है या नहीं, विधि यह देखने के लिए जांच करती है कि स्ट्रिंग में प्रथम कैरेक्टर नोड में कैरेक्टर मान से अधिक है या कम है और लुकअप ऑपरेशन के अनुसार उपयुक्त नोड पर रिकर्सिव कॉल करता है। यद्यपि, यदि कुंजी का प्रथम कैरेक्टर नोड के मान के समान है तो सम्मिलन प्रक्रिया को समान किड पर कॉल किया जाता है और कुंजी का प्रथम कैरेक्टर कम कर दिया जाता है।[1] बाइनरी सर्च ट्री और अन्य डेटा संरचनाओं की भाँति, टर्नरी सर्च ट्री कुंजियों के क्रम के आधार पर पतित हो सकते हैं।[3] वर्णानुक्रम में इन्सर्टिंग कुंजियाँ निकृष्ट संभावित ट्री को प्राप्त करने की विधि है।[1] कुंजियों को यादृच्छिक क्रम में इन्सर्ट करने पर अधिकांशतः उचित प्रकार से संतुलित ट्री बनता है।[1]
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 > फ़ंक्शन इंसर्शन (स्ट्रिंग कुंजी) है नोड पी= रूट
//रूट शून्य होने की स्थिति में बराबर होने के लिए आरंभ किया गया
नोड अंतिम= रूट पूर्णांक आईडीएक्स= 0 जबकि p शून्य नहीं है
//उचित उपवृक्ष पर पुनरावृत्ति करें
यदि key[idx] < p.splitchar तो अंतिम= पी पी= पी.बाएं अन्यथा यदि key[idx] > p.splitchar तो अंतिम= पी पी= पी.सही अन्य:
// कुंजी पहले से ही हमारे ट्री में है
यदि idx == लंबाई (कुंजी) तो वापस करना
// हमारी कुंजी से चरित्र ट्रिम करें
आईडीएक्स= आईडीएक्स+1 अंतिम= पी पी:= पी.मध्य पी= नोड()
// अंतिम गैर-शून्य नोड के चाइल्ड के रूप में p जोड़ें (या यदि रूट शून्य है तो रूट करें)
यदि रूट == शून्य है तो
जड़:= पी
अन्यथा यदि Last.splitchar < key[idx] तो अंतिम.दाएं:= पी अन्यथा यदि Last.splitchar > key[idx] तो अंतिम.बाएं= पी अन्य अंतिम.मध्य = पी p.स्प्लिटचर= कुंजी[idx] आईडीएक्स:= आईडीएक्स+1
// कुंजी का शेष भाग डालें
जबकि idx < length(key) करते हैं p.mid:= नोड()
p.mid.splitchar:= कुंजी[idx]
आईडीएक्स += 1 </सिंटैक्सहाइलाइट>
सर्च
किसी विशेष नोड या नोड से संयोजित डेटा को देखने के लिए, स्ट्रिंग कुंजी की आवश्यकता होती है। लुकअप प्रक्रिया ट्री के रूट नोड का अन्वेषण करके और यह निर्धारित करके प्रारम्भ होती है कि निम्नलिखित में से कौन सी स्थिति उत्पन्न हुई है। यदि स्ट्रिंग का प्रथम कैरेक्टर रूट नोड के कैरेक्टर से कम है, तो उस ट्री पर रिकर्सिव लुकअप को कॉल किया जा सकता है जिसका रूट वर्तमान रूट का लो किड है। इसी प्रकार, यदि प्रथम कैरेक्टर ट्री में वर्तमान नोड से बड़ा है, तो उस ट्री पर रिकर्सिव कॉल की जा सकती है जिसका रूट वर्तमान नोड का हाय किड है।[1] अंतिम स्थिति के रूप में, यदि स्ट्रिंग का प्रथम कैरेक्टर वर्तमान नोड के कैरेक्टर के समान है तो कुंजी में अन्य कैरेक्टर नहीं होने पर फ़ंक्शन नोड रिटर्न करता है। यदि कुंजी में अधिक कैरेक्टर हैं तो कुंजी का प्रथम कैरेक्टर विस्थापित कर दिया जाना चाहिए और समान किड नोड और संशोधित कुंजी को देखते हुए रिकर्सिव कॉल किया जाना चाहिए।[1] इसे वर्तमान नोड के लिए पॉइंटर और कुंजी के वर्तमान कैरेक्टर के लिए पॉइंटर का उपयोग करके नॉन-रिकर्सिव प्रकार से भी लिखा जा सकता है।[1]
स्यूडोकोड
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
फ़ंक्शन खोज (स्ट्रिंग क्वेरी) है
यदि is_empty(क्वेरी) है तो
विवरण झूठा है
नोड पी:= रूट
पूर्णांक आईडीएक्स:= 0
जबकि p शून्य नहीं है
यदि क्वेरी[idx] <p.splitchar तो
पी:= पी.बाएं
अन्यथा यदि query[idx] > p.splitchar तो
पी:= पी.सही;
अन्य
यदि idx = लंबाई(क्वेरी) तो
सच लौटें
आईडीएक्स:= आईडीएक्स + 1
पी:= पी.मध्य
विवरण झूठा है
</सिंटैक्सहाइलाइट>
विलोपन
डिलीट ऑपरेशन में सर्च ट्री में एक कुंजी स्ट्रिंग की खोज करना और एक नोड ढूंढना सम्मिलित है, जिसे नीचे छद्म कोड में फर्स्टमिड कहा जाता है, जैसे कि फर्स्टमिड के मध्य चाइल्ड से लेकर कुंजी स्ट्रिंग के लिए खोज पथ के अंत तक का कोई रास्ता नहीं है। या सही बच्चे. यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में एक अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पथ नहीं है, तो इसका मतलब है कि कुंजी स्ट्रिंग या तो पूरी तरह से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, या खोज ट्री में नहीं है। कई कार्यान्वयन केवल बाद वाले मामले को सुनिश्चित करने के लिए स्ट्रिंग कैरेक्टर के अंत का उपयोग करते हैं। फिर पथ को फर्स्टमिड.मिड से खोज पथ के अंत तक हटा दिया जाता है। इस मामले में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग ट्री में आखिरी स्ट्रिंग रही होगी, और इस प्रकार रूट को हटाने के बाद शून्य पर सेट किया गया है। <सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
फ़ंक्शन डिलीट (स्ट्रिंग कुंजी) है
यदि is_empty(key) है तो
वापस करना
नोड पी:= रूट
पूर्णांक आईडीएक्स:= 0
नोड फर्स्टमिड:= शून्य
जबकि p शून्य नहीं है
यदि key[idx] < p.splitchar तो
फर्स्टमिड:= शून्य
पी:= पी.बाएं
अन्यथा यदि key[idx] > p.splitchar तो
फर्स्टमिड:= शून्य
पी:= पी.सही
अन्य
फर्स्टमिड:= पी
जबकि p शून्य नहीं है और key[idx] == p.splitchar करते हैं
आईडीएक्स:= आईडीएक्स + 1
पी:= पी.मध्य
यदि फर्स्टमिड == शून्य है तो
वापसी // कोई अद्वितीय स्ट्रिंग प्रत्यय नहीं
// इस बिंदु पर, फर्स्टमिड स्ट्रिंग अद्वितीय प्रत्यय होने से पहले नोड को इंगित करता है
नोड q:= फर्स्टमिड.मिड
नोड पी:= क्यू
फर्स्टमिड.मिड:= शून्य // ट्री से प्रत्यय को डिस्कनेक्ट करें
जबकि q शून्य नहीं है //प्रत्यय पथ पर चलें और नोड्स हटा दें
पी:= क्यू
q:= q.मध्य
डिलीट(पी) // नोड पी से जुड़ी मुफ्त मेमोरी
यदि फर्स्टमिड == रूट है तो
डिलीट(रूट) // पूरे ट्री को हटा दें
जड़:= शून्य
</सिंटैक्सहाइलाइट>
ट्रैवर्सल
आंशिक-मिलान खोज
निकट-पड़ोसी खोज रहा है
चलने का समय
टर्नरी सर्च ट्री का चलने का समय इनपुट के साथ काफी भिन्न होता है। जब कई समान स्ट्रिंग दी जाती हैं तो टर्नरी सर्च ट्री सबसे अच्छे से चलते हैं, खासकर जब वे स्ट्रिंग एक सामान्य उपसर्ग साझा करते हैं। वैकल्पिक रूप से, बड़ी संख्या में अपेक्षाकृत छोटी स्ट्रिंग्स (जैसे शब्दकोश में शब्द) को संग्रहीत करते समय टर्नरी सर्च ट्री प्रभावी होते हैं।[1]टर्नरी सर्च ट्री के लिए चलने का समय बाइनरी खोज ट्री के समान है, जिसमें वे आम तौर पर लॉगरिदमिक समय में चलते हैं, किन्तु खराब (सबसे खराब) स्थिति में रैखिक समय में चल सकते हैं। इसके अलावा, रनटाइम पर विचार करते समय स्ट्रिंग्स के आकार को भी ध्यान में रखा जाना चाहिए। उदाहरण के लिए, लंबाई k की एक स्ट्रिंग के लिए खोज पथ में, ट्री में मध्य बच्चों के नीचे k ट्रैवर्सल होंगे, साथ ही ट्री में बाएं और दाएं बच्चों के नीचे ट्रैवर्सल की एक लघुगणकीय संख्या होगी। इस प्रकार, एक टर्नरी सर्च ट्री में बहुत बड़ी स्ट्रिंग्स की एक छोटी संख्या पर स्ट्रिंग्स की लंबाई रनटाइम पर हावी हो सकती है।[4] टर्नरी सर्च ट्री संचालन के लिए समय जटिलताएँ:[1]
| Average-case running time | Worst-case running time | |
|---|---|---|
| Lookup | O(log n + k) | O(n + k) |
| Insertion | O(log n + k) | O(n + k) |
| Delete | O(log n + k) | O(n + k) |
अन्य डेटा संरचनाओं से तुलना
प्रयास
अन्य प्रयासों की तुलना में धीमे होने के बावजूद, टर्नरी सर्च ट्री अपनी स्थान-दक्षता के कारण बड़े डेटा सेट के लिए बेहतर अनुकूल हो सकते हैं।[1]
हैश मानचित्र
स्ट्रिंग्स को मानों में मैप करने के लिए टर्नरी सर्च ट्री के स्थान पर हैश तालिका ्स का भी उपयोग किया जा सकता है। यद्यपि, हैश मानचित्र भी अक्सर टर्नरी सर्च ट्री की तुलना में अधिक मेमोरी का उपयोग करते हैं (किन्तु उतना नहीं जितना प्रयास किया जाता है)। इसके अतिरिक्त, हैश मैप आमतौर पर एक स्ट्रिंग की रिपोर्ट करने में धीमे होते हैं जो समान डेटा संरचना में नहीं है, क्योंकि इसमें केवल पहले कुछ कैरेक्टरों की तुलना में पूरी स्ट्रिंग की तुलना करनी होगी। ऐसे कुछ सबूत हैं जो टर्नरी सर्च ट्री को हैश मैप की तुलना में तेजी से चलते हुए दिखाते हैं।[1]इसके अतिरिक्त, हैश मानचित्र टर्नरी सर्च ट्रीों के कई उपयोगों की अनुमति नहीं देते हैं, जैसे कि निकट-पड़ोसी लुकअप।
डीएएफएसए (नियतात्मक चक्रीय परिमित अवस्था ऑटोमेटन)
यदि शब्दकोश शब्दों को संग्रहीत करना ही आवश्यक है (यानी, प्रत्येक शब्द के लिए सहायक जानकारी का भंडारण आवश्यक नहीं है), तो न्यूनतम नियतात्मक चक्रीय परिमित राज्य ऑटोमेटन (डीएएफएसए) एक ट्राई या टर्नरी सर्च ट्री की तुलना में कम जगह का उपयोग करेगा। ऐसा इसलिए है क्योंकि एक डीएएफएसए त्रि से समान शाखाओं को संपीड़ित कर सकता है जो संग्रहीत किए जा रहे विभिन्न शब्दों के समान प्रत्ययों (या भागों) से मेल खाते हैं।
उपयोग
टर्नरी सर्च ट्री का उपयोग कई समस्याओं को हल करने के लिए किया जा सकता है जिसमें बड़ी संख्या में स्ट्रिंग्स को मनमाने क्रम में संग्रहीत और पुनर्प्राप्त किया जाना चाहिए। इनमें से कुछ सबसे आम या सबसे उपयोगी नीचे हैं:
- किसी भी समय ट्राई का उपयोग किया जा सकता है किन्तु कम मेमोरी खपत वाली संरचना को प्राथमिकता दी जाती है।[1]* अन्य डेटा के लिए डेटा मैपिंग स्ट्रिंग के लिए एक त्वरित और स्थान-बचत डेटा संरचना।[3]* स्वतः पूर्णता लागू करने के लिए।[2]
- वर्तनी जाँच के रूप में।[5]
- निकटतम पड़ोसी खोज|निकट-पड़ोसी खोज (जिसमें वर्तनी-जांच एक विशेष मामला है)।[1]* एक डेटाबेस के रूप में, विशेष रूप से जब कई गैर-कुंजी फ़ील्ड द्वारा अनुक्रमण वांछनीय है।[5]* हैश तालिका के स्थान पर.[5]
यह भी देखें
- थ्री-वे रेडिक्स क्विकसॉर्ट
- प्रयास करें
- बाइनरी सर्च ट्री
- हैश तालिका
संदर्भ
- ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 "टर्नरी खोज वृक्ष". Dr. Dobb's.
- ↑ 2.0 2.1 Ostrovsky, Igor. "टर्नरी सर्च ट्री के साथ कुशल स्वतः पूर्ण".
- ↑ 3.0 3.1 Wrobel, Lukasz. "टर्नेरी सर्च ट्री".
- ↑ Bentley, Jon; Sedgewick, Bob. "टर्नेरी सर्च ट्री".
- ↑ 5.0 5.1 5.2 Flint, Wally (February 16, 2001). "अपने डेटा को टर्नरी सर्च ट्री में रोपित करें". JavaWorld. Retrieved 2020-07-19.
बाहरी संबंध
- Ternary Search Trees page with papers (by Jon Bentley and Robert Sedgewick) about ternary search trees and algorithms for "sorting and searching strings"
- Ternary Search Tries – a video by Robert Sedgewick
- TST.java.html Implementation in Java of a TST by Robert Sedgewick and Kevin Wayne
