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