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

From Vigyanwiki
No edit summary
m (Abhishekkshukla moved page टर्नरी खोज वृक्ष to टर्नरी सर्च ट्री without leaving a redirect)
 
(19 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{distinguish|बाइनरी ट्री}}
{{distinguish|बाइनरी ट्री}}[[कंप्यूटर विज्ञान]] में, '''टर्नरी सर्च ट्री''' [[ प्रयास करें |ट्राइ]] का प्रकार है (जिसे कभी-कभी प्रीफिक्स ट्री भी कहा जाता है) जहां नोड्स को [[बाइनरी सर्च ट्री]] के समान विधि द्वारा व्यवस्थित किया जाता है, किन्तु बाइनरी ट्री दो की सीमा के अतिरिक्त तीन चाइल्ड तक होता है। अन्य प्रीफिक्स ट्री की भाँति, टर्नरी सर्च ट्री का उपयोग इंक्रीमेंटल [[स्ट्रिंग खोज|स्ट्रिंग सर्च]] की क्षमता के साथ [[सहयोगी मानचित्र|अस्सोसिएटिव मैप]] स्ट्रक्चर के रूप में किया जा सकता है। यद्यपि, स्पीड की कॉस्ट पर, टर्नरी सर्च ट्री स्टैण्डर्ड प्रीफिक्स ट्री की अपेक्षा में अधिक स्पेस एफिशिएंट होते हैं। टर्नरी सर्च ट्री के सामान्य ऍप्लिकेशन्स में स्पेल-चेकिंग और ऑटो-कम्पलीशन सम्मिलित होता है।
{{Infobox data structure
|name=Ternary Search Tree (TST)
|type=tree
|search_avg= O(log ''n'')
|search_worst= O(''n'')
|insert_avg= O(log ''n'')
|insert_worst= O(''n'')
|delete_avg= O(log ''n'')
|delete_worst= O(''n'')
}}
 
[[कंप्यूटर विज्ञान]] में, टर्नरी सर्च ट्री [[ प्रयास करें |ट्राइ]] का प्रकार है (जिसे कभी-कभी ''प्रीफिक्स ट्री'' भी कहा जाता है) जहां नोड्स को [[बाइनरी सर्च ट्री]] के समान विधि द्वारा व्यवस्थित किया जाता है, किन्तु बाइनरी ट्री दो की सीमा के अतिरिक्त तीन बच्चों तक होता है। अन्य प्रीफिक्स ट्री की भाँति, टर्नरी सर्च ट्री का उपयोग वृद्धिशील [[स्ट्रिंग खोज|स्ट्रिंग सर्च]] की क्षमता के साथ [[सहयोगी मानचित्र]] संरचना के रूप में किया जा सकता है। यद्यपि, गति के मूल्य पर, टर्नरी सर्च ट्री मानक प्रीफिक्स ट्री की तुलना में अधिक स्थान कुशल हैं। टर्नरी सर्च ट्री के सामान्य अनुप्रयोगों में वर्तनी-अन्वेषण और स्वत: पूर्णता सम्मिलित है।


==विवरण==
==विवरण==
टर्नरी सर्च ट्री का प्रत्येक नोड एकल वर्ण (कला), ऑब्जेक्ट (या कार्यान्वयन के आधार पर किसी ऑब्जेक्ट के लिए [[ सूचक (कंप्यूटर प्रोग्रामिंग) |पॉइंटर (कंप्यूटर प्रोग्रामिंग)]]) को संग्रहीत करता है, और इसके तीन बच्चों के लिए पॉइंटर्स को पारंपरिक रूप से समान किड, लो किड और हाय किड नाम दिया गया है, जिन्हें क्रमशः मध्य (बच्चा), निचला (बच्चा) और उच्चतर (बच्चा) भी कहा जा सकता है।<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
         / | \
         / | \
         ए यू एच
         a  u  h
         | | | \
         | | | \
         टी टी ई यू
         t t e  u
       / / | / |
       / / | / |
     एस पी ई आई एस
     s p  e i s
 
