टर्नरी सर्च ट्री

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

Ternary Search Tree (TST)
Type	tree
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)

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

विवरण

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

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

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

संचालन

इंसर्शन

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

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 >

फ़ंक्शन सर्च (स्ट्रिंग क्वेरी) है
    यदि 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.मध्य
        डिलीट(पी) // नोड पी से जुड़ी मुफ्त मेमोरी
    यदि फर्स्टमिड == रूट है तो
        डिलीट(रूट) // पूरे ट्री को हटा दें
        जड़:= शून्य

</सिंटैक्सहाइलाइट>

रनिंग टाइम

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

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

	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)

अन्य डेटा संरचनाओं से तुलना

ट्राइज

अन्य प्रीफिक्स ट्रीज की तुलना में मंद होने पर भी, टर्नरी सर्च ट्री अपनी स्थान-दक्षता के कारण बड़े डेटा सेट के लिए श्रेष्ठ अनुकूल हो सकते हैं।

हैश मानचित्र

स्ट्रिंग्स को मानों में मैप करने के लिए टर्नरी सर्च ट्री के स्थान पर हैश तालिका का भी उपयोग किया जा सकता है। यद्यपि, हैश मानचित्र भी अधिकांशतः टर्नरी सर्च ट्री की तुलना में अधिक मेमोरी का उपयोग करते हैं (किन्तु उतना नहीं जितना प्रयास किया जाता है)। इसके अतिरिक्त, हैश मैप सामान्यतः स्ट्रिंग की रिपोर्ट करने में मंद होते हैं जो समान डेटा संरचना में नहीं है, क्योंकि इसमें केवल प्रथम कुछ कैरेक्टर्स की तुलना में पूर्ण स्ट्रिंग की तुलना करनी होगी। ऐसे कुछ प्रमाण हैं जो टर्नरी सर्च ट्री को हैश मैप की तुलना में तीव्रता से रन करते हुए दिखाते हैं। इसके अतिरिक्त, हैश मैप टर्नरी सर्च ट्री के कई उपयोगों जैसे नियर-नेबर लुकअप की अनुमति प्रदान नहीं करते हैं।

डीएएफएसए (नियतात्मक चक्रीय परिमित अवस्था ऑटोमेटन)

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

उपयोग

टर्नरी सर्च ट्री का उपयोग कई समस्याओं का समाधान करने के लिए किया जा सकता है जिसमें बड़ी संख्या में स्ट्रिंग्स को आरबिटरेरी क्रम में संग्रहीत और पुनर्प्राप्त किया जाना चाहिए। इनमें से कुछ सबसे सामान्य या सबसे उपयोगी नीचे हैं:

• किसी भी समय ट्राई का उपयोग किया जा सकता है किन्तु कम मेमोरी उपयोग वाली संरचना को प्राथमिकता दी जाती है।
• अन्य डेटा के डेटा मैपिंग स्ट्रिंग के लिए शीघ्र और स्थान-संचारण डेटा संरचना का उपयोग किया जाता है।
• स्वतः पूर्णता प्रारम्भ करने के लिए उपयोग किया जाता है।
• वर्तनी अन्वेषण के रूप में उपयोग किया जाता है।
• नियर-नेबर सर्चिंग (जिसमें वर्तनी-अन्वेषण विशेष स्थिति है)।
• डेटाबेस के रूप में, विशेष रूप से जब कई गैर-कुंजी फ़ील्ड द्वारा अनुक्रमण वांछनीय है।
• हैश तालिका के स्थान पर उपयोग किया जाता है।

यह भी देखें

• थ्री-वे रेडिक्स क्विकसॉर्ट
• ट्राइ
• बाइनरी सर्च ट्री
• हैश तालिका

बाहरी संबंध

• 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