ऑप्टिमल बाइनरी सर्च ट्री

कंप्यूटर विज्ञान में, सर्वोत्तम बाइनरी सर्च ट्री (ऑप्टिमल बीएसटी), जिसे कभी-कभी वजन-संतुलित बाइनरी ट्री भी कहा जाता है, बाइनरी सर्च ट्री है जो एक्सेस के दिए गए अनुक्रम (या एक्सेस संभावनाओं) के लिए सबसे छोटा संभव खोज समय (या अपेक्षित मूल्य) प्रदान करता है। सर्वोत्तम बीएसटी को सामान्यतः दो प्रकारों स्थिर और गतिशील में विभाजित किया जाता है।

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

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

स्थिर अनुकूलता

परिभाषा

डोनाल्ड ई. नुथ द्वारा परिभाषित स्थैतिक सर्वोत्तमता समस्या में, हमें का समुच्चय दिया गया है इस प्रकार n आदेशित अवयव और का समुच्चय $2n+1$ सम्भावनाएँ हम अवयवों को निरूपित करेंगे $a_{1}$ द्वारा $a_{n}$ और संभावनाएँ $A_{1}$ द्वारा $A_{n}$ और $B_{0}$ द्वारा $B_{n}$. $A_{i}$ अवयव के लिए खोज किये जाने की संभावना है $a_{i}$ (या सफल खोज). के लिए $1\leq i<n$, $B_{i}$ के बीच किसी अवयव की खोज होने की संभावना है $a_{i}$ और $a_{i+1}$(या असफल खोज), $B_{0}$ किसी अवयव के लिए खोज किए जाने की संभावना बिल्कुल कम $a_{1}$, और $B_{n}$ है किसी अवयव के लिए खोज किए जाने की संभावना उससे कहीं अधिक $a_{n}$ है इन $2n+1$ संभावनाएँ सभी संभावित खोजों को कवर करती हैं, और इसलिए तक जुड़ जाती हैं।

स्थैतिक सर्वोत्तमता समस्या बाइनरी खोज ट्री को खोजने की अनुकूलन समस्या है जो अपेक्षित खोज समय को कम करती है, जिसे देखते हुए $2n+1$ सम्भावनाएँ के समुच्चय पर संभावित ट्री की संख्या के रूप में n अवयव है ${2n \choose n}{\frac {1}{n+1}}$, जो कि घातांकीय है n, क्रूर-बल खोज सामान्यतः व्यवहार्य समाधान नहीं है।

नुथ का गतिशील प्रोग्रामिंग एल्गोरिदम

1971 में, नुथ ने अपेक्षाकृत सीधा गतिशील प्रोग्रामिंग एल्गोरिदम प्रकाशित किया जो केवल O(n²) में सांख्यिकीय रूप से सर्वोत्तम ट्री का निर्माण करने में सक्षम था।) समय. इस कार्य में, नथ ने 1958 में एडगर गिल्बर्ट और एडवर्ड एफ. मूर द्वारा प्रस्तुत गतिशील प्रोग्रामिंग एल्गोरिदम का विस्तार और सुधार किया था। गिल्बर्ट और मूर का एल्गोरिदम आवश्यक है इस प्रकार $O(n^{3})$ समय और $O(n^{2})$ समिष्ट और सर्वोत्तम बाइनरी खोज ट्री निर्माण के विशेष स्थिति के लिए डिज़ाइन किया गया था (सर्वोत्तम वर्णमाला ट्री समस्या के रूप में जाना जाता है)। जो केवल असफल खोजों की संभावना पर विचार करता है, अर्थात, ${\textstyle \sum _{i=1}^{n}A_{i}=0}$. नुथ का कार्य निम्नलिखित अंतर्दृष्टि पर निर्भर था: स्थैतिक सर्वोत्तमता समस्या सर्वोत्तम उपसंरचना को प्रदर्शित करती है; अर्थात्, यदि निश्चित ट्री किसी दिए गए संभाव्यता वितरण के लिए सांख्यिकीय रूप से सर्वोत्तम है, तो उसके बाएँ और दाएँ उपट्री भी वितरण के उनके उपयुक्त उपसमूहों के लिए सांख्यिकीय रूप से सर्वोत्तम होने चाहिए (मूलों की एकरसता प्रोपर्टी के रूप में जाना जाता है)।

