टर्नरी सर्च ट्री
| Ternary Search Tree (TST) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | ||||||||||||
| Time complexity in big O notation | |||||||||||||
| |||||||||||||
कंप्यूटर विज्ञान में, टर्नरी सर्च ट्री ट्राइ का प्रकार है (जिसे कभी-कभी प्रीफिक्स ट्री भी कहा जाता है) जहां नोड्स को बाइनरी सर्च ट्री के समान विधि द्वारा व्यवस्थित किया जाता है, किन्तु बाइनरी ट्री दो की सीमा के अतिरिक्त तीन बच्चों तक होता है। अन्य प्रीफिक्स ट्री की भाँति, टर्नरी सर्च ट्री का उपयोग वृद्धिशील स्ट्रिंग सर्च की क्षमता के साथ सहयोगी मानचित्र संरचना के रूप में किया जा सकता है। यद्यपि, गति के मूल्य पर, टर्नरी सर्च ट्री मानक प्रीफिक्स ट्री की तुलना में अधिक स्थान कुशल हैं। टर्नरी सर्च ट्री के सामान्य अनुप्रयोगों में वर्तनी-अन्वेषण और स्वत: पूर्णता सम्मिलित है।
विवरण
टर्नरी सर्च ट्री का प्रत्येक नोड एकल वर्ण (कला), ऑब्जेक्ट (या कार्यान्वयन के आधार पर किसी ऑब्जेक्ट के लिए पॉइंटर (कंप्यूटर प्रोग्रामिंग)) को संग्रहीत करता है, और इसके तीन बच्चों के लिए पॉइंटर्स को पारंपरिक रूप से समान किड, लो किड और हाय किड नाम दिया गया है, जिन्हें क्रमशः मध्य (बच्चा), निचला (बच्चा) और उच्चतर (बच्चा) भी कहा जा सकता है।[1] नोड में अपने मूल नोड के लिए सूचक के साथ संकेतक भी हो सकता है कि नोड किसी शब्द के अंत को चिह्नित करता है या नहीं करता है।[2] लो किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका वर्ण मान वर्तमान नोड से कम है। हाय किड पॉइंटर को ऐसे नोड की ओर संकेत करना चाहिए जिसका कैरेक्टर वर्तमान नोड से बड़ा है।[1] बराबर का बच्चा शब्द में अगले अक्षर की ओर इशारा करता है। नीचे दिया गया चित्र क्यूट, कप, एट, एज़, वह, यूएस और आई स्ट्रिंग के साथ टर्नरी सर्च ट्री दिखाता है:
c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s
अन्य ट्राई डेटा संरचनाओं की भाँति, टर्नरी सर्च ट्री में प्रत्येक नोड संग्रहीत स्ट्रिंग्स के उपसर्ग का प्रतिनिधित्व करता है। किसी नोड के मध्य सबट्री में सभी स्ट्रिंग उस उपसर्ग से प्रारम्भ होते हैं।
संचालन
सम्मिलन
टर्नरी खोज में एक मान डालने को लुकअप को परिभाषित करने के समान ही पुनरावर्ती या पुनरावृत्त रूप से परिभाषित किया जा सकता है। इस पुनरावर्ती विधि को एक कुंजी दिए जाने पर पेड़ के नोड्स पर लगातार बुलाया जाता है जो कुंजी के सामने से वर्णों को काटकर उत्तरोत्तर छोटा होता जाता है। यदि यह विधि किसी ऐसे नोड तक पहुँचती है जो नहीं बनाया गया है, तो यह नोड बनाता है और उसे कुंजी में पहले वर्ण का वर्ण मान निर्दिष्ट करता है। कोई नया नोड बनाया गया है या नहीं, विधि यह देखने के लिए जांच करती है कि स्ट्रिंग में पहला वर्ण नोड में वर्ण मान से अधिक है या कम है और लुकअप ऑपरेशन के अनुसार उपयुक्त नोड पर एक पुनरावर्ती कॉल करता है। यद्यपि, यदि कुंजी का पहला अक्षर नोड के मान के बराबर है तो सम्मिलन प्रक्रिया को बराबर बच्चे पर बुलाया जाता है और कुंजी का पहला अक्षर हटा दिया जाता है।[1] बाइनरी सर्च ट्री और अन्य डेटा संरचनाओं की तरह, टर्नरी सर्च ट्री कुंजियों के क्रम के आधार पर खराब हो सकते हैं।[3] वर्णानुक्रम में कुंजियाँ डालना सबसे खराब संभावित ख़राब पेड़ को प्राप्त करने का एक तरीका है।[1]कुंजियों को यादृच्छिक क्रम में डालने से अक्सर एक अच्छी तरह से संतुलित पेड़ बनता है।[1]<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 > फ़ंक्शन इंसर्शन (स्ट्रिंग कुंजी) है नोड पी= रूट
//रूट शून्य होने की स्थिति में बराबर होने के लिए आरंभ किया गया
नोड अंतिम= रूट पूर्णांक आईडीएक्स= 0 जबकि p शून्य नहीं है
//उचित उपवृक्ष पर पुनरावृत्ति करें
यदि key[idx] < p.splitchar तो अंतिम= पी पी= पी.बाएं अन्यथा यदि key[idx] > p.splitchar तो अंतिम= पी पी= पी.सही अन्य:
// कुंजी पहले से ही हमारे पेड़ में है
यदि idx == लंबाई (कुंजी) तो वापस करना
// हमारी कुंजी से चरित्र ट्रिम करें
आईडीएक्स= आईडीएक्स+1 अंतिम= पी पी:= पी.मध्य पी= नोड()
// अंतिम गैर-शून्य नोड के चाइल्ड के रूप में p जोड़ें (या यदि रूट शून्य है तो रूट करें)
यदि रूट == शून्य है तो
जड़:= पी
अन्यथा यदि Last.splitchar < key[idx] तो अंतिम.दाएं:= पी अन्यथा यदि Last.splitchar > key[idx] तो अंतिम.बाएं= पी अन्य अंतिम.मध्य = पी p.स्प्लिटचर= कुंजी[idx] आईडीएक्स:= आईडीएक्स+1
// कुंजी का शेष भाग डालें
जबकि idx < length(key) करते हैं p.mid:= नोड()
p.mid.splitchar:= कुंजी[idx]
आईडीएक्स += 1 </सिंटैक्सहाइलाइट>
खोजें
किसी विशेष नोड या नोड से जुड़े डेटा को देखने के लिए, एक स्ट्रिंग कुंजी की आवश्यकता होती है। लुकअप प्रक्रिया पेड़ के रूट नोड की जांच करके और यह निर्धारित करके शुरू होती है कि निम्नलिखित में से कौन सी स्थिति उत्पन्न हुई है। यदि स्ट्रिंग का पहला वर्ण रूट नोड के वर्ण से कम है, तो उस पेड़ पर एक पुनरावर्ती लुकअप को कॉल किया जा सकता है जिसका रूट वर्तमान रूट का लो किड है। इसी प्रकार, यदि पहला अक्षर पेड़ में वर्तमान नोड से बड़ा है, तो उस पेड़ पर एक पुनरावर्ती कॉल की जा सकती है जिसकी जड़ वर्तमान नोड का हाय किड है।[1]अंतिम मामले के रूप में, यदि स्ट्रिंग का पहला अक्षर वर्तमान नोड के चरित्र के बराबर है तो कुंजी में कोई और अक्षर नहीं होने पर फ़ंक्शन नोड लौटाता है। यदि कुंजी में अधिक अक्षर हैं तो कुंजी का पहला अक्षर हटा दिया जाना चाहिए और समान किड नोड और संशोधित कुंजी को देखते हुए एक पुनरावर्ती कॉल किया जाना चाहिए।[1]इसे वर्तमान नोड के लिए एक सूचक और कुंजी के वर्तमान चरित्र के लिए एक सूचक का उपयोग करके गैर-पुनरावर्ती तरीके से भी लिखा जा सकता है।[1]
स्यूडोकोड
<सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
फ़ंक्शन खोज (स्ट्रिंग क्वेरी) है
यदि is_empty(क्वेरी) है तो
विवरण झूठा है
नोड पी:= रूट
पूर्णांक आईडीएक्स:= 0
जबकि p शून्य नहीं है
यदि क्वेरी[idx] <p.splitchar तो
पी:= पी.बाएं
अन्यथा यदि query[idx] > p.splitchar तो
पी:= पी.सही;
अन्य
यदि idx = लंबाई(क्वेरी) तो
सच लौटें
आईडीएक्स:= आईडीएक्स + 1
पी:= पी.मध्य
विवरण झूठा है
</सिंटैक्सहाइलाइट>
विलोपन
डिलीट ऑपरेशन में सर्च ट्री में एक कुंजी स्ट्रिंग की खोज करना और एक नोड ढूंढना सम्मिलित है, जिसे नीचे छद्म कोड में फर्स्टमिड कहा जाता है, जैसे कि फर्स्टमिड के मध्य चाइल्ड से लेकर कुंजी स्ट्रिंग के लिए खोज पथ के अंत तक का कोई रास्ता नहीं है। या सही बच्चे. यह कुंजी स्ट्रिंग के अनुरूप टर्नरी ट्री में एक अद्वितीय प्रत्यय का प्रतिनिधित्व करेगा। यदि ऐसा कोई पथ नहीं है, तो इसका मतलब है कि कुंजी स्ट्रिंग या तो पूरी तरह से किसी अन्य स्ट्रिंग के उपसर्ग के रूप में समाहित है, या खोज ट्री में नहीं है। कई कार्यान्वयन केवल बाद वाले मामले को सुनिश्चित करने के लिए स्ट्रिंग वर्ण के अंत का उपयोग करते हैं। फिर पथ को फर्स्टमिड.मिड से खोज पथ के अंत तक हटा दिया जाता है। इस मामले में कि फर्स्टमिड रूट है, कुंजी स्ट्रिंग पेड़ में आखिरी स्ट्रिंग रही होगी, और इस प्रकार रूट को हटाने के बाद शून्य पर सेट किया गया है। <सिंटैक्सहाइलाइट लैंग=पास्कल स्टार्ट=1 >
फ़ंक्शन डिलीट (स्ट्रिंग कुंजी) है
यदि is_empty(key) है तो
वापस करना
नोड पी:= रूट
पूर्णांक आईडीएक्स:= 0
नोड फर्स्टमिड:= शून्य
जबकि p शून्य नहीं है
यदि key[idx] < p.splitchar तो
फर्स्टमिड:= शून्य
पी:= पी.बाएं
अन्यथा यदि key[idx] > p.splitchar तो
फर्स्टमिड:= शून्य
पी:= पी.सही
अन्य
फर्स्टमिड:= पी
जबकि p शून्य नहीं है और key[idx] == p.splitchar करते हैं
आईडीएक्स:= आईडीएक्स + 1
पी:= पी.मध्य
यदि फर्स्टमिड == शून्य है तो
वापसी // कोई अद्वितीय स्ट्रिंग प्रत्यय नहीं
// इस बिंदु पर, फर्स्टमिड स्ट्रिंग अद्वितीय प्रत्यय होने से पहले नोड को इंगित करता है
नोड q:= फर्स्टमिड.मिड
नोड पी:= क्यू
फर्स्टमिड.मिड:= शून्य // पेड़ से प्रत्यय को डिस्कनेक्ट करें
जबकि q शून्य नहीं है //प्रत्यय पथ पर चलें और नोड्स हटा दें
पी:= क्यू
q:= q.मध्य
डिलीट(पी) // नोड पी से जुड़ी मुफ्त मेमोरी
यदि फर्स्टमिड == रूट है तो
डिलीट(रूट) // पूरे पेड़ को हटा दें
जड़:= शून्य
</सिंटैक्सहाइलाइट>
ट्रैवर्सल
आंशिक-मिलान खोज
निकट-पड़ोसी खोज रहा है
चलने का समय
टर्नरी सर्च ट्री का चलने का समय इनपुट के साथ काफी भिन्न होता है। जब कई समान स्ट्रिंग दी जाती हैं तो टर्नरी सर्च ट्री सबसे अच्छे से चलते हैं, खासकर जब वे स्ट्रिंग एक सामान्य उपसर्ग साझा करते हैं। वैकल्पिक रूप से, बड़ी संख्या में अपेक्षाकृत छोटी स्ट्रिंग्स (जैसे शब्दकोश में शब्द) को संग्रहीत करते समय टर्नरी सर्च ट्री प्रभावी होते हैं।[1]टर्नरी सर्च ट्री के लिए चलने का समय बाइनरी खोज पेड़ के समान है, जिसमें वे आम तौर पर लॉगरिदमिक समय में चलते हैं, किन्तु खराब (सबसे खराब) स्थिति में रैखिक समय में चल सकते हैं। इसके अलावा, रनटाइम पर विचार करते समय स्ट्रिंग्स के आकार को भी ध्यान में रखा जाना चाहिए। उदाहरण के लिए, लंबाई k की एक स्ट्रिंग के लिए खोज पथ में, पेड़ में मध्य बच्चों के नीचे k ट्रैवर्सल होंगे, साथ ही पेड़ में बाएं और दाएं बच्चों के नीचे ट्रैवर्सल की एक लघुगणकीय संख्या होगी। इस प्रकार, एक टर्नरी सर्च ट्री में बहुत बड़ी स्ट्रिंग्स की एक छोटी संख्या पर स्ट्रिंग्स की लंबाई रनटाइम पर हावी हो सकती है।[4] टर्नरी सर्च ट्री संचालन के लिए समय जटिलताएँ:[1]
| Average-case running time | Worst-case running time | |
|---|---|---|
| Lookup | O(log n + k) | O(n + k) |
| Insertion | O(log n + k) | O(n + k) |
| Delete | O(log n + k) | O(n + k) |
अन्य डेटा संरचनाओं से तुलना
प्रयास
अन्य प्रयासों की तुलना में धीमे होने के बावजूद, टर्नरी सर्च ट्री अपनी स्थान-दक्षता के कारण बड़े डेटा सेट के लिए बेहतर अनुकूल हो सकते हैं।[1]
हैश मानचित्र
स्ट्रिंग्स को मानों में मैप करने के लिए टर्नरी सर्च ट्री के स्थान पर हैश तालिका ्स का भी उपयोग किया जा सकता है। यद्यपि, हैश मानचित्र भी अक्सर टर्नरी सर्च ट्री की तुलना में अधिक मेमोरी का उपयोग करते हैं (किन्तु उतना नहीं जितना प्रयास किया जाता है)। इसके अतिरिक्त, हैश मैप आमतौर पर एक स्ट्रिंग की रिपोर्ट करने में धीमे होते हैं जो समान डेटा संरचना में नहीं है, क्योंकि इसमें केवल पहले कुछ वर्णों की तुलना में पूरी स्ट्रिंग की तुलना करनी होगी। ऐसे कुछ सबूत हैं जो टर्नरी सर्च ट्री को हैश मैप की तुलना में तेजी से चलते हुए दिखाते हैं।[1]इसके अतिरिक्त, हैश मानचित्र टर्नरी सर्च ट्रीों के कई उपयोगों की अनुमति नहीं देते हैं, जैसे कि निकट-पड़ोसी लुकअप।
डीएएफएसए (नियतात्मक चक्रीय परिमित अवस्था ऑटोमेटन)
यदि शब्दकोश शब्दों को संग्रहीत करना ही आवश्यक है (यानी, प्रत्येक शब्द के लिए सहायक जानकारी का भंडारण आवश्यक नहीं है), तो न्यूनतम नियतात्मक चक्रीय परिमित राज्य ऑटोमेटन (डीएएफएसए) एक ट्राई या टर्नरी सर्च ट्री की तुलना में कम जगह का उपयोग करेगा। ऐसा इसलिए है क्योंकि एक डीएएफएसए त्रि से समान शाखाओं को संपीड़ित कर सकता है जो संग्रहीत किए जा रहे विभिन्न शब्दों के समान प्रत्ययों (या भागों) से मेल खाते हैं।
उपयोग
टर्नरी सर्च ट्री का उपयोग कई समस्याओं को हल करने के लिए किया जा सकता है जिसमें बड़ी संख्या में स्ट्रिंग्स को मनमाने क्रम में संग्रहीत और पुनर्प्राप्त किया जाना चाहिए। इनमें से कुछ सबसे आम या सबसे उपयोगी नीचे हैं:
- किसी भी समय ट्राई का उपयोग किया जा सकता है किन्तु कम मेमोरी खपत वाली संरचना को प्राथमिकता दी जाती है।[1]* अन्य डेटा के लिए डेटा मैपिंग स्ट्रिंग के लिए एक त्वरित और स्थान-बचत डेटा संरचना।[3]* स्वतः पूर्णता लागू करने के लिए।[2]
- वर्तनी जाँच के रूप में।[5]
- निकटतम पड़ोसी खोज|निकट-पड़ोसी खोज (जिसमें वर्तनी-जांच एक विशेष मामला है)।[1]* एक डेटाबेस के रूप में, विशेष रूप से जब कई गैर-कुंजी फ़ील्ड द्वारा अनुक्रमण वांछनीय है।[5]* हैश तालिका के स्थान पर.[5]
यह भी देखें
- थ्री-वे रेडिक्स क्विकसॉर्ट
- प्रयास करें
- बाइनरी सर्च ट्री
- हैश तालिका
संदर्भ
- ↑ 1.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.0 2.1 Ostrovsky, Igor. "टर्नरी सर्च ट्री के साथ कुशल स्वतः पूर्ण".
- ↑ 3.0 3.1 Wrobel, Lukasz. "टर्नेरी सर्च ट्री".
- ↑ Bentley, Jon; Sedgewick, Bob. "टर्नेरी सर्च ट्री".
- ↑ 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
