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

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


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


==विवरण==
==विवरण==
Line 34: Line 34:
function insertion(string key) is
function insertion(string key) is


node p := root  
node p= root  
     //initialized to be equal in case root is null
     //initialized to be equal in case root is null
node last := root
node last= root


int idx := 0
int idx= 0


while p is not null do
while p is not null do
Line 44: Line 44:
if key[idx] < p.splitchar then
if key[idx] < p.splitchar then


last := p
last= p


p := p.left
p= p.left


else if key[idx] > p.splitchar then
else if key[idx] > p.splitchar then


last := p
last= p


p := p.right
p= p.right


else:
else:
Line 60: Line 60:
return  
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= p.mid


p := node()
p= node()
   //add p in as a child of the last non-null node (or root if root is null)
   //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
         root= p
else if last.splitchar < key[idx] then
else if last.splitchar < key[idx] then


last.right := p
last.right= p


else if last.splitchar > key[idx] then
else if last.splitchar > key[idx] then


last.left := p
last.left= p


else  
else  


last.mid := p
last.mid= p


p.splitchar := key[idx]
p.splitchar= key[idx]


idx := idx+1
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]
p.mid.splitchar= key[idx]


idx += 1
idx += 1
Line 103: Line 103:
         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 125: Line 125:
         return  
         return  
   
   
     node p := root
     node p= root
     int idx := 0
     int idx= 0


  node firstMid := null
  node firstMid= null
     while p is not null do
     while p is not null do
         if key[idx] < p.splitchar then
         if key[idx] < p.splitchar then
             firstMid := null
             firstMid= null
             p := p.left
             p= p.left
           else if key[idx] > p.splitchar then
           else if key[idx] > p.splitchar then
             firstMid := null
             firstMid= null
             p := p.right
             p= p.right
         else
         else
             firstMid := p
             firstMid= p
             while p is not null and key[idx] == p.splitchar do
             while p is not null and key[idx] == p.splitchar do
             idx := idx + 1
             idx= idx + 1
             p := p.mid
             p= p.mid
              
              
     if firstMid == null then
     if firstMid == null then
Line 146: Line 146:


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


Revision as of 20:35, 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]

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=234505’