इसे देखने के लिए, विचार करें कि नथ ट्री की भारित पथ लंबाई को क्या कहते हैं। n अवयवों के ट्री की भारित पथ लंबाई सभी की लंबाई का योग है $2n+1$ संभावित खोज पथ, उनकी संबंधित संभावनाओं के आधार पर भारित न्यूनतम भारित पथ लंबाई वाला ट्री, परिभाषा के अनुसार, सांख्यिकीय रूप से सर्वोत्तम है।

किन्तु भारित पथ लंबाई में रोचक गुण होता है। मान लीजिए E बाइनरी ट्री की भारित पथ लंबाई है, E_L इसके बाएँ उपट्री की भारित पथ लंबाई हो, और E_R इसके दाएँ उपट्री की भारित पथ लंबाई होता है। यह भी मान लें कि W ट्री की सभी संभावनाओं का योग है। ध्यान दें कि जब कोई भी उपट्री मूल से जुड़ा होता है, तो उसके प्रत्येक अवयव की गहराई (और इस प्रकार उसके प्रत्येक खोज पथ) में की वृद्धि होती है। यह भी ध्यान रखें कि मूल की गहराई भी होता है। इसका कारण यह है कि ट्री और उसके दो उपट्री के बीच भारित पथ की लंबाई का अंतर ट्री में हर संभावना का योग है, जिससे निम्नलिखित पुनरावृत्ति होती है:

$E=E_{L}+E_{R}+W$

यह पुनरावृत्ति प्राकृतिक गतिशील प्रोग्रामिंग समाधान की ओर ले जाती है। मान लीजिए $E_{ij}$ बीच के सभी मानों के लिए सांख्यिकीय रूप से सर्वोत्तम खोज ट्री की भारित पथ लंबाई हो a_i और a_j, मान लीजिए $W_{ij}$ उस ट्री का कुल वजन हो, और रहने दो $R_{ij}$ इसकी मूल का सूचकांक बनें. एल्गोरिथ्म निम्नलिखित सूत्रों का उपयोग करके बनाया जा सकता है:

${\begin{aligned}E_{i,i-1}=W_{i,i-1}&=B_{i-1}\operatorname {for} 1\leq i\leq n+1\\W_{i,j}&=W_{i,j-1}+A_{j}+B_{j}\\E_{i,j}&=\min _{i\leq r\leq j}(E_{i,r-1}+E_{r+1,j}+W_{i,j})\operatorname {for} 1\leq i\leq j\leq n\end{aligned}}$

इस एल्गोरिथ्म का सरल कार्यान्वयन वास्तव में O(n) लेता है³) समय, किन्तु नथ के पेपर में कुछ अतिरिक्त अवलोकन सम्मिलित हैं जिनका उपयोग केवल O(n) लेकर संशोधित एल्गोरिदम तैयार करने के लिए किया जा सकता है)

इस प्रकार अपने गतिशील प्रोग्रामिंग एल्गोरिदम के अतिरिक्त, नुथ ने सर्वोत्तम बाइनरी खोज ट्री का लगभग (अनुमान) उत्पादन करने के लिए दो अनुमान (या नियम) प्रस्तावित किए जाते है। लगभग सर्वोत्तम बाइनरी खोज ट्री का अध्ययन करना आवश्यक था क्योंकि नुथ के एल्गोरिथ्म समय और समिष्ट की जटिलता निषेधात्मक हो सकती है $n$ अधिक बड़ा है. नुथ के नियमों को निम्नलिखित के रूप में देखा जा सकता है:

• नियम I (रूट-मैक्स): सबसे अधिक बार आने वाले नाम को ट्री की मूल में रखें, फिर उपट्री पर भी इसी तरह आगे बढ़ें।
• नियम II (द्विभाजन): मूल का चयन करें ताकि बाएं और दाएं उपट्री के कुल वजन को जितना संभव हो सके समान किया जा सके, फिर उपट्री पर भी इसी तरह आगे बढ़ें।

नुथ का अनुमान लगभग सर्वोत्तम बाइनरी सर्च ट्री को प्रयुक्त करता है इस प्रकार $O(n\log n)$ समय और $O(n)$ समिष्ट सर्वोत्तम नुथ के अनुमान से कितनी दूर हो सकता है इसका विश्लेषण आगे कर्ट मेहलहॉर्न द्वारा प्रस्तावित किया गया था।

मेहलहॉर्न का सन्निकटन एल्गोरिथ्म

जबकि o(n²) नथ के एल्गोरिदम द्वारा लिया गया समय जानवर-बल खोज के लिए आवश्यक घातीय समय से अधिक उत्तम है, यह अभी भी व्यावहारिक होने के लिए बहुत धीमा है जब ट्री में अवयवों की संख्या बहुत बड़ी है।

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

