टर्नरी सर्च ट्री: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 11: Line 11:
}}
}}


[[कंप्यूटर विज्ञान]] में, टर्नरी सर्च ट्री [[ प्रयास करें |ट्राइ]] का प्रकार है (जिसे कभी-कभी ''प्रीफिक्स ट्री'' भी कहा जाता है) जहां नोड्स को [[बाइनरी सर्च ट्री]] के समान विधि द्वारा व्यवस्थित किया जाता है, किन्तु बाइनरी ट्री दो की सीमा के अतिरिक्त तीन बच्चों तक होता है। अन्य प्रीफिक्स ट्री की भाँति, टर्नरी सर्च ट्री का उपयोग वृद्धिशील [[स्ट्रिंग खोज|स्ट्रिंग सर्च]] की क्षमता के साथ [[सहयोगी मानचित्र]] संरचना के रूप में किया जा सकता है। यद्यपि, गति के मूल्य पर, टर्नरी सर्च ट्री मानक प्रीफिक्स ट्री की तुलना में अधिक स्थान कुशल हैं। टर्नरी सर्च ट्री के सामान्य अनुप्रयोगों में वर्तनी-अन्वेषण और स्वत: पूर्णता सम्मिलित है।
[[कंप्यूटर विज्ञान]] में, टर्नरी सर्च ट्री [[ प्रयास करें |ट्राइ]] का प्रकार है (जिसे कभी-कभी ''प्रीफिक्स ट्री'' भी कहा जाता है) जहां नोड्स को [[बाइनरी सर्च ट्री]] के समान विधि द्वारा व्यवस्थित किया जाता है, किन्तु बाइनरी ट्री दो की सीमा के अतिरिक्त तीन चाइल्ड तक होता है। अन्य प्रीफिक्स ट्री की भाँति, टर्नरी सर्च ट्री का उपयोग वृद्धिशील [[स्ट्रिंग खोज|स्ट्रिंग सर्च]] की क्षमता के साथ [[सहयोगी मानचित्र]] संरचना के रूप में किया जा सकता है। यद्यपि, गति के मूल्य पर, टर्नरी सर्च ट्री मानक प्रीफिक्स ट्री की तुलना में अधिक स्थान कुशल हैं। टर्नरी सर्च ट्री के सामान्य अनुप्रयोगों में वर्तनी-अन्वेषण और स्वत: पूर्णता सम्मिलित है।


