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

From Vigyanwiki
No edit summary
m (Abhishekkshukla moved page टर्नरी खोज वृक्ष to टर्नरी सर्च ट्री without leaving a redirect)
 
(9 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'')
}}
 
[[कंप्यूटर विज्ञान]] में, टर्नरी सर्च ट्री [[ प्रयास करें |ट्राइ]] का प्रकार है (जिसे कभी-कभी ''प्रीफिक्स ट्री'' भी कहा जाता है) जहां नोड्स को [[बाइनरी सर्च ट्री]] के समान विधि द्वारा व्यवस्थित किया जाता है, किन्तु बाइनरी ट्री दो की सीमा के अतिरिक्त तीन चाइल्ड तक होता है। अन्य प्रीफिक्स ट्री की भाँति, टर्नरी सर्च ट्री का उपयोग वृद्धिशील [[स्ट्रिंग खोज|स्ट्रिंग सर्च]] की क्षमता के साथ [[सहयोगी मानचित्र]] संरचना के रूप में किया जा सकता है। यद्यपि, गति के मूल्य पर, टर्नरी सर्च ट्री मानक प्रीफिक्स ट्री की तुलना में अधिक स्थान कुशल हैं। टर्नरी सर्च ट्री के सामान्य अनुप्रयोगों में वर्तनी-अन्वेषण और स्वत: पूर्णता सम्मिलित है।


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


==संचालन==
==ऑपरेशन्स==


===इंसर्शन===
===इंसर्शन===


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


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


        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
     // Insert remainder of key
while idx < length(key) do
while idx < length(key) do
 
p.mid:= node()
p.mid := node()
        p.mid.splitchar:= key[idx]
 
idx += 1
p.mid.splitchar := key[idx]


idx += 1
=== सर्च ===
=== सर्च ===


Line 103: Line 68:
         return false
         return false
   
   
     node p := root
     node p= root
     int idx := 0
     int idx= 0
   
   
       while p is not null do
       while p is not null do
         if query[idx] < p.splitchar then
         if query[idx] < p.splitchar then
             p := p.left
             p= p.left
         else if query[idx] > p.splitchar then
         else if query[idx] > p.splitchar then
             p := p.right;
             p= p.right;
         else
         else
             if idx = length(query) then
             if idx = length(query) then
                 return true
                 return true
             idx := idx + 1
             idx= idx + 1
             p := p.mid
             p= p.mid
   
   
     return false
     return false
Line 121: Line 86:


डिलीट ऑपरेशन में सर्च ट्री में कुंजी स्ट्रिंग को सर्च करना और नोड को फाइंड करना सम्मिलित है, जिसे नीचे सुडो कोड में फर्स्टमिड कहा जाता है, जिस प्रकार कुंजी स्ट्रिंग के लिए सर्च पाथ के फर्स्टमिड के मध्य चाइल्ड से अंत तक के पाथ में कोई बाएँ या दाएँ चाइल्ड नहीं है। यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पाथ नहीं है, तो इसका अर्थ है कि कुंजी स्ट्रिंग या तो पूर्ण रूप से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, अथवा सर्च ट्री में नहीं है। कई कार्यान्वयन केवल पश्चात की स्थिति को सुनिश्चित करने के लिए स्ट्रिंग कैरेक्टर के अंत का उपयोग करते हैं। तत्पश्चात पाथ को फर्स्टमिड.मिड से सर्च पाथ के अंत तक डिलीट कर दिया जाता है। इस स्थिति में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग ट्री में अंतिम स्ट्रिंग होनी चाहिए, और इस प्रकार रूट को डिलीट करने के पश्चात शून्य पर सेट किया जाता है।
डिलीट ऑपरेशन में सर्च ट्री में कुंजी स्ट्रिंग को सर्च करना और नोड को फाइंड करना सम्मिलित है, जिसे नीचे सुडो कोड में फर्स्टमिड कहा जाता है, जिस प्रकार कुंजी स्ट्रिंग के लिए सर्च पाथ के फर्स्टमिड के मध्य चाइल्ड से अंत तक के पाथ में कोई बाएँ या दाएँ चाइल्ड नहीं है। यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पाथ नहीं है, तो इसका अर्थ है कि कुंजी स्ट्रिंग या तो पूर्ण रूप से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, अथवा सर्च ट्री में नहीं है। कई कार्यान्वयन केवल पश्चात की स्थिति को सुनिश्चित करने के लिए स्ट्रिंग कैरेक्टर के अंत का उपयोग करते हैं। तत्पश्चात पाथ को फर्स्टमिड.मिड से सर्च पाथ के अंत तक डिलीट कर दिया जाता है। इस स्थिति में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग ट्री में अंतिम स्ट्रिंग होनी चाहिए, और इस प्रकार रूट को डिलीट करने के पश्चात शून्य पर सेट किया जाता है।
 
  function delete(string key) is
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
     if is_empty(key) then
  फ़ंक्शन डिलीट (स्ट्रिंग कुंजी) है
         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
 
    // इस बिंदु पर, फर्स्टमिड स्ट्रिंग अद्वितीय प्रत्यय होने से पहले नोड को इंगित करता है
    नोड q:= फर्स्टमिड.मिड
    नोड पी:= क्यू
    फर्स्टमिड.मिड:= शून्य // ट्री से प्रत्यय को डिस्कनेक्ट करें
    जबकि q शून्य नहीं है //प्रत्यय पाथ पर चलें और नोड्स हटा दें
        पी:= क्यू
        q:= q.मध्य
        डिलीट(पी) // नोड पी से जुड़ी मुफ्त मेमोरी
    यदि फर्स्टमिड == रूट है तो
        डिलीट(रूट) // पूरे ट्री को हटा दें
        जड़:= शून्य
</सिंटैक्सहाइलाइट>


    // 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
=== ट्रैवर्सल ===
=== ट्रैवर्सल ===


Line 173: Line 134:
{| 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 220: 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’