${\textstyle {\begin{aligned}n=2^{k}-1,~~A_{i}=2^{-k}+\varepsilon _{i}~~\operatorname {with} ~~\sum _{i=1}^{n}\varepsilon _{i}=2^{-k}\end{aligned}}}$ और

${\textstyle {\begin{aligned}\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{n}>0~~\operatorname {for} ~~1\leqq i\leqq n~~\operatorname {and} ~~B_{j}=0\operatorname {for} ~~0\leqq j\leqq n.\end{aligned}}}$ भारित पथ लंबाई को ध्यान में रखते हुए $P$ पिछली परिभाषा के आधार पर निर्मित ट्री से, हमारे पास निम्नलिखित हैं:

${\textstyle {\begin{aligned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_{j}\\&=\sum _{i=1}^{n}A_{i}i\\&\geqq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1)}{2}}\geqq {\frac {n}{2}}.\end{aligned}}}$

इस प्रकार, रूट-मैक्स नियम के अनुसार परिणामी ट्री ऐसा ट्री होगा जो केवल दाईं ओर बढ़ता है (ट्री के सबसे गहरे स्तर को छोड़कर), और बाईं ओर सदैव टर्मिनल नोड्स होंगे। इस ट्री की पथ लंबाई से घिरा हुआ है ${\textstyle \Omega ({\frac {n}{2}})}$ और, जब संतुलित खोज ट्री के साथ तुलना की जाती है (पथ से घिरा हुआ) ${\textstyle O(2\log n)}$), समान आवृत्ति वितरण के लिए अधिक व्यर्थ प्रदर्शन करते है।

इसके अतिरिक्त, मेहलहॉर्न ने नुथ के काम में सुधार किया और बहुत ही सरल एल्गोरिथ्म प्रस्तुत किया जो नियम II का उपयोग करता है और केवल सांख्यिकीय रूप से सर्वोत्तम ट्री के प्रदर्शन का सूक्ष्मता से अनुमान लगाता है। $O(n)$ समय एल्गोरिथ्म बाएँ और दाएँ उपट्री के कुल वजन (संभावना द्वारा) को सबसे निकट से संतुलित करने के लिए ट्री की मूल को चुनकर द्विभाजन नियम के समान विचार का पालन करता है। और फिर रणनीति को प्रत्येक उपट्री पर पुनरावर्ती रूप से प्रयुक्त किया जाता है।

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

$2+(1-\log({\sqrt {5}}-1))^{-1}H=2+{\frac {H}{1-\log({\sqrt {5}}-1)}}$

जहाँ H संभाव्यता वितरण की एन्ट्रापी (सूचना सिद्धांत) है। चूँकि कोई भी सर्वोत्तम बाइनरी सर्च ट्री कभी भी भारित पथ लंबाई से उत्तम नहीं कर सकता है

$(1/\log 3)H={\frac {H}{\log 3}}$

यह सन्निकटन बहुत निकट है.

हू-टकर और गार्सिया-वाच एल्गोरिदम

Main article: गार्सिया-वॉच एल्गोरिदम

विशेष स्थिति में कि सभी $A_{i}$ मान शून्य हैं, सर्वोत्तम ट्री समय में पाया जा सकता है $O(n\log n)$. यह पहली बार टी. सी. हू और एलन टकर द्वारा 1971 में प्रकाशित पेपर में सिद्ध किया गया था। गार्सिया और वाच्स द्वारा पश्चात् में सरलीकरण, गार्सिया-वाच एल्गोरिदम, समान क्रम में समान तुलना करता है। एल्गोरिथ्म ग्रीडी एल्गोरिदम का उपयोग करके ट्री का निर्माण करता है जिसमें प्रत्येक पत्ते के लिए सर्वोत्तम ऊंचाई होती है, किन्तु क्रम से बाहर है, और फिर उसी ऊंचाई के साथ और बाइनरी खोज ट्री का निर्माण करता है।

गतिशील सर्वोत्तमता

Unsolved problem in कंप्यूटर विज्ञान:

क्या स्प्ले ट्री किसी अन्य बाइनरी सर्च ट्री एल्गोरिदम की तरह ही अच्छा प्रदर्शन करते हैं?

(more unsolved problems in कंप्यूटर विज्ञान)

परिभाषा

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