==विवरण==
==विवरण==
टर्नरी सर्च ट्री का प्रत्येक नोड एकल कैरेक्टर (कला), ऑब्जेक्ट (या कार्यान्वयन के आधार पर किसी ऑब्जेक्ट के लिए [[ सूचक (कंप्यूटर प्रोग्रामिंग) |पॉइंटर (कंप्यूटर प्रोग्रामिंग)]]) को संग्रहीत करता है, और इसके तीन बच्चों के लिए पॉइंटर्स को पारंपरिक रूप से समान किड, लो किड और हाय किड नाम दिया गया है, जिन्हें क्रमशः मध्य (बच्चा), निचला (बच्चा) और उच्चतर (बच्चा) भी कहा जा सकता है।<ref name="dobbs">{{cite journal |journal=[[Dr. Dobb's]] |title=टर्नरी खोज वृक्ष|url=http://www.drdobbs.com/database/184410528}}</ref> नोड में अपने मूल नोड के लिए पॉइंटर के साथ संकेतक भी हो सकता है कि नोड किसी शब्द के अंत को चिह्नित करता है या नहीं करता है।<ref name="ostrov" /> लो किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर मान वर्तमान नोड से कम है। हाय किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर वर्तमान नोड से बड़ा है।<ref name="dobbs" /> समान किड शब्द में अग्र कैरेक्टर की ओर संकेत करता है। नीचे दिया गया चित्र क्यूट, कप, एट, एज़, ही, यूएस और आई स्ट्रिंग के साथ टर्नरी सर्च ट्री दिखाता है:
टर्नरी सर्च ट्री का प्रत्येक नोड एकल कैरेक्टर (कला), ऑब्जेक्ट (या कार्यान्वयन के आधार पर किसी ऑब्जेक्ट के लिए [[ सूचक (कंप्यूटर प्रोग्रामिंग) |पॉइंटर (कंप्यूटर प्रोग्रामिंग)]]) को संग्रहीत करता है, और इसके तीन चाइल्ड के लिए पॉइंटर्स को पारंपरिक रूप से समान किड, लो किड और हाय किड नाम दिया गया है, जिन्हें क्रमशः मध्य (चाइल्ड), निचला (चाइल्ड) और उच्चतर (चाइल्ड) भी कहा जा सकता है।<ref name="dobbs">{{cite journal |journal=[[Dr. Dobb's]] |title=टर्नरी खोज वृक्ष|url=http://www.drdobbs.com/database/184410528}}</ref> नोड में अपने मूल नोड के लिए पॉइंटर के साथ इंडिकेटर भी हो सकता है कि नोड किसी शब्द के अंत को चिह्नित करता है या नहीं करता है।<ref name="ostrov" /> लो किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर मान वर्तमान नोड से कम है। हाय किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर वर्तमान नोड से बड़ा है।<ref name="dobbs" /> समान किड शब्द में अग्र कैरेक्टर की ओर संकेत करता है। नीचे दिया गया चित्र क्यूट, कप, एट, एज़, ही, यूएस और आई स्ट्रिंग के साथ टर्नरी सर्च ट्री दिखाता है:


           c
           c
Line 80: Line 80:


<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
  फ़ंक्शन खोज (स्ट्रिंग क्वेरी) है
  फ़ंक्शन सर्च (स्ट्रिंग क्वेरी) है
     यदि is_empty(क्वेरी) है तो
     यदि is_empty(क्वेरी) है तो
         विवरण झूठा है
         विवरण झूठा है
Line 101: Line 101:
</सिंटैक्सहाइलाइट>
</सिंटैक्सहाइलाइट>


=== विलोपन ===
=== डिलीशन ===
 
डिलीट ऑपरेशन में सर्च ट्री में कुंजी स्ट्रिंग को सर्च करना और नोड को फाइंड करना सम्मिलित है, जिसे नीचे सुडो कोड में फर्स्टमिड कहा जाता है, जिस प्रकार कुंजी स्ट्रिंग के लिए सर्च पाथ के फर्स्टमिड के मध्य चाइल्ड से अंत तक के पाथ में कोई बाएँ या दाएँ चाइल्ड नहीं है। यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पाथ नहीं है, तो इसका अर्थ है कि कुंजी स्ट्रिंग या तो पूर्ण रूप से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, अथवा सर्च ट्री में नहीं है। कई कार्यान्वयन केवल पश्चात की स्थिति को सुनिश्चित करने के लिए स्ट्रिंग कैरेक्टर के अंत का उपयोग करते हैं। तत्पश्चात पाथ को फर्स्टमिड.मिड से सर्च पाथ के अंत तक डिलीट कर दिया जाता है। इस स्थिति में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग ट्री में अंतिम स्ट्रिंग होनी चाहिए, और इस प्रकार रूट को डिलीट करने के पश्चात शून्य पर सेट किया जाता है।


डिलीट ऑपरेशन में सर्च ट्री में एक कुंजी स्ट्रिंग की खोज करना और एक नोड ढूंढना सम्मिलित है, जिसे नीचे छद्म कोड में फर्स्टमिड कहा जाता है, जैसे कि फर्स्टमिड के मध्य चाइल्ड से लेकर कुंजी स्ट्रिंग के लिए खोज पथ के अंत तक का कोई रास्ता नहीं है। या सही बच्चे. यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में एक अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पथ नहीं है, तो इसका मतलब है कि कुंजी स्ट्रिंग या तो पूरी तरह से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, या खोज ट्री में नहीं है। कई कार्यान्वयन केवल बाद वाले मामले को सुनिश्चित करने के लिए स्ट्रिंग कैरेक्टर के अंत का उपयोग करते हैं। फिर पथ को फर्स्टमिड.मिड से खोज पथ के अंत तक हटा दिया जाता है। इस मामले में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग ट्री में आखिरी स्ट्रिंग रही होगी, और इस प्रकार रूट को हटाने के बाद शून्य पर सेट किया गया है।
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
  फ़ंक्शन डिलीट (स्ट्रिंग कुंजी) है
  फ़ंक्शन डिलीट (स्ट्रिंग कुंजी) है
Line 133: Line 134:
     नोड पी:= क्यू
     नोड पी:= क्यू
     फर्स्टमिड.मिड:= शून्य // ट्री से प्रत्यय को डिस्कनेक्ट करें
     फर्स्टमिड.मिड:= शून्य // ट्री से प्रत्यय को डिस्कनेक्ट करें
     जबकि q शून्य नहीं है //प्रत्यय पथ पर चलें और नोड्स हटा दें
     जबकि q शून्य नहीं है //प्रत्यय पाथ पर चलें और नोड्स हटा दें
         पी:= क्यू
         पी:= क्यू
         q:= q.मध्य
         q:= q.मध्य
Line 144: Line 145:
=== ट्रैवर्सल ===
=== ट्रैवर्सल ===


=== आंशिक-मिलान खोज ===
=== पार्शियल-मैच सर्चिंग ===


=== निकट-पड़ोसी खोज रहा है ===
=== नियर-नेबर सर्चिंग ===


==चलने का समय==
==रनिंग टाइम==
टर्नरी सर्च ट्री का चलने का समय इनपुट के साथ काफी भिन्न होता है। जब कई समान स्ट्रिंग दी जाती हैं तो टर्नरी सर्च ट्री सबसे अच्छे से चलते हैं, खासकर जब वे स्ट्रिंग एक सामान्य उपसर्ग साझा करते हैं। वैकल्पिक रूप से, बड़ी संख्या में अपेक्षाकृत छोटी स्ट्रिंग्स (जैसे शब्दकोश में शब्द) को संग्रहीत करते समय टर्नरी सर्च ट्री प्रभावी होते हैं।<ref name ="dobbs" />टर्नरी सर्च ट्री के लिए चलने का समय [[बाइनरी खोज पेड़|बाइनरी खोज ट्री]] के समान है, जिसमें वे आम तौर पर लॉगरिदमिक समय में चलते हैं, किन्तु खराब (सबसे खराब) स्थिति में रैखिक समय में चल सकते हैं। इसके अलावा, रनटाइम पर विचार करते समय स्ट्रिंग्स के आकार को भी ध्यान में रखा जाना चाहिए। उदाहरण के लिए, लंबाई k की एक स्ट्रिंग के लिए खोज पथ में, ट्री में मध्य बच्चों के नीचे k ट्रैवर्सल होंगे, साथ ही ट्री में बाएं और दाएं बच्चों के नीचे ट्रैवर्सल की एक लघुगणकीय संख्या होगी। इस प्रकार, एक टर्नरी सर्च ट्री में बहुत बड़ी स्ट्रिंग्स की एक छोटी संख्या पर स्ट्रिंग्स की लंबाई रनटाइम पर हावी हो सकती है।<ref name="sedgewick">{{cite web|last1=Bentley|last2=Sedgewick |first1=Jon|first2=Bob|title=टर्नेरी सर्च ट्री|url=https://www.cs.upc.edu/~ps/downloads/tst/tst.html}}</ref>
टर्नरी सर्च ट्री का चलने का समय इनपुट के साथ काफी भिन्न होता है। जब कई समान स्ट्रिंग दी जाती हैं तो टर्नरी सर्च ट्री सबसे अच्छे से चलते हैं, खासकर जब वे स्ट्रिंग एक सामान्य उपसर्ग साझा करते हैं। वैकल्पिक रूप से, बड़ी संख्या में अपेक्षाकृत छोटी स्ट्रिंग्स (जैसे शब्दकोश में शब्द) को संग्रहीत करते समय टर्नरी सर्च ट्री प्रभावी होते हैं।<ref name ="dobbs" />टर्नरी सर्च ट्री के लिए चलने का समय [[बाइनरी खोज पेड़|बाइनरी सर्च ट्री]] के समान है, जिसमें वे आम तौर पर लॉगरिदमिक समय में चलते हैं, किन्तु खराब (सबसे खराब) स्थिति में रैखिक समय में चल सकते हैं। इसके अलावा, रनटाइम पर विचार करते समय स्ट्रिंग्स के आकार को भी ध्यान में रखा जाना चाहिए। उदाहरण के लिए, लंबाई k की एक स्ट्रिंग के लिए सर्च पाथ में, ट्री में मध्य चाइल्ड के नीचे k ट्रैवर्सल होंगे, साथ ही ट्री में बाएं और दाएं चाइल्ड के नीचे ट्रैवर्सल की एक लघुगणकीय संख्या होगी। इस प्रकार, एक टर्नरी सर्च ट्री में बहुत बड़ी स्ट्रिंग्स की एक छोटी संख्या पर स्ट्रिंग्स की लंबाई रनटाइम पर हावी हो सकती है।<ref name="sedgewick">{{cite web|last1=Bentley|last2=Sedgewick |first1=Jon|first2=Bob|title=टर्नेरी सर्च ट्री|url=https://www.cs.upc.edu/~ps/downloads/tst/tst.html}}</ref>
टर्नरी सर्च ट्री संचालन के लिए समय जटिलताएँ:<ref name="dobbs" />
टर्नरी सर्च ट्री संचालन के लिए समय जटिलताएँ:<ref name="dobbs" />


Line 180: Line 181:
* किसी भी समय ट्राई का उपयोग किया जा सकता है किन्तु कम मेमोरी खपत वाली संरचना को प्राथमिकता दी जाती है।<ref name ="dobbs" />* अन्य डेटा के लिए [[डेटा मैपिंग]] स्ट्रिंग के लिए एक त्वरित और स्थान-बचत डेटा संरचना।<ref name="wrobel" />* स्वतः पूर्णता लागू करने के लिए।<ref name="ostrov">{{cite web |last1=Ostrovsky |first1=Igor |title=टर्नरी सर्च ट्री के साथ कुशल स्वतः पूर्ण|url=http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/}}</ref>
* किसी भी समय ट्राई का उपयोग किया जा सकता है किन्तु कम मेमोरी खपत वाली संरचना को प्राथमिकता दी जाती है।<ref name ="dobbs" />* अन्य डेटा के लिए [[डेटा मैपिंग]] स्ट्रिंग के लिए एक त्वरित और स्थान-बचत डेटा संरचना।<ref name="wrobel" />* स्वतः पूर्णता लागू करने के लिए।<ref name="ostrov">{{cite web |last1=Ostrovsky |first1=Igor |title=टर्नरी सर्च ट्री के साथ कुशल स्वतः पूर्ण|url=http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/}}</ref>
* वर्तनी जाँच के रूप में।<ref name=wally>{{cite web |last1=Flint |first1=Wally |date=2001-02-16 |df=mdy |url=https://www.infoworld.com/article/2075027/plant-your-data-in-a-ternary-search-tree.html |title=अपने डेटा को टर्नरी सर्च ट्री में रोपित करें|work=[[JavaWorld]] |access-date=2020-07-19}}</ref>
* वर्तनी जाँच के रूप में।<ref name=wally>{{cite web |last1=Flint |first1=Wally |date=2001-02-16 |df=mdy |url=https://www.infoworld.com/article/2075027/plant-your-data-in-a-ternary-search-tree.html |title=अपने डेटा को टर्नरी सर्च ट्री में रोपित करें|work=[[JavaWorld]] |access-date=2020-07-19}}</ref>
* निकटतम पड़ोसी खोज|निकट-पड़ोसी खोज (जिसमें वर्तनी-जांच एक विशेष मामला है)।<ref name ="dobbs" />* एक [[डेटाबेस]] के रूप में, विशेष रूप से जब कई गैर-कुंजी फ़ील्ड द्वारा अनुक्रमण वांछनीय है।<ref name="wally" />* [[ हैश तालिका ]] के स्थान पर.<ref name="wally" />
* निकटतम पड़ोसी सर्च|निकट-पड़ोसी सर्च (जिसमें वर्तनी-जांच एक विशेष मामला है)।<ref name ="dobbs" />* एक [[डेटाबेस]] के रूप में, विशेष रूप से जब कई गैर-कुंजी फ़ील्ड द्वारा अनुक्रमण वांछनीय है।<ref name="wally" />* [[ हैश तालिका ]] के स्थान पर.<ref name="wally" />


== यह भी देखें ==
== यह भी देखें ==

Revision as of 18:42, 15 July 2023

Not to be confused with बाइनरी ट्री.
Ternary Search Tree (TST)
Typetree
Time complexity in big O notation
Algorithm Average Worst case
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

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

विवरण

टर्नरी सर्च ट्री का प्रत्येक नोड एकल कैरेक्टर (कला), ऑब्जेक्ट (या कार्यान्वयन के आधार पर किसी ऑब्जेक्ट के लिए पॉइंटर (कंप्यूटर प्रोग्रामिंग)) को संग्रहीत करता है, और इसके तीन चाइल्ड के लिए पॉइंटर्स को पारंपरिक रूप से समान किड, लो किड और हाय किड नाम दिया गया है, जिन्हें क्रमशः मध्य (चाइल्ड), निचला (चाइल्ड) और उच्चतर (चाइल्ड) भी कहा जा सकता है।[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. ↑ 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. ↑ 2.0 2.1 Ostrovsky, Igor. "टर्नरी सर्च ट्री के साथ कुशल स्वतः पूर्ण".
  3. ↑ 3.0 3.1 Wrobel, Lukasz. "टर्नेरी सर्च ट्री".
  4. ↑ Bentley, Jon; Sedgewick, Bob. "टर्नेरी सर्च ट्री".
  5. ↑ 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
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टर्नरी_सर्च_ट्री&oldid=234495’