अन्य ट्राई डेटा संरचनाओं की भाँति, टर्नरी सर्च ट्री में प्रत्येक नोड संग्रहीत स्ट्रिंग्स के उपसर्ग का प्रतिनिधित्व करता है। किसी नोड के मध्य सबट्री में सभी स्ट्रिंग उस उपसर्ग से प्रारम्भ होते हैं।
 
==ऑपरेशन्स==


अन्य ट्राई डेटा संरचनाओं की तरह, टर्नरी सर्च ट्री में प्रत्येक नोड संग्रहीत स्ट्रिंग्स के उपसर्ग का प्रतिनिधित्व करता है। किसी नोड के मध्य उपट्री में सभी तार उस उपसर्ग से शुरू होते हैं।
===इंसर्शन===


==संचालन==
टर्नरी सर्च में मान इन्सर्ट करने को लुकअप परिभाषित करने के समान ही रिकर्सिव या पुनरावृत्त रूप से परिभाषित किया जा सकता है। इस रिकर्सिव विधि को कुंजी दिए जाने पर ट्री के नोड्स पर निरंतर कॉल किया जाता है जो कुंजी के सामने से कैरेक्टरों को विभक्त करने पर उत्तरोत्तर छोटा होता जाता है। यदि यह विधि किसी ऐसे नोड तक पहुँचती है जो नहीं बनाया गया है, तो यह नोड बनाता है और उसे कुंजी में प्रथम कैरेक्टर का कैरेक्टर मान निर्दिष्ट करता है। कोई नया नोड बनाया गया है या नहीं, विधि यह देखने के लिए जांच करती है कि स्ट्रिंग में प्रथम कैरेक्टर नोड में कैरेक्टर मान से अधिक है या कम है और लुकअप ऑपरेशन के अनुसार उपयुक्त नोड पर रिकर्सिव कॉल करता है। यद्यपि, यदि कुंजी का प्रथम कैरेक्टर नोड के मान के समान है तो सम्मिलन प्रक्रिया को समान किड पर कॉल किया जाता है और कुंजी का प्रथम कैरेक्टर कम कर दिया जाता है।<ref name="dobbs" /> बाइनरी सर्च ट्री और अन्य डेटा संरचनाओं की भाँति, टर्नरी सर्च ट्री कुंजियों के क्रम के आधार पर पतित हो सकते हैं।<ref name=wrobel>{{cite web|last=Wrobel|first=Lukasz|title=टर्नेरी सर्च ट्री|url=http://lukaszwrobel.pl/blog/ternary-search-tree}}</ref> वर्णानुक्रम में इन्सर्टिंग कुंजियाँ निकृष्ट संभावित ट्री को प्राप्त करने की विधि है।<ref name="dobbs" /> कुंजियों को यादृच्छिक क्रम में इन्सर्ट करने पर अधिकांशतः उचित प्रकार से संतुलित ट्री बनता है।<ref name="dobbs" />
  function insertion(string key) is


===सम्मिलन===
node p:= root
    //initialized to be equal in case root is null
node last:= root
int idx:= 0
while p is not null do
        //recurse on proper subtree
if key[idx] < p.splitchar then
last:= p
p:= p.left
else if key[idx] > p.splitchar then
last:= p
p:= p.right
else:
            // key is already in our Tree
if idx == length(key) then
return
            //trim character from our key
idx:= idx+1
last:= p
p:= p.mid
p:= node()
    //add p in as a child of the last non-null node (or root if root is null)
    if root == null then
        root:= p
else if last.splitchar < key[idx] then
last.right:= p
else if last.splitchar > key[idx] then
last.left:= p
else
last.mid:= p
p.splitchar:= key[idx]idx:= idx+1


टर्नरी खोज में एक मान डालने को लुकअप को परिभाषित करने के समान ही पुनरावर्ती या पुनरावृत्त रूप से परिभाषित किया जा सकता है। इस पुनरावर्ती विधि को एक कुंजी दिए जाने पर पेड़ के नोड्स पर लगातार बुलाया जाता है जो कुंजी के सामने से वर्णों को काटकर उत्तरोत्तर छोटा होता जाता है। यदि यह विधि किसी ऐसे नोड तक पहुँचती है जो नहीं बनाया गया है, तो यह नोड बनाता है और उसे कुंजी में पहले वर्ण का वर्ण मान निर्दिष्ट करता है। कोई नया नोड बनाया गया है या नहीं, विधि यह देखने के लिए जांच करती है कि स्ट्रिंग में पहला वर्ण नोड में वर्ण मान से अधिक है या कम है और लुकअप ऑपरेशन के अनुसार उपयुक्त नोड पर एक पुनरावर्ती कॉल करता है। यद्यपि, यदि कुंजी का पहला अक्षर नोड के मान के बराबर है तो सम्मिलन प्रक्रिया को बराबर बच्चे पर बुलाया जाता है और कुंजी का पहला अक्षर हटा दिया जाता है।<ref name="dobbs" />  बाइनरी सर्च ट्री और अन्य डेटा संरचनाओं की तरह, टर्नरी सर्च ट्री कुंजियों के क्रम के आधार पर खराब हो सकते हैं।<ref name=wrobel>{{cite web|last=Wrobel|first=Lukasz|title=टर्नेरी सर्च ट्री|url=http://lukaszwrobel.pl/blog/ternary-search-tree}}</ref> वर्णानुक्रम में कुंजियाँ डालना सबसे खराब संभावित ख़राब पेड़ को प्राप्त करने का एक तरीका है।<ref name="dobbs" />कुंजियों को यादृच्छिक क्रम में डालने से अक्सर एक अच्छी तरह से संतुलित पेड़ बनता है।<ref name="dobbs" /><सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
    // Insert remainder of key
फ़ंक्शन इंसर्शन (स्ट्रिंग कुंजी) है
while idx < length(key) do
नोड पी= रूट
p.mid:= node()
    //रूट शून्य होने की स्थिति में बराबर होने के लिए आरंभ किया गया
        p.mid.splitchar:= key[idx]
नोड अंतिम= रूट
idx += 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
</सिंटैक्सहाइलाइट>


=== खोजें ===
=== सर्च ===


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


'''स्यूडोकोड'''
'''स्यूडोकोड'''
 
  function search(string query) is
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
     function search(string query) is
  फ़ंक्शन खोज (स्ट्रिंग क्वेरी) है
         return false
     यदि is_empty(क्वेरी) है तो
         विवरण झूठा है
   
   
     नोड पी:= रूट
     node p= root
     पूर्णांक आईडीएक्स:= 0
     int idx= 0
   
   
    जबकि p शून्य नहीं है
      while p is not null do
         यदि क्वेरी[idx] <p.splitchar तो
         if query[idx] < p.splitchar then
             पी:= पी.बाएं
             p= p.left
         अन्यथा यदि query[idx] > p.splitchar तो
         else if query[idx] > p.splitchar then
             पी:= पी.सही;
             p= p.right;
         अन्य
         else
             यदि idx = लंबाई(क्वेरी) तो
             if idx = length(query) then
                 सच लौटें
                 return true
             आईडीएक्स:= आईडीएक्स + 1
             idx= idx + 1
             पी:= पी.मध्य
             p= p.mid
   
   
     विवरण झूठा है
     return false
</सिंटैक्सहाइलाइट>
=== डिलीशन ===


=== विलोपन ===
डिलीट ऑपरेशन में सर्च ट्री में कुंजी स्ट्रिंग को सर्च करना और नोड को फाइंड करना सम्मिलित है, जिसे नीचे सुडो कोड में फर्स्टमिड कहा जाता है, जिस प्रकार कुंजी स्ट्रिंग के लिए सर्च पाथ के फर्स्टमिड के मध्य चाइल्ड से अंत तक के पाथ में कोई बाएँ या दाएँ चाइल्ड नहीं है। यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पाथ नहीं है, तो इसका अर्थ है कि कुंजी स्ट्रिंग या तो पूर्ण रूप से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, अथवा सर्च ट्री में नहीं है। कई कार्यान्वयन केवल पश्चात की स्थिति को सुनिश्चित करने के लिए स्ट्रिंग कैरेक्टर के अंत का उपयोग करते हैं। तत्पश्चात पाथ को फर्स्टमिड.मिड से सर्च पाथ के अंत तक डिलीट कर दिया जाता है। इस स्थिति में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग ट्री में अंतिम स्ट्रिंग होनी चाहिए, और इस प्रकार रूट को डिलीट करने के पश्चात शून्य पर सेट किया जाता है।
 
  function delete(string key) is
डिलीट ऑपरेशन में सर्च ट्री में एक कुंजी स्ट्रिंग की खोज करना और एक नोड ढूंढना सम्मिलित है, जिसे नीचे छद्म कोड में फर्स्टमिड कहा जाता है, जैसे कि फर्स्टमिड के मध्य चाइल्ड से लेकर कुंजी स्ट्रिंग के लिए खोज पथ के अंत तक का कोई रास्ता नहीं है। या सही बच्चे. यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में एक अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पथ नहीं है, तो इसका मतलब है कि कुंजी स्ट्रिंग या तो पूरी तरह से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, या खोज ट्री में नहीं है। कई कार्यान्वयन केवल बाद वाले मामले को सुनिश्चित करने के लिए स्ट्रिंग वर्ण के अंत का उपयोग करते हैं। फिर पथ को फर्स्टमिड.मिड से खोज पथ के अंत तक हटा दिया जाता है। इस मामले में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग पेड़ में आखिरी स्ट्रिंग रही होगी, और इस प्रकार रूट को हटाने के बाद शून्य पर सेट किया गया है।
     if is_empty(key) then
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
         return
  फ़ंक्शन डिलीट (स्ट्रिंग कुंजी) है
     यदि is_empty(key) है तो
         वापस करना
   
   
     नोड पी:= रूट
     node p= root
     पूर्णांक आईडीएक्स:= 0
     int idx= 0


  नोड फर्स्टमिड:= शून्य
  node firstMid= null
     जबकि p शून्य नहीं है
     while p is not null do
         यदि key[idx] < p.splitchar तो
         if key[idx] < p.splitchar then
             फर्स्टमिड:= शून्य
             firstMid= null
             पी:= पी.बाएं
             p= p.left
        अन्यथा यदि key[idx] > p.splitchar तो
          else if key[idx] > p.splitchar then
             फर्स्टमिड:= शून्य
             firstMid= null
             पी:= पी.सही
             p= p.right
         अन्य
         else
             फर्स्टमिड:= पी
             firstMid= p
             जबकि p शून्य नहीं है और key[idx] == p.splitchar करते हैं
             while p is not null and key[idx] == p.splitchar do
             आईडीएक्स:= आईडीएक्स + 1
             idx= idx + 1
             पी:= पी.मध्य
             p= p.mid
              
              
     यदि फर्स्टमिड == शून्य है तो
     if firstMid == null then
         वापसी // कोई अद्वितीय स्ट्रिंग प्रत्यय नहीं
         return  // No unique string suffix


     // इस बिंदु पर, फर्स्टमिड स्ट्रिंग अद्वितीय प्रत्यय होने से पहले नोड को इंगित करता है
     // At this point, firstMid points to the node before the strings unique suffix occurs
     नोड q:= फर्स्टमिड.मिड
     node q= firstMid.mid
     नोड पी:= क्यू
     node p= q
     फर्स्टमिड.मिड:= शून्य // पेड़ से प्रत्यय को डिस्कनेक्ट करें
     firstMid.mid= null // disconnect suffix from tree
     जबकि q शून्य नहीं है //प्रत्यय पथ पर चलें और नोड्स हटा दें
     while q is not null do //walk down suffix path and delete nodes
         पी:= क्यू
         p= q
         q:= q.मध्य
         q= q.mid
         डिलीट(पी) // नोड पी से जुड़ी मुफ्त मेमोरी
         delete(p) // free memory associated with node p
     यदि फर्स्टमिड == रूट है तो
     if firstMid == root then
         डिलीट(रूट) // पूरे पेड़ को हटा दें
         delete(root)       //delete the entire tree
         जड़:= शून्य
         root= null
</सिंटैक्सहाइलाइट>
=== ट्रैवर्सल ===


=== ट्रैवर्सल ===
=== पार्शियल-मैच सर्चिंग ===


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


=== निकट-पड़ोसी खोज रहा है ===
==रनिंग टाइम==
टर्नरी सर्च ट्री का रनिंग टाइम इनपुट के साथ अधिक भिन्न होता है। जब कई समान स्ट्रिंग दी जाती हैं तो टर्नरी सर्च ट्री उचित प्रकार से रन करते हैं, अधिकांशतः जब वे स्ट्रिंग सामान्य उपसर्ग की भागीदारी करते हैं। वैकल्पिक रूप से, बड़ी संख्या में अपेक्षाकृत छोटी स्ट्रिंग्स (जैसे शब्दकोश में शब्द) को संग्रहीत करते समय टर्नरी सर्च ट्री प्रभावी होते हैं।<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" />


{| class="wikitable"
{| class="wikitable"
|-
|-
!  !! Average-case running time !! Worst-case running time
!  !! एवरेज-केस रनिंग टाइम !! वर्स्ट केस रनिंग टाइम
|-
|-
| Lookup || ''O''(log ''n'' + ''k'') || ''O''(''n''  + ''k'')
| लुकउप || ''O''(log ''n'' + ''k'') || ''O''(''n''  + ''k'')
|-
|-
| Insertion || ''O''(log ''n''  + ''k'') || ''O''(''n''  + ''k'')
| इंसर्शन || ''O''(log ''n''  + ''k'') || ''O''(''n''  + ''k'')
|-
|-
| Delete || ''O''(log ''n''  + ''k'') || ''O''(''n''  + ''k'')
| डिलीट || ''O''(log ''n''  + ''k'') || ''O''(''n''  + ''k'')
|}
|}


== अन्य डेटा संरचनाओं से तुलना ==
== अन्य डेटा स्ट्रक्चर्स से कम्पेरिज़न ==


===प्रयास===
===ट्राइज===
अन्य प्रयासों की तुलना में धीमे होने के बावजूद, टर्नरी सर्च ट्री अपनी स्थान-दक्षता के कारण बड़े डेटा सेट के लिए बेहतर अनुकूल हो सकते हैं।<ref name="dobbs" />
अन्य प्रीफिक्स ट्रीज की अपेक्षा में मंद होने पर भी, टर्नरी सर्च ट्री अपनी स्थान-दक्षता के कारण बड़े डेटा सेट के लिए श्रेष्ठ अनुकूल हो सकते हैं।<ref name="dobbs" />


'''हैश मानचित्र'''
'''हैश मैप'''


स्ट्रिंग्स को मानों में मैप करने के लिए टर्नरी सर्च ट्री के स्थान पर [[ हैश तालिका ]]्स का भी उपयोग किया जा सकता है। यद्यपि, हैश मानचित्र भी अक्सर टर्नरी सर्च ट्री की तुलना में अधिक मेमोरी का उपयोग करते हैं (किन्तु उतना नहीं जितना प्रयास किया जाता है)। इसके अतिरिक्त, हैश मैप आमतौर पर एक स्ट्रिंग की रिपोर्ट करने में धीमे होते हैं जो समान डेटा संरचना में नहीं है, क्योंकि इसमें केवल पहले कुछ वर्णों की तुलना में पूरी स्ट्रिंग की तुलना करनी होगी। ऐसे कुछ सबूत हैं जो टर्नरी सर्च ट्री को हैश मैप की तुलना में तेजी से चलते हुए दिखाते हैं।<ref name="dobbs" />इसके अतिरिक्त, हैश मानचित्र टर्नरी सर्च ट्रीों के कई उपयोगों की अनुमति नहीं देते हैं, जैसे कि निकट-पड़ोसी लुकअप।
स्ट्रिंग्स को मानों में मैप करने के लिए टर्नरी सर्च ट्री के स्थान पर [[ हैश तालिका |हैश तालिका]] का भी उपयोग किया जा सकता है। यद्यपि, हैश मानचित्र भी अधिकांशतः टर्नरी सर्च ट्री की अपेक्षा में अधिक मेमोरी का उपयोग करते हैं (किन्तु उतना नहीं जितना प्रयास किया जाता है)। इसके अतिरिक्त, हैश मैप सामान्यतः स्ट्रिंग की रिपोर्ट करने में मंद होते हैं जो समान डेटा स्ट्रक्चर में नहीं है, क्योंकि इसमें केवल प्रथम कुछ कैरेक्टर्स की अपेक्षा में पूर्ण स्ट्रिंग की अपेक्षा करनी होगी। ऐसे कुछ प्रमाण हैं जो टर्नरी सर्च ट्री को हैश मैप की अपेक्षा में तीव्रता से रन करते हुए दिखाते हैं।<ref name="dobbs" /> इसके अतिरिक्त, हैश मैप टर्नरी सर्च ट्री के कई उपयोगों जैसे नियर-नेबर लुकअप की अनुमति प्रदान नहीं करते हैं।


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


==उपयोग==
==उपयोग==
टर्नरी सर्च ट्री का उपयोग कई समस्याओं को हल करने के लिए किया जा सकता है जिसमें बड़ी संख्या में स्ट्रिंग्स को मनमाने क्रम में संग्रहीत और पुनर्प्राप्त किया जाना चाहिए। इनमें से कुछ सबसे आम या सबसे उपयोगी नीचे हैं:
टर्नरी सर्च ट्री का उपयोग कई प्रोब्लेम्स को सॉल्व करने के लिए किया जा सकता है जिसमें बड़ी संख्या में स्ट्रिंग्स को आरबिटरेरी आर्डर में स्टोर और रिट्रीव किया जाना चाहिए। इनमें से कुछ सबसे सामान्य या सबसे उपयोगी नीचे हैं:
 
* किसी भी समय ट्राई का उपयोग किया जा सकता है किन्तु कम मेमोरी खपत वाली संरचना को प्राथमिकता दी जाती है।<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 ="dobbs" />* एक [[डेटाबेस]] के रूप में, विशेष रूप से जब कई गैर-कुंजी फ़ील्ड द्वारा अनुक्रमण वांछनीय है।<ref name="wally" />* [[ हैश तालिका ]] के स्थान पर.<ref name="wally" />


* किसी भी समय ट्राई का उपयोग किया जा सकता है किन्तु लेस्स मेमोरी-कोन्सुमिंग स्ट्रक्चर को प्राथमिकता दी जाती है।<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="dobbs" />
*[[डेटाबेस]] के रूप में, विशेष रूप से जब कई नॉन-की फ़ील्ड द्वारा इंडेक्सिंग वांछनीय है।<ref name="wally" />
*[[ हैश तालिका |हैश टेबल]] के स्थान पर उपयोग किया जाता है।<ref name="wally" />
== यह भी देखें ==
== यह भी देखें ==
* [[थ्री-वे रेडिक्स क्विकसॉर्ट]]
* [[थ्री-वे रेडिक्स क्विकसॉर्ट]]
* प्रयास करें
* ट्राइ
* बाइनरी सर्च ट्री
* बाइनरी सर्च ट्री
* हैश तालिका
* हैश टेबल
 
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
==बाहरी संबंध==
==बाहरी संबंध==
* [http://www.cs.princeton.edu/~rs/strings/ Ternary Search Trees ] page with papers (by Jon Bentley and Robert Sedgewick) about ternary search trees and algorithms for "sorting and searching strings"
* [http://www.cs.princeton.edu/~rs/strings/ Ternary Search Trees ] page with papers (by Jon Bentley and Robert Sedgewick) about ternary search trees and algorithms for "sorting and searching strings"
Line 196: Line 177:
* [http://algs4.cs.princeton.edu/52trie/TST.java.html TST.java.html] Implementation in Java of a TST by Robert Sedgewick and Kevin Wayne
* [http://algs4.cs.princeton.edu/52trie/TST.java.html TST.java.html] Implementation in Java of a TST by Robert Sedgewick and Kevin Wayne


{{CS-Trees}}
[[Category:Articles with hatnote templates targeting a nonexistent page]]
{{Strings |state=collapsed}}
[[Category:Collapse templates]]
[[Category: पेड़ (डेटा संरचनाएं)]] [[Category: एल्गोरिदम खोजें]]
 
 
 
[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:एल्गोरिदम खोजें]]
[[Category:पेड़ (डेटा संरचनाएं)]]

Latest revision as of 12:18, 1 November 2023

Not to be confused with बाइनरी ट्री.

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

विवरण

टर्नरी सर्च ट्री का प्रत्येक नोड एकल कैरेक्टर (कला), ऑब्जेक्ट (या कार्यान्वयन के आधार पर किसी ऑब्जेक्ट के लिए पॉइंटर (कंप्यूटर प्रोग्रामिंग)) को संग्रहीत करता है, और इसके तीन चाइल्ड के लिए पॉइंटर्स को पारंपरिक रूप से समान किड, लो किड और हाय किड नाम दिया गया है, जिन्हें क्रमशः मध्य (चाइल्ड), निचला (चाइल्ड) और उच्चतर (चाइल्ड) भी कहा जा सकता है।[1] नोड में अपने मूल नोड के लिए पॉइंटर के साथ इंडिकेटर भी हो सकता है कि नोड किसी शब्द के अंत को चिह्नित करता है या नहीं करता है।[2] लो किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर मान वर्तमान नोड से कम है। हाय किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर वर्तमान नोड से बड़ा है।[1] समान किड शब्द में अग्र कैरेक्टर की ओर संकेत करता है। नीचे दिया गया चित्र क्यूट, कप, एट, एज़, ही, यूएस और आई स्ट्रिंग के साथ टर्नरी सर्च ट्री दिखाता है: 

          c
        / | \
       a  u  h
       | | | \
       t t e  u
     / / | / |
    s p  e i s

अन्य ट्राई डेटा संरचनाओं की भाँति, टर्नरी सर्च ट्री में प्रत्येक नोड संग्रहीत स्ट्रिंग्स के उपसर्ग का प्रतिनिधित्व करता है। किसी नोड के मध्य सबट्री में सभी स्ट्रिंग उस उपसर्ग से प्रारम्भ होते हैं।

ऑपरेशन्स

इंसर्शन

टर्नरी सर्च में मान इन्सर्ट करने को लुकअप परिभाषित करने के समान ही रिकर्सिव या पुनरावृत्त रूप से परिभाषित किया जा सकता है। इस रिकर्सिव विधि को कुंजी दिए जाने पर ट्री के नोड्स पर निरंतर कॉल किया जाता है जो कुंजी के सामने से कैरेक्टरों को विभक्त करने पर उत्तरोत्तर छोटा होता जाता है। यदि यह विधि किसी ऐसे नोड तक पहुँचती है जो नहीं बनाया गया है, तो यह नोड बनाता है और उसे कुंजी में प्रथम कैरेक्टर का कैरेक्टर मान निर्दिष्ट करता है। कोई नया नोड बनाया गया है या नहीं, विधि यह देखने के लिए जांच करती है कि स्ट्रिंग में प्रथम कैरेक्टर नोड में कैरेक्टर मान से अधिक है या कम है और लुकअप ऑपरेशन के अनुसार उपयुक्त नोड पर रिकर्सिव कॉल करता है। यद्यपि, यदि कुंजी का प्रथम कैरेक्टर नोड के मान के समान है तो सम्मिलन प्रक्रिया को समान किड पर कॉल किया जाता है और कुंजी का प्रथम कैरेक्टर कम कर दिया जाता है।[1] बाइनरी सर्च ट्री और अन्य डेटा संरचनाओं की भाँति, टर्नरी सर्च ट्री कुंजियों के क्रम के आधार पर पतित हो सकते हैं।[3] वर्णानुक्रम में इन्सर्टिंग कुंजियाँ निकृष्ट संभावित ट्री को प्राप्त करने की विधि है।[1] कुंजियों को यादृच्छिक क्रम में इन्सर्ट करने पर अधिकांशतः उचित प्रकार से संतुलित ट्री बनता है।[1] 

  function insertion(string key) is

	node p:= root 
    //initialized to be equal in case root is null
	node last:= root
	int idx:= 0
	while p is not null do
        //recurse on proper subtree
		if key[idx] < p.splitchar then
			last:= p
			p:= p.left
		else if key[idx] > p.splitchar then
			last:= p
			p:= p.right
		else:
            // key is already in our Tree
			if idx == length(key) then
				return 
            //trim character from our key 
			idx:= idx+1
			last:= p
			p:= p.mid
	p:= node()
    //add p in as a child of the last non-null node (or root if root is null)
    if root == null then
        root:= p
	else if last.splitchar < key[idx] then
		last.right:= p
	else if last.splitchar > key[idx] then
		last.left:= p
	else 
		last.mid:= p
	p.splitchar:= key[idx]idx:= idx+1

    // Insert remainder of key
	while idx < length(key) do
		p.mid:= node()
        p.mid.splitchar:= key[idx]
		idx += 1

सर्च

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

स्यूडोकोड 

function search(string query) is
    function search(string query) is
        return false

    node p= root
    int idx= 0

     while p is not null do
        if query[idx] < p.splitchar then
            p= p.left
        else if query[idx] > p.splitchar then
            p= p.right;
        else
            if idx = length(query) then
                return true
            idx= idx + 1
            p= p.mid

    return false

डिलीशन

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

function delete(string key) is
    if is_empty(key) then
        return 

    node p= root
    int idx= 0

node firstMid= null
    while p is not null do
        if key[idx] < p.splitchar then
            firstMid= null
            p= p.left
         else if key[idx] > p.splitchar then
            firstMid= null
            p= p.right
        else
            firstMid= p
            while p is not null and key[idx] == p.splitchar do
            idx= idx + 1
            p= p.mid
            
    if firstMid == null then
        return  // No unique string suffix

    // At this point, firstMid points to the node before the strings unique suffix occurs
    node q= firstMid.mid
    node p= q
    firstMid.mid= null // disconnect suffix from tree
    while q is not null do //walk down suffix path and delete nodes 
        p= q
        q= q.mid
        delete(p)			// free memory associated with node p
    if firstMid == root then
        delete(root)       //delete the entire tree
        root= null

ट्रैवर्सल

पार्शियल-मैच सर्चिंग

नियर-नेबर सर्चिंग

रनिंग टाइम

टर्नरी सर्च ट्री का रनिंग टाइम इनपुट के साथ अधिक भिन्न होता है। जब कई समान स्ट्रिंग दी जाती हैं तो टर्नरी सर्च ट्री उचित प्रकार से रन करते हैं, अधिकांशतः जब वे स्ट्रिंग सामान्य उपसर्ग की भागीदारी करते हैं। वैकल्पिक रूप से, बड़ी संख्या में अपेक्षाकृत छोटी स्ट्रिंग्स (जैसे शब्दकोश में शब्द) को संग्रहीत करते समय टर्नरी सर्च ट्री प्रभावी होते हैं।[1] टर्नरी सर्च ट्री के लिए रनिंग टाइम बाइनरी सर्च ट्री के समान होता है, जिसमें वे सामान्यतः लॉगरिदमिक समय में रन करते हैं, किन्तु विकृत (सबसे विकृत) स्थिति में रैखिक समय में रन कर सकते हैं। इसके अतिरिक्त, रनटाइम पर विचार करते समय स्ट्रिंग्स के आकार को भी ध्यान में रखा जाना चाहिए। उदाहरण के लिए, लंबाई k की स्ट्रिंग के लिए सर्च पाथ में, ट्री में मध्य चाइल्ड के नीचे k ट्रैवर्सल होंगे, साथ ही ट्री में बाएं और दाएं चाइल्ड के नीचे ट्रैवर्सल की लघुगणकीय संख्या होगी। इस प्रकार, टर्नरी सर्च ट्री में अत्यंत बड़ी स्ट्रिंग्स की छोटी संख्या पर स्ट्रिंग्स की लंबाई रनटाइम पर श्रेष्ठ हो सकती है।[4]

टर्नरी सर्च ट्री संचालन के लिए समय जटिलताएँ:[1]

एवरेज-केस रनिंग टाइम वर्स्ट केस रनिंग टाइम
लुकउप O(log n + k) O(n + k)
इंसर्शन O(log n + k) O(n + k)
डिलीट 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=272046’