गतिशील सर्वोत्तमता समस्या में, हमें एक्सेस x₁, ..., x_m का क्रम दिया गया है कीज पर प्रत्येक एक्सेस के लिए, हमें अपने बीएसटी के रूट पर पॉइंटर (कंप्यूटर प्रोग्रामिंग) दिया जाता है और हम निम्नलिखित में से कोई भी ऑपरेशन करने के लिए पॉइंटर का उपयोग कर सकते हैं:

1. पॉइंटर को वर्तमान नोड के बाएँ चाइल्ड पर ले जाएँ।
2. पॉइंटर को वर्तमान नोड के दाएँ चाइल्ड पर ले जाएँ।
3. पॉइंटर को वर्तमान नोड के पैरेंट पर ले जाएं।
4. वर्तमान नोड और उसके पैरेंट पर एकल ट्री रोटेशन निष्पादित करें।

(यह चौथे ऑपरेशन की उपस्थिति है, जो एक्सेस के समय ट्री को पुनर्व्यवस्थित करता है, जो इसे गतिशील ऑप्टिमलिटी समस्या बनाता है।)

प्रत्येक पहुंच के लिए, हमारा बीएसटी एल्गोरिदम उपरोक्त परिचालनों के किसी भी अनुक्रम को तब तक निष्पादित कर सकता है जब तक कि सूचक अंततः लक्ष्य मान x वाले नोड पर समाप्त न हो जाए।_i. किसी दिए गए गतिशील बीएसटी एल्गोरिदम को एक्सेस के अनुक्रम को निष्पादित करने में लगने वाला समय उस अनुक्रम के समय किए गए ऐसे ऑपरेशनों की कुल संख्या के समान है। अवयवों के किसी भी समुच्चय पर पहुंच के किसी भी क्रम को देखते हुए, उन पहुंचों को निष्पादित करने के लिए कुछ न्यूनतम कुल संचालन की आवश्यकता होती है। हम इस न्यूनतम के निकट पहुंचना चाहेंगे.

चूँकि एक्सेस अनुक्रम क्या होगा, इसकी पूर्व जानकारी के बिना इस एल्गोरिदम को प्रयुक्त करना असंभव है, हम ओपीटी (x) को एक्सेस अनुक्रम x के लिए किए जाने वाले संचालन की संख्या के रूप में परिभाषित कर सकते हैं, और हम कह सकते हैं कि एल्गोरिदम है गतिशील सर्वोत्तमता यदि, किसी भी x के लिए, यह समय में बिग ओ अंकन (ओपीटी (एक्स)) में x प्रदर्शन करता है (अर्थात, इसका निरंतर प्रतिस्पर्धी अनुपात है)।

कई डेटा संरचनाओं में यह गुण होने का अनुमान लगाया गया है, किन्तु कोई भी सिद्ध नहीं हुआ है। यह संवृत समस्या है कि क्या इस मॉडल में गतिशील रूप से सर्वोत्तम डेटा संरचना उपस्थित है।

स्पले ट्री

Main article: सिप्ली ट्री

स्प्ले ट्री बाइनरी सर्च ट्री का रूप है जिसका आविष्कार 1985 में डैनियल स्लिएटर और रॉबर्ट टार्जन द्वारा किया गया था, जिस पर मानक सर्च ट्री ऑपरेशन चलते हैं। $O(\log(n))$ परिशोधित समय. इसे आवश्यक अर्थों में गतिशील सर्वोत्तमता होने का अनुमान लगाया गया है। ऐसा माना जाता है कि स्प्ले ट्री समय O(OPT(X)) में किसी भी पर्याप्त लंबे एक्सेस अनुक्रम X को निष्पादित करता है।

टैंगो ट्री

Main article: टैंगो ट्री

टैंगो ट्री 2004 में एरिक डेमाइन और अन्य द्वारा प्रस्तावित डेटा संरचना है जो समय में किसी भी पर्याप्त-लंबे एक्सेस अनुक्रम x को निष्पादित करने के लिए सिद्ध हुई है। $O(\log \log n\operatorname {OPT} (X))$. चूँकि यह गतिशील रूप से सर्वोत्तम नहीं है, किन्तु इसका प्रतिस्पर्धी अनुपात $\log \log n$ n के उचित मूल्यों के लिए अभी भी बहुत छोटा है।

अन्य परिणाम

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

इंटरलीव निचली सीमा गतिशील सर्वोत्तमता पर असम्बद्ध रूप से सर्वोत्तम है।

यह भी देखें

• ट्री डेटा संरचना
• स्पले ट्री
• टैंगो ट्री
• बाइनरी सर्च ट्री की ज्यामिति
• निचली सीमा को इंटरलीव करें

टिप्पणियाँ

[Category:Search tre