ऑप्टिमल बाइनरी सर्च ट्री: Difference between revisions

Revision as of 12:44, 19 July 2023

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

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

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

स्थैतिक इष्टतमता

परिभाषा

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

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

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

1971 में, नुथ ने अपेक्षाकृत सीधा गतिशील प्रोग्रामिंग एल्गोरिदम प्रकाशित किया जो केवल O(n) में सांख्यिकीय रूप से इष्टतम पेड़ का निर्माण करने में सक्षम था।²) समय.^[2]इस कार्य में, नथ ने 1958 में एडगर गिल्बर्ट और एडवर्ड एफ. मूर द्वारा प्रस्तुत गतिशील प्रोग्रामिंग एल्गोरिदम का विस्तार और सुधार किया।^[4] गिल्बर्ट और मूर का एल्गोरिदम आवश्यक है $O(n^{3})$ समय और $O(n^{2})$ स्थान और इष्टतम बाइनरी खोज वृक्ष निर्माण के विशेष मामले के लिए डिज़ाइन किया गया था (इष्टतम वर्णमाला वृक्ष समस्या के रूप में जाना जाता है)।^[5]) जो केवल असफल खोजों की संभावना पर विचार करता है, अर्थात, ${\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$ काफी बड़ा है.^[6] नुथ के नियमों को निम्नलिखित के रूप में देखा जा सकता है:

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

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

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

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

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

  ${\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)}$ ), समान आवृत्ति वितरण के लिए काफी खराब प्रदर्शन करेगा।^[6]

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

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

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}}

यह सन्निकटन बहुत करीब है.^[6]

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

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

गतिशील इष्टतमता

Unsolved problem in computer science:

Do splay trees perform as well as any other binary search tree algorithm?

(more unsolved problems in computer science)

परिभाषा

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

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

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

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

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

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

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

पेड़ों को बिखेरें

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

टैंगो पेड़

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

अन्य परिणाम

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

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

यह भी देखें

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

↑ Tremblay, Jean-Paul; Cheston, Grant A. (2001). ऑब्जेक्ट-ओरिएंटेड डोमेन में डेटा संरचनाएं और सॉफ़्टवेयर विकास. Eiffel Edition/Prentice Hall. ISBN 978-0-13-787946-5.
↑ ^2.0 ^2.1 ^2.2 Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica, 1 (1): 14–25, doi:10.1007/BF00264289, S2CID 62777263
↑ ^3.0 ^3.1 Nagaraj, S. V. (1997-11-30). "इष्टतम बाइनरी खोज पेड़". Theoretical Computer Science (in English). 188 (1): 1–44. doi:10.1016/S0304-3975(96)00320-9. ISSN 0304-3975. S2CID 33484183.
↑ Gilbert, E. N.; Moore, E. F. (July 1959). "परिवर्तनीय-लंबाई बाइनरी एनकोडिंग". Bell System Technical Journal (in English). 38 (4): 933–967. doi:10.1002/j.1538-7305.1959.tb01583.x.
↑ Hu, T. C.; Tucker, A. C. (December 1971). "इष्टतम कंप्यूटर खोज वृक्ष और चर-लंबाई वर्णमाला कोड". SIAM Journal on Applied Mathematics. 21 (4): 514–532. doi:10.1137/0121057. ISSN 0036-1399.
↑ ^6.0 ^6.1 ^6.2 ^6.3 ^6.4 ^6.5 Mehlhorn, Kurt (1975), "Nearly optimal binary search trees", Acta Informatica, 5 (4): 287–295, doi:10.1007/BF00264563, S2CID 17188103
↑ Knuth, Donald E. (1998), "Algorithm G (Garsia–Wachs algorithm for optimum binary trees)", The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison–Wesley, pp. 451–453. See also History and bibliography, pp. 453–454.
↑ ^8.0 ^8.1 ^8.2 ^8.3 Demaine, Erik D.; Harmon, Dion; Iacono, John; Patrascu, Mihai (2004), "Dynamic optimality—almost" (PDF), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 484–490, CiteSeerX 10.1.1.99.4964, doi:10.1109/FOCS.2004.23, ISBN 978-0-7695-2228-9
↑ ^9.0 ^9.1 Sleator, Daniel; Tarjan, Robert (1985), "Self-adjusting binary search trees", Journal of the ACM, 32 (3): 652–686, doi:10.1145/3828.3835, S2CID 1165848
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald; Stein, Clifford (2009). एल्गोरिदम का परिचय (PDF) (Third ed.). The MIT Press. p. 503. ISBN 978-0-262-03384-8. Retrieved 31 October 2017.
↑ Iacono, John (2013), "गतिशील इष्टतमता अनुमान की खोज में", arXiv:1306.0207 [cs.DS]

[Category:Search tre

[1] Tremblay, Jean-Paul; Cheston, Grant A. (2001). ऑब्जेक्ट-ओरिएंटेड डोमेन में डेटा संरचनाएं और सॉफ़्टवेयर विकास. Eiffel Edition/Prentice Hall. ISBN 978-0-13-787946-5.

[Knuth1971-2] 2.0 ^2.1 ^2.2 Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica, 1 (1): 14–25, doi:10.1007/BF00264289, S2CID 62777263

[:0-3] 3.0 ^3.1 Nagaraj, S. V. (1997-11-30). "इष्टतम बाइनरी खोज पेड़". Theoretical Computer Science (in English). 188 (1): 1–44. doi:10.1016/S0304-3975(96)00320-9. ISSN 0304-3975. S2CID 33484183.

[4] Gilbert, E. N.; Moore, E. F. (July 1959). "परिवर्तनीय-लंबाई बाइनरी एनकोडिंग". Bell System Technical Journal (in English). 38 (4): 933–967. doi:10.1002/j.1538-7305.1959.tb01583.x.

[5] Hu, T. C.; Tucker, A. C. (December 1971). "इष्टतम कंप्यूटर खोज वृक्ष और चर-लंबाई वर्णमाला कोड". SIAM Journal on Applied Mathematics. 21 (4): 514–532. doi:10.1137/0121057. ISSN 0036-1399.

[Mehlhorm1975-6] 6.0 ^6.1 ^6.2 ^6.3 ^6.4 ^6.5 Mehlhorn, Kurt (1975), "Nearly optimal binary search trees", Acta Informatica, 5 (4): 287–295, doi:10.1007/BF00264563, S2CID 17188103

[7] Knuth, Donald E. (1998), "Algorithm G (Garsia–Wachs algorithm for optimum binary trees)", The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison–Wesley, pp. 451–453. See also History and bibliography, pp. 453–454.

[Demaine2004-8] 8.0 ^8.1 ^8.2 ^8.3 Demaine, Erik D.; Harmon, Dion; Iacono, John; Patrascu, Mihai (2004), "Dynamic optimality—almost" (PDF), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 484–490, CiteSeerX 10.1.1.99.4964, doi:10.1109/FOCS.2004.23, ISBN 978-0-7695-2228-9

[SplayTrees-9] 9.0 ^9.1 Sleator, Daniel; Tarjan, Robert (1985), "Self-adjusting binary search trees", Journal of the ACM, 32 (3): 652–686, doi:10.1145/3828.3835, S2CID 1165848

[10] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald; Stein, Clifford (2009). एल्गोरिदम का परिचय (PDF) (Third ed.). The MIT Press. p. 503. ISBN 978-0-262-03384-8. Retrieved 31 October 2017.

[Iacono2013-11] Iacono, John (2013), "गतिशील इष्टतमता अनुमान की खोज में", arXiv:1306.0207 [cs.DS]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 {{Short description|Computer science concept}}
-[[कंप्यूटर विज्ञान]] में, एक इष्टतम बाइनरी सर्च ट्री (ऑप्टिमल बीएसटी), जिसे कभी-कभी वजन-संतुलित बाइनरी ट्री भी कहा जाता है,<ref>{{cite book |first1=Jean-Paul |last1=Tremblay |first2=Grant A. |last2=Cheston |title=ऑब्जेक्ट-ओरिएंटेड डोमेन में डेटा संरचनाएं और सॉफ़्टवेयर विकास|publisher=Eiffel Edition/Prentice Hall |year=2001 |isbn=978-0-13-787946-5}}</ref> एक [[बाइनरी सर्च ट्री]] है जो एक्सेस के दिए गए अनुक्रम (या एक्सेस संभावनाओं) के लिए सबसे छोटा संभव खोज समय (या [[अपेक्षित मूल्य]]) प्रदान करता है। इष्टतम बीएसटी को आम तौर पर दो प्रकारों में विभाजित किया जाता है: स्थिर और गतिशील।
+[[कंप्यूटर विज्ञान]] में, इष्टतम बाइनरी सर्च ट्री (ऑप्टिमल बीएसटी), जिसे कभी-कभी वजन-संतुलित बाइनरी ट्री भी कहा जाता है,<ref>{{cite book |first1=Jean-Paul |last1=Tremblay |first2=Grant A. |last2=Cheston |title=ऑब्जेक्ट-ओरिएंटेड डोमेन में डेटा संरचनाएं और सॉफ़्टवेयर विकास|publisher=Eiffel Edition/Prentice Hall |year=2001 |isbn=978-0-13-787946-5}}</ref> [[बाइनरी सर्च ट्री]] है जो एक्सेस के दिए गए अनुक्रम (या एक्सेस संभावनाओं) के लिए सबसे छोटा संभव खोज समय (या [[अपेक्षित मूल्य]]) प्रदान करता है। इष्टतम बीएसटी को आम तौर पर दो प्रकारों में विभाजित किया जाता है: स्थिर और गतिशील।
 स्थैतिक इष्टतमता समस्या में, पेड़ के निर्माण के बाद उसे संशोधित नहीं किया जा सकता है। इस मामले में, पेड़ के नोड्स का कुछ विशेष लेआउट मौजूद है जो दी गई पहुंच संभावनाओं के लिए सबसे छोटा अपेक्षित खोज समय प्रदान करता है। तत्वों की पहुंच संभावनाओं पर जानकारी देते हुए सांख्यिकीय रूप से इष्टतम पेड़ का निर्माण या अनुमान लगाने के लिए विभिन्न एल्गोरिदम मौजूद हैं।
-गतिशील इष्टतमता समस्या में, पेड़ को किसी भी समय संशोधित किया जा सकता है, आमतौर पर पेड़ के घूमने की अनुमति देकर। ऐसा माना जाता है कि पेड़ की जड़ से शुरू होने वाला एक कर्सर होता है जिसे वह स्थानांतरित कर सकता है या संशोधन करने के लिए उपयोग कर सकता है। इस मामले में, इन परिचालनों का कुछ न्यूनतम-लागत अनुक्रम मौजूद है जो कर्सर को लक्ष्य पहुंच अनुक्रम में प्रत्येक नोड पर क्रम से जाने का कारण बनता है। सभी मामलों में #डायनामिक ऑप्टिमिटी ट्री की तुलना में [[ बिखरा हुआ पेड़ ]] में निरंतर [[प्रतिस्पर्धी अनुपात]] होने का अनुमान लगाया गया है, हालांकि यह अभी तक साबित नहीं हुआ है।
+गतिशील इष्टतमता समस्या में, पेड़ को किसी भी समय संशोधित किया जा सकता है, आमतौर पर पेड़ के घूमने की अनुमति देकर। ऐसा माना जाता है कि पेड़ की जड़ से शुरू होने वाला कर्सर होता है जिसे वह स्थानांतरित कर सकता है या संशोधन करने के लिए उपयोग कर सकता है। इस मामले में, इन परिचालनों का कुछ न्यूनतम-लागत अनुक्रम मौजूद है जो कर्सर को लक्ष्य पहुंच अनुक्रम में प्रत्येक नोड पर क्रम से जाने का कारण बनता है। सभी मामलों में #डायनामिक ऑप्टिमिटी ट्री की तुलना में [[ बिखरा हुआ पेड़ |बिखरा हुआ पेड़]] में निरंतर [[प्रतिस्पर्धी अनुपात]] होने का अनुमान लगाया गया है, हालांकि यह अभी तक साबित नहीं हुआ है।
 == स्थैतिक इष्टतमता ==
@@ Line 10: / Line 10: @@
 === परिभाषा ===
-डोनाल्ड ई. नुथ द्वारा परिभाषित स्थैतिक इष्टतमता समस्या में,<ref name="Knuth1971">{{Citation |first1=Donald E. |last1=Knuth |title=Optimum binary search trees |journal=Acta Informatica |volume=1 |issue=1 |pages=14–25 |year=1971 |doi=10.1007/BF00264289 |s2cid=62777263 }}</ref> हमें का एक सेट दिया गया है {{mvar|n}} आदेशित तत्व और का एक सेट <math>2n+1</math> सम्भावनाएँ हम तत्वों को निरूपित करेंगे <math>a_1</math> द्वारा <math>a_n</math> और संभावनाएँ <math>A_1</math> द्वारा <math>A_n</math> और <math>B_0</math> द्वारा <math>B_n</math>. <math>A_i</math> तत्व के लिए खोज किये जाने की संभावना है <math>a_i</math> (या सफल खोज).<ref name=":0">{{Cite journal|last=Nagaraj|first=S. V.|date=1997-11-30|title=इष्टतम बाइनरी खोज पेड़|url=https://www.sciencedirect.com/science/article/pii/S0304397596003209|journal=Theoretical Computer Science|language=en|volume=188|issue=1|pages=1–44|doi=10.1016/S0304-3975(96)00320-9|s2cid=33484183 |issn=0304-3975}}</ref> के लिए <math>1 \le i < n</math>, <math>B_i</math> के बीच किसी तत्व की खोज होने की संभावना है <math>a_i</math> और <math>a_{i+1}</math>(या असफल खोज),<ref name=":0" /> <math>B_0</math> किसी तत्व के लिए खोज किए जाने की संभावना बिल्कुल कम है <math>a_1</math>, और <math>B_n</math> किसी तत्व के लिए खोज किए जाने की संभावना उससे कहीं अधिक है <math>a_n</math>. इन <math>2n+1</math> संभावनाएँ सभी संभावित खोजों को कवर करती हैं, और इसलिए एक तक जुड़ जाती हैं।
+डोनाल्ड ई. नुथ द्वारा परिभाषित स्थैतिक इष्टतमता समस्या में,<ref name="Knuth1971">{{Citation |first1=Donald E. |last1=Knuth |title=Optimum binary search trees |journal=Acta Informatica |volume=1 |issue=1 |pages=14–25 |year=1971 |doi=10.1007/BF00264289 |s2cid=62777263 }}</ref> हमें का सेट दिया गया है {{mvar|n}} आदेशित तत्व और का सेट <math>2n+1</math> सम्भावनाएँ हम तत्वों को निरूपित करेंगे <math>a_1</math> द्वारा <math>a_n</math> और संभावनाएँ <math>A_1</math> द्वारा <math>A_n</math> और <math>B_0</math> द्वारा <math>B_n</math>. <math>A_i</math> तत्व के लिए खोज किये जाने की संभावना है <math>a_i</math> (या सफल खोज).<ref name=":0">{{Cite journal|last=Nagaraj|first=S. V.|date=1997-11-30|title=इष्टतम बाइनरी खोज पेड़|url=https://www.sciencedirect.com/science/article/pii/S0304397596003209|journal=Theoretical Computer Science|language=en|volume=188|issue=1|pages=1–44|doi=10.1016/S0304-3975(96)00320-9|s2cid=33484183 |issn=0304-3975}}</ref> के लिए <math>1 \le i < n</math>, <math>B_i</math> के बीच किसी तत्व की खोज होने की संभावना है <math>a_i</math> और <math>a_{i+1}</math>(या असफल खोज),<ref name=":0" /> <math>B_0</math> किसी तत्व के लिए खोज किए जाने की संभावना बिल्कुल कम है <math>a_1</math>, और <math>B_n</math> किसी तत्व के लिए खोज किए जाने की संभावना उससे कहीं अधिक है <math>a_n</math>. इन <math>2n+1</math> संभावनाएँ सभी संभावित खोजों को कवर करती हैं, और इसलिए तक जुड़ जाती हैं।
-स्थैतिक इष्टतमता समस्या बाइनरी खोज वृक्ष को खोजने की [[अनुकूलन समस्या]] है जो अपेक्षित खोज समय को कम करती है, जिसे देखते हुए <math>2n+1</math> सम्भावनाएँ के एक सेट पर संभावित पेड़ों की संख्या के रूप में {{mvar|n}}तत्व है <math>{2n \choose n}\frac{1}{n+1}</math>,<ref name="Knuth1971" />जो कि घातांकीय है {{mvar|n}}, क्रूर-बल खोज आमतौर पर एक व्यवहार्य समाधान नहीं है।
+स्थैतिक इष्टतमता समस्या बाइनरी खोज वृक्ष को खोजने की [[अनुकूलन समस्या]] है जो अपेक्षित खोज समय को कम करती है, जिसे देखते हुए <math>2n+1</math> सम्भावनाएँ के सेट पर संभावित पेड़ों की संख्या के रूप में {{mvar|n}}तत्व है <math>{2n \choose n}\frac{1}{n+1}</math>,<ref name="Knuth1971" />जो कि घातांकीय है {{mvar|n}}, क्रूर-बल खोज आमतौर पर व्यवहार्य समाधान नहीं है।
 === नुथ का [[गतिशील प्रोग्रामिंग]] एल्गोरिदम ===
-में, नुथ ने एक अपेक्षाकृत सीधा गतिशील प्रोग्रामिंग एल्गोरिदम प्रकाशित किया जो केवल O(n) में सांख्यिकीय रूप से इष्टतम पेड़ का निर्माण करने में सक्षम था।<sup>2</sup>) समय.<ref name="Knuth1971" />इस कार्य में, नथ ने 1958 में [[एडगर गिल्बर्ट]] और एडवर्ड एफ. मूर द्वारा प्रस्तुत गतिशील प्रोग्रामिंग एल्गोरिदम का विस्तार और सुधार किया।<ref>{{Cite journal|last1=Gilbert|first1=E. N.|last2=Moore|first2=E. F.|date=July 1959|title=परिवर्तनीय-लंबाई बाइनरी एनकोडिंग|url=https://ieeexplore.ieee.org/document/6768523|journal=Bell System Technical Journal|language=en|volume=38|issue=4|pages=933–967|doi=10.1002/j.1538-7305.1959.tb01583.x}}</ref> गिल्बर्ट और मूर का एल्गोरिदम आवश्यक है <math>O(n^3)</math> समय और <math>O(n^2)</math> स्थान और इष्टतम बाइनरी खोज वृक्ष निर्माण के एक विशेष मामले के लिए डिज़ाइन किया गया था (इष्टतम वर्णमाला वृक्ष समस्या के रूप में जाना जाता है)।<ref>{{Cite journal|last1=Hu|first1=T. C.|last2=Tucker|first2=A. C.|date=December 1971|title=इष्टतम कंप्यूटर खोज वृक्ष और चर-लंबाई वर्णमाला कोड|url=http://dx.doi.org/10.1137/0121057|journal=SIAM Journal on Applied Mathematics|volume=21|issue=4|pages=514–532|doi=10.1137/0121057|issn=0036-1399}}</ref>) जो केवल असफल खोजों की संभावना पर विचार करता है, अर्थात, <math display="inline">\sum _{i = 1}^{n} A_i = 0</math>. नुथ का कार्य निम्नलिखित अंतर्दृष्टि पर निर्भर था: स्थैतिक इष्टतमता समस्या [[इष्टतम उपसंरचना]] को प्रदर्शित करती है; अर्थात्, यदि एक निश्चित वृक्ष किसी दिए गए संभाव्यता वितरण के लिए सांख्यिकीय रूप से इष्टतम है, तो उसके बाएँ और दाएँ उपवृक्ष भी वितरण के उनके उपयुक्त उपसमूहों के लिए सांख्यिकीय रूप से इष्टतम होने चाहिए (जड़ों की एकरसता संपत्ति के रूप में जाना जाता है)।
+में, नुथ ने अपेक्षाकृत सीधा गतिशील प्रोग्रामिंग एल्गोरिदम प्रकाशित किया जो केवल O(n) में सांख्यिकीय रूप से इष्टतम पेड़ का निर्माण करने में सक्षम था।<sup>2</sup>) समय.<ref name="Knuth1971" />इस कार्य में, नथ ने 1958 में [[एडगर गिल्बर्ट]] और एडवर्ड एफ. मूर द्वारा प्रस्तुत गतिशील प्रोग्रामिंग एल्गोरिदम का विस्तार और सुधार किया।<ref>{{Cite journal|last1=Gilbert|first1=E. N.|last2=Moore|first2=E. F.|date=July 1959|title=परिवर्तनीय-लंबाई बाइनरी एनकोडिंग|url=https://ieeexplore.ieee.org/document/6768523|journal=Bell System Technical Journal|language=en|volume=38|issue=4|pages=933–967|doi=10.1002/j.1538-7305.1959.tb01583.x}}</ref> गिल्बर्ट और मूर का एल्गोरिदम आवश्यक है <math>O(n^3)</math> समय और <math>O(n^2)</math> स्थान और इष्टतम बाइनरी खोज वृक्ष निर्माण के विशेष मामले के लिए डिज़ाइन किया गया था (इष्टतम वर्णमाला वृक्ष समस्या के रूप में जाना जाता है)।<ref>{{Cite journal|last1=Hu|first1=T. C.|last2=Tucker|first2=A. C.|date=December 1971|title=इष्टतम कंप्यूटर खोज वृक्ष और चर-लंबाई वर्णमाला कोड|url=http://dx.doi.org/10.1137/0121057|journal=SIAM Journal on Applied Mathematics|volume=21|issue=4|pages=514–532|doi=10.1137/0121057|issn=0036-1399}}</ref>) जो केवल असफल खोजों की संभावना पर विचार करता है, अर्थात, <math display="inline">\sum _{i = 1}^{n} A_i = 0</math>. नुथ का कार्य निम्नलिखित अंतर्दृष्टि पर निर्भर था: स्थैतिक इष्टतमता समस्या [[इष्टतम उपसंरचना]] को प्रदर्शित करती है; अर्थात्, यदि निश्चित वृक्ष किसी दिए गए संभाव्यता वितरण के लिए सांख्यिकीय रूप से इष्टतम है, तो उसके बाएँ और दाएँ उपवृक्ष भी वितरण के उनके उपयुक्त उपसमूहों के लिए सांख्यिकीय रूप से इष्टतम होने चाहिए (जड़ों की एकरसता संपत्ति के रूप में जाना जाता है)।
-इसे देखने के लिए, विचार करें कि नथ एक पेड़ की भारित पथ लंबाई को क्या कहते हैं। n तत्वों के एक पेड़ की भारित पथ लंबाई सभी की लंबाई का योग है <math>2n+1</math> संभावित खोज पथ, उनकी संबंधित संभावनाओं के आधार पर भारित। न्यूनतम भारित पथ लंबाई वाला पेड़, परिभाषा के अनुसार, सांख्यिकीय रूप से इष्टतम है।
+इसे देखने के लिए, विचार करें कि नथ पेड़ की भारित पथ लंबाई को क्या कहते हैं। n तत्वों के पेड़ की भारित पथ लंबाई सभी की लंबाई का योग है <math>2n+1</math> संभावित खोज पथ, उनकी संबंधित संभावनाओं के आधार पर भारित। न्यूनतम भारित पथ लंबाई वाला पेड़, परिभाषा के अनुसार, सांख्यिकीय रूप से इष्टतम है।
-लेकिन भारित पथ लंबाई में एक दिलचस्प गुण होता है। मान लीजिए E एक बाइनरी ट्री की भारित पथ लंबाई है, {{mvar|E<sub>L</sub>}} इसके बाएँ उपवृक्ष की भारित पथ लंबाई हो, और {{mvar|E<sub>R</sub>}} इसके दाएँ उपवृक्ष की भारित पथ लंबाई हो। यह भी मान लें कि W पेड़ की सभी संभावनाओं का योग है। ध्यान दें कि जब कोई भी उपवृक्ष जड़ से जुड़ा होता है, तो उसके प्रत्येक तत्व की गहराई (और इस प्रकार उसके प्रत्येक खोज पथ) में एक की वृद्धि होती है। यह भी ध्यान रखें कि जड़ की गहराई भी एक हो। इसका मतलब यह है कि एक पेड़ और उसके दो उपवृक्षों के बीच भारित पथ की लंबाई का अंतर पेड़ में हर एक संभावना का योग है, जिससे निम्नलिखित पुनरावृत्ति होती है:
+लेकिन भारित पथ लंबाई में दिलचस्प गुण होता है। मान लीजिए E बाइनरी ट्री की भारित पथ लंबाई है, {{mvar|E<sub>L</sub>}} इसके बाएँ उपवृक्ष की भारित पथ लंबाई हो, और {{mvar|E<sub>R</sub>}} इसके दाएँ उपवृक्ष की भारित पथ लंबाई हो। यह भी मान लें कि W पेड़ की सभी संभावनाओं का योग है। ध्यान दें कि जब कोई भी उपवृक्ष जड़ से जुड़ा होता है, तो उसके प्रत्येक तत्व की गहराई (और इस प्रकार उसके प्रत्येक खोज पथ) में की वृद्धि होती है। यह भी ध्यान रखें कि जड़ की गहराई भी हो। इसका मतलब यह है कि पेड़ और उसके दो उपवृक्षों के बीच भारित पथ की लंबाई का अंतर पेड़ में हर संभावना का योग है, जिससे निम्नलिखित पुनरावृत्ति होती है:
 :<math>E = E_L + E_R + W</math>
-यह पुनरावृत्ति एक प्राकृतिक गतिशील प्रोग्रामिंग समाधान की ओर ले जाती है। होने देना <math>E_{ij}</math> बीच के सभी मानों के लिए सांख्यिकीय रूप से इष्टतम खोज वृक्ष की भारित पथ लंबाई हो {{mvar|a<sub>i</sub>}} और {{mvar|a<sub>j</sub>}}, होने देना <math>W_{ij}</math> उस पेड़ का कुल वजन हो, और रहने दो <math>R_{ij}</math> इसकी जड़ का सूचकांक बनें. एल्गोरिथ्म निम्नलिखित सूत्रों का उपयोग करके बनाया जा सकता है:
+यह पुनरावृत्ति प्राकृतिक गतिशील प्रोग्रामिंग समाधान की ओर ले जाती है। होने देना <math>E_{ij}</math> बीच के सभी मानों के लिए सांख्यिकीय रूप से इष्टतम खोज वृक्ष की भारित पथ लंबाई हो {{mvar|a<sub>i</sub>}} और {{mvar|a<sub>j</sub>}}, होने देना <math>W_{ij}</math> उस पेड़ का कुल वजन हो, और रहने दो <math>R_{ij}</math> इसकी जड़ का सूचकांक बनें. एल्गोरिथ्म निम्नलिखित सूत्रों का उपयोग करके बनाया जा सकता है:
 :<math>\begin{align}
@@ Line 30: / Line 30: @@
 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{align}</math>
-इस एल्गोरिथ्म का सरल कार्यान्वयन वास्तव में O(n) लेता है<sup>3</sup>) समय, लेकिन नथ के पेपर में कुछ अतिरिक्त अवलोकन शामिल हैं जिनका उपयोग केवल O(n) लेकर एक संशोधित एल्गोरिदम तैयार करने के लिए किया जा सकता है<sup>2</sup>) समय.
+इस एल्गोरिथ्म का सरल कार्यान्वयन वास्तव में O(n) लेता है<sup>3</sup>) समय, लेकिन नथ के पेपर में कुछ अतिरिक्त अवलोकन शामिल हैं जिनका उपयोग केवल O(n) लेकर संशोधित एल्गोरिदम तैयार करने के लिए किया जा सकता है<sup>2</sup>) समय.
 अपने गतिशील प्रोग्रामिंग एल्गोरिदम के अलावा, नुथ ने इष्टतम बाइनरी खोज पेड़ों का लगभग (अनुमान) उत्पादन करने के लिए दो अनुमान (या नियम) प्रस्तावित किए। लगभग इष्टतम बाइनरी खोज पेड़ों का अध्ययन करना आवश्यक था क्योंकि नुथ के एल्गोरिथ्म समय और स्थान की जटिलता निषेधात्मक हो सकती है <math>n</math> काफी बड़ा है.<ref name="Mehlhorm1975">{{Citation|last1=Mehlhorn|first1=Kurt|title=Nearly optimal binary search trees|url=http://edoc.mpg.de/344677|journal=Acta Informatica|volume=5|issue=4|pages=287–295|year=1975|doi=10.1007/BF00264563|s2cid=17188103}}</ref> नुथ के नियमों को निम्नलिखित के रूप में देखा जा सकता है:
@@ Line 44: / Line 44: @@
 जबकि ओ(एन<sup>2</sup>) नथ के एल्गोरिदम द्वारा लिया गया समय जानवर-बल खोज के लिए आवश्यक घातीय समय से काफी बेहतर है, यह अभी भी व्यावहारिक होने के लिए बहुत धीमा है जब पेड़ में तत्वों की संख्या बहुत बड़ी है।
-में, कर्ट मेहलहॉर्न ने नुथ के नियमों के संबंध में महत्वपूर्ण गुणों को साबित करने वाला एक पेपर प्रकाशित किया। मेहलहॉर्न के प्रमुख परिणाम बताते हैं कि नुथ के अनुमानों में से केवल एक (नियम II) हमेशा लगभग इष्टतम बाइनरी खोज पेड़ उत्पन्न करता है। दूसरी ओर, रूट-मैक्स नियम अक्सर निम्नलिखित सरल तर्क के आधार पर बहुत खराब खोज वृक्षों का कारण बन सकता है।<ref name="Mehlhorm1975" />  होने देना
+में, कर्ट मेहलहॉर्न ने नुथ के नियमों के संबंध में महत्वपूर्ण गुणों को साबित करने वाला पेपर प्रकाशित किया। मेहलहॉर्न के प्रमुख परिणाम बताते हैं कि नुथ के अनुमानों में से केवल (नियम II) हमेशा लगभग इष्टतम बाइनरी खोज पेड़ उत्पन्न करता है। दूसरी ओर, रूट-मैक्स नियम अक्सर निम्नलिखित सरल तर्क के आधार पर बहुत खराब खोज वृक्षों का कारण बन सकता है।<ref name="Mehlhorm1975" /> होने देना
    <math display="inline">\begin{align}
@@ Line 58: / Line 58: @@
   <math display="inline">\begin{align}
-P &= \sum_{i=1}^{n} A_i(a_i + 1) + \sum_{j=1}^{n} B_j b_j \\
+ 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 \\
+ &=  \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}.
+ &\geqq 2^{-k} \sum_{i=1}^{n} i = 2^{-k} \frac{n(n+1)}{2}\geqq \frac{n}{2}.
-\end{align}
+ \end{align}
-</math> इस प्रकार, रूट-मैक्स नियम के अनुसार परिणामी पेड़ एक ऐसा पेड़ होगा जो केवल दाईं ओर बढ़ता है (पेड़ के सबसे गहरे स्तर को छोड़कर), और बाईं ओर हमेशा टर्मिनल नोड्स होंगे। इस पेड़ की पथ लंबाई से घिरा हुआ है <math display="inline">\Omega (\frac{n}{2})</math> और, जब एक संतुलित खोज वृक्ष के साथ तुलना की जाती है (पथ से घिरा हुआ)। <math display="inline">O (2 \log n)</math>), समान आवृत्ति वितरण के लिए काफी खराब प्रदर्शन करेगा।<ref name="Mehlhorm1975" />
+ </math> इस प्रकार, रूट-मैक्स नियम के अनुसार परिणामी पेड़ ऐसा पेड़ होगा जो केवल दाईं ओर बढ़ता है (पेड़ के सबसे गहरे स्तर को छोड़कर), और बाईं ओर हमेशा टर्मिनल नोड्स होंगे। इस पेड़ की पथ लंबाई से घिरा हुआ है <math display="inline">\Omega (\frac{n}{2})</math> और, जब संतुलित खोज वृक्ष के साथ तुलना की जाती है (पथ से घिरा हुआ)। <math display="inline">O (2 \log n)</math>), समान आवृत्ति वितरण के लिए काफी खराब प्रदर्शन करेगा।<ref name="Mehlhorm1975" />
-इसके अलावा, मेहलहॉर्न ने नुथ के काम में सुधार किया और एक बहुत ही सरल एल्गोरिथ्म पेश किया जो नियम II का उपयोग करता है और केवल सांख्यिकीय रूप से इष्टतम पेड़ के प्रदर्शन का बारीकी से अनुमान लगाता है। {{tmath|O(n)}} समय।<ref name="Mehlhorm1975" />एल्गोरिथ्म बाएँ और दाएँ उपवृक्षों के कुल वजन (संभावना द्वारा) को सबसे निकट से संतुलित करने के लिए पेड़ की जड़ को चुनकर द्विभाजन नियम के समान विचार का पालन करता है। और फिर रणनीति को प्रत्येक उपवृक्ष पर पुनरावर्ती रूप से लागू किया जाता है।
+इसके अलावा, मेहलहॉर्न ने नुथ के काम में सुधार किया और बहुत ही सरल एल्गोरिथ्म पेश किया जो नियम II का उपयोग करता है और केवल सांख्यिकीय रूप से इष्टतम पेड़ के प्रदर्शन का बारीकी से अनुमान लगाता है। {{tmath|O(n)}} समय।<ref name="Mehlhorm1975" />एल्गोरिथ्म बाएँ और दाएँ उपवृक्षों के कुल वजन (संभावना द्वारा) को सबसे निकट से संतुलित करने के लिए पेड़ की जड़ को चुनकर द्विभाजन नियम के समान विचार का पालन करता है। और फिर रणनीति को प्रत्येक उपवृक्ष पर पुनरावर्ती रूप से लागू किया जाता है।
-यह रणनीति एक अच्छा सन्निकटन उत्पन्न करती है, इसे सहज रूप से देखा जा सकता है, यह देखते हुए कि किसी भी पथ के साथ उपवृक्षों का वजन ज्यामितीय रूप से घटते क्रम के बहुत करीब होता है। वास्तव में, यह रणनीति एक पेड़ उत्पन्न करती है जिसकी भारित पथ लंबाई अधिकतम होती है
+यह रणनीति अच्छा सन्निकटन उत्पन्न करती है, इसे सहज रूप से देखा जा सकता है, यह देखते हुए कि किसी भी पथ के साथ उपवृक्षों का वजन ज्यामितीय रूप से घटते क्रम के बहुत करीब होता है। वास्तव में, यह रणनीति पेड़ उत्पन्न करती है जिसकी भारित पथ लंबाई अधिकतम होती है
 :<math>2+(1 - \log(\sqrt{5} - 1))^{-1}H = 2 + \frac H {1 - \log(\sqrt{5} - 1)}</math>
@@ Line 76: / Line 76: @@
 ===हू-टकर और गार्सिया-वाच एल्गोरिदम===
 {{main|Garsia–Wachs algorithm}}
-विशेष मामले में कि सभी <math>A_i</math> मान शून्य हैं, इष्टतम वृक्ष समय में पाया जा सकता है <math>O(n\log n)</math>. यह पहली बार टी. सी. हू और [[एलन टकर]] द्वारा 1971 में प्रकाशित एक पेपर में सिद्ध किया गया था। गार्सिया और वाच्स द्वारा बाद में सरलीकरण, गार्सिया-वाच एल्गोरिदम, समान क्रम में समान तुलना करता है। एल्गोरिथ्म एक [[लालची एल्गोरिदम]] का उपयोग करके एक पेड़ का निर्माण करता है जिसमें प्रत्येक पत्ते के लिए इष्टतम ऊंचाई होती है, लेकिन क्रम से बाहर है, और फिर उसी ऊंचाई के साथ एक और बाइनरी खोज पेड़ का निर्माण करता है।<ref>{{citation
+विशेष मामले में कि सभी <math>A_i</math> मान शून्य हैं, इष्टतम वृक्ष समय में पाया जा सकता है <math>O(n\log n)</math>. यह पहली बार टी. सी. हू और [[एलन टकर]] द्वारा 1971 में प्रकाशित पेपर में सिद्ध किया गया था। गार्सिया और वाच्स द्वारा बाद में सरलीकरण, गार्सिया-वाच एल्गोरिदम, समान क्रम में समान तुलना करता है। एल्गोरिथ्म [[लालची एल्गोरिदम]] का उपयोग करके पेड़ का निर्माण करता है जिसमें प्रत्येक पत्ते के लिए इष्टतम ऊंचाई होती है, लेकिन क्रम से बाहर है, और फिर उसी ऊंचाई के साथ और बाइनरी खोज पेड़ का निर्माण करता है।<ref>{{citation
   | last = Knuth | first = Donald E. | author-link = Donald Knuth
   | contribution = Algorithm G (Garsia–Wachs algorithm for optimum binary trees)
@@ Line 91: / Line 91: @@
 === परिभाषा ===
-गतिशील इष्टतमता की कई अलग-अलग परिभाषाएँ हैं, जिनमें से सभी प्रभावी रूप से रनिंग-टाइम के संदर्भ में एक स्थिर कारक के बराबर हैं।<ref name="Demaine2004">{{Citation |first1=Erik D. |last1=Demaine |first2=Dion |last2=Harmon |first3=John |last3=Iacono |first4=Mihai |last4=Patrascu |contribution=Dynamic optimality—almost |title=Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science |isbn=978-0-7695-2228-9 |pages=484–490 |year=2004 |doi=10.1109/FOCS.2004.23 |citeseerx=10.1.1.99.4964 |contribution-url=http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf}}</ref> इस समस्या को सबसे पहले [[डेनियल स्लेटर]] और [[रॉबर्ट टार्जन]] ने स्प्ले ट्रीज़ पर अपने पेपर में स्पष्ट रूप से पेश किया था,<ref name="SplayTrees">{{Citation |first1=Daniel |last1=Sleator |first2=Robert |last2=Tarjan |title=Self-adjusting binary search trees |journal=Journal of the ACM |volume=32 |issue=3 |pages=652–686 |year=1985 |doi=10.1145/3828.3835 |s2cid=1165848 }}</ref> लेकिन [[एरिक कल]] एट अल। इसका एक बहुत अच्छा औपचारिक विवरण दें।<ref name="Demaine2004" />
+गतिशील इष्टतमता की कई अलग-अलग परिभाषाएँ हैं, जिनमें से सभी प्रभावी रूप से रनिंग-टाइम के संदर्भ में स्थिर कारक के बराबर हैं।<ref name="Demaine2004">{{Citation |first1=Erik D. |last1=Demaine |first2=Dion |last2=Harmon |first3=John |last3=Iacono |first4=Mihai |last4=Patrascu |contribution=Dynamic optimality—almost |title=Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science |isbn=978-0-7695-2228-9 |pages=484–490 |year=2004 |doi=10.1109/FOCS.2004.23 |citeseerx=10.1.1.99.4964 |contribution-url=http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf}}</ref> इस समस्या को सबसे पहले [[डेनियल स्लेटर]] और [[रॉबर्ट टार्जन]] ने स्प्ले ट्रीज़ पर अपने पेपर में स्पष्ट रूप से पेश किया था,<ref name="SplayTrees">{{Citation |first1=Daniel |last1=Sleator |first2=Robert |last2=Tarjan |title=Self-adjusting binary search trees |journal=Journal of the ACM |volume=32 |issue=3 |pages=652–686 |year=1985 |doi=10.1145/3828.3835 |s2cid=1165848 }}</ref> लेकिन [[एरिक कल]] एट अल। इसका बहुत अच्छा औपचारिक विवरण दें।<ref name="Demaine2004" />
-गतिशील इष्टतमता समस्या में, हमें एक्सेस x का एक क्रम दिया गया है<sub>1</sub>, ..., एक्स<sub>m</sub> कुंजियों पर 1, ..., एन। प्रत्येक एक्सेस के लिए, हमें अपने BST के रूट पर एक [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] दिया जाता है और हम निम्नलिखित में से कोई भी ऑपरेशन करने के लिए पॉइंटर का उपयोग कर सकते हैं:
+गतिशील इष्टतमता समस्या में, हमें एक्सेस x का क्रम दिया गया है<sub>1</sub>, ..., एक्स<sub>m</sub> कुंजियों पर 1, ..., एन। प्रत्येक एक्सेस के लिए, हमें अपने BST के रूट पर [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] दिया जाता है और हम निम्नलिखित में से कोई भी ऑपरेशन करने के लिए पॉइंटर का उपयोग कर सकते हैं:
 # पॉइंटर को वर्तमान नोड के बाएँ चाइल्ड पर ले जाएँ।
@@ Line 104: / Line 104: @@
 प्रत्येक पहुंच के लिए, हमारा बीएसटी एल्गोरिदम उपरोक्त परिचालनों के किसी भी अनुक्रम को तब तक निष्पादित कर सकता है जब तक कि सूचक अंततः लक्ष्य मान x वाले नोड पर समाप्त न हो जाए।<sub>i</sub>. किसी दिए गए गतिशील बीएसटी एल्गोरिदम को एक्सेस के अनुक्रम को निष्पादित करने में लगने वाला समय उस अनुक्रम के दौरान किए गए ऐसे ऑपरेशनों की कुल संख्या के बराबर है। तत्वों के किसी भी सेट पर पहुंच के किसी भी क्रम को देखते हुए, उन पहुंचों को निष्पादित करने के लिए कुछ न्यूनतम कुल संचालन की आवश्यकता होती है। हम इस न्यूनतम के करीब पहुंचना चाहेंगे.
-हालांकि एक्सेस अनुक्रम क्या होगा, इसकी पूर्व जानकारी के बिना इस भगवान के एल्गोरिदम को लागू करना असंभव है, हम ओपीटी (एक्स) को एक्सेस अनुक्रम एक्स के लिए किए जाने वाले संचालन की संख्या के रूप में परिभाषित कर सकते हैं, और हम कह सकते हैं कि एक एल्गोरिदम # है गतिशील इष्टतमता यदि, किसी भी एक्स के लिए, यह समय में [[ बिग ओ अंकन ]] (ओपीटी (एक्स)) में एक्स प्रदर्शन करता है (अर्थात, इसका एक निरंतर प्रतिस्पर्धी अनुपात है)।<ref name="Demaine2004"/>
+हालांकि एक्सेस अनुक्रम क्या होगा, इसकी पूर्व जानकारी के बिना इस भगवान के एल्गोरिदम को लागू करना असंभव है, हम ओपीटी (एक्स) को एक्सेस अनुक्रम एक्स के लिए किए जाने वाले संचालन की संख्या के रूप में परिभाषित कर सकते हैं, और हम कह सकते हैं कि एल्गोरिदम # है गतिशील इष्टतमता यदि, किसी भी एक्स के लिए, यह समय में [[ बिग ओ अंकन |बिग ओ अंकन]] (ओपीटी (एक्स)) में एक्स प्रदर्शन करता है (अर्थात, इसका निरंतर प्रतिस्पर्धी अनुपात है)।<ref name="Demaine2004"/>
-कई डेटा संरचनाओं में यह गुण होने का अनुमान लगाया गया है, लेकिन कोई भी सिद्ध नहीं हुआ है। यह एक [[खुली समस्या]] है कि क्या इस मॉडल में गतिशील रूप से इष्टतम डेटा संरचना मौजूद है।
+कई डेटा संरचनाओं में यह गुण होने का अनुमान लगाया गया है, लेकिन कोई भी सिद्ध नहीं हुआ है। यह [[खुली समस्या]] है कि क्या इस मॉडल में गतिशील रूप से इष्टतम डेटा संरचना मौजूद है।
 === पेड़ों को बिखेरें ===
@@ Line 112: / Line 112: @@
 {{Main|Splay tree}}
-स्प्ले ट्री बाइनरी सर्च ट्री का एक रूप है जिसका आविष्कार 1985 में डैनियल स्लिएटर और रॉबर्ट टार्जन द्वारा किया गया था, जिस पर मानक सर्च ट्री ऑपरेशन चलते हैं। <math>O(\log(n))</math> परिशोधित समय.<ref>{{cite book|last1=Cormen|first1=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald|last4=Stein|first4=Clifford|title=एल्गोरिदम का परिचय|date=2009|publisher=The MIT Press|isbn=978-0-262-03384-8|page=503|edition=Third|url=http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf|access-date=31 October 2017}}</ref> इसे आवश्यक अर्थों में #गतिशील इष्टतमता होने का अनुमान लगाया गया है। ऐसा माना जाता है कि एक स्प्ले ट्री समय O(OPT(X)) में किसी भी पर्याप्त लंबे एक्सेस अनुक्रम X को निष्पादित करता है।<ref name="SplayTrees"/>
+स्प्ले ट्री बाइनरी सर्च ट्री का रूप है जिसका आविष्कार 1985 में डैनियल स्लिएटर और रॉबर्ट टार्जन द्वारा किया गया था, जिस पर मानक सर्च ट्री ऑपरेशन चलते हैं। <math>O(\log(n))</math> परिशोधित समय.<ref>{{cite book|last1=Cormen|first1=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald|last4=Stein|first4=Clifford|title=एल्गोरिदम का परिचय|date=2009|publisher=The MIT Press|isbn=978-0-262-03384-8|page=503|edition=Third|url=http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf|access-date=31 October 2017}}</ref> इसे आवश्यक अर्थों में #गतिशील इष्टतमता होने का अनुमान लगाया गया है। ऐसा माना जाता है कि स्प्ले ट्री समय O(OPT(X)) में किसी भी पर्याप्त लंबे एक्सेस अनुक्रम X को निष्पादित करता है।<ref name="SplayTrees"/>
@@ Line 119: / Line 119: @@
 {{Main|Tango tree}}
-[[टैंगो पेड़]] 2004 में एरिक डेमाइन और अन्य द्वारा प्रस्तावित एक डेटा संरचना है जो समय में किसी भी पर्याप्त-लंबे एक्सेस अनुक्रम एक्स को निष्पादित करने के लिए सिद्ध हुई है। <math>O(\log\log n \operatorname{OPT}(X))</math>. हालांकि यह गतिशील रूप से इष्टतम नहीं है, लेकिन इसका प्रतिस्पर्धी अनुपात <math>\log\log n</math> n के उचित मूल्यों के लिए अभी भी बहुत छोटा है।<ref name="Demaine2004"/>
+[[टैंगो पेड़]] 2004 में एरिक डेमाइन और अन्य द्वारा प्रस्तावित डेटा संरचना है जो समय में किसी भी पर्याप्त-लंबे एक्सेस अनुक्रम एक्स को निष्पादित करने के लिए सिद्ध हुई है। <math>O(\log\log n \operatorname{OPT}(X))</math>. हालांकि यह गतिशील रूप से इष्टतम नहीं है, लेकिन इसका प्रतिस्पर्धी अनुपात <math>\log\log n</math> n के उचित मूल्यों के लिए अभी भी बहुत छोटा है।<ref name="Demaine2004"/>
 === अन्य परिणाम ===
-में, [[जॉन इकोनो]] ने एक पेपर प्रकाशित किया था जो एक एल्गोरिथ्म प्रदान करने के लिए बाइनरी सर्च ट्री की ज्यामिति का उपयोग करता है जो गतिशील रूप से इष्टतम है यदि कोई बाइनरी सर्च ट्री एल्गोरिदम गतिशील रूप से इष्टतम है।<ref name="Iacono2013">{{cite arXiv |first1=John |last1=Iacono |title=गतिशील इष्टतमता अनुमान की खोज में|eprint=1306.0207 |year=2013 |mode=cs2 |class=cs.DS }}</ref> नोड्स की व्याख्या दो आयामों में बिंदुओं के रूप में की जाती है, और इष्टतम पहुंच अनुक्रम उन बिंदुओं का सबसे छोटा [[आर्बरली संतुष्ट]] सुपरसेट है। स्प्ले ट्री और टैंगो ट्री के विपरीत, इकोनो की डेटा संरचना को एक्सेस अनुक्रम चरण के अनुसार निरंतर समय में कार्यान्वयन योग्य नहीं माना जाता है, इसलिए भले ही यह गतिशील रूप से इष्टतम हो, फिर भी यह एक गैर-स्थिर कारक द्वारा अन्य खोज ट्री डेटा संरचनाओं की तुलना में धीमी हो सकती है।
+में, [[जॉन इकोनो]] ने पेपर प्रकाशित किया था जो एल्गोरिथ्म प्रदान करने के लिए बाइनरी सर्च ट्री की ज्यामिति का उपयोग करता है जो गतिशील रूप से इष्टतम है यदि कोई बाइनरी सर्च ट्री एल्गोरिदम गतिशील रूप से इष्टतम है।<ref name="Iacono2013">{{cite arXiv |first1=John |last1=Iacono |title=गतिशील इष्टतमता अनुमान की खोज में|eprint=1306.0207 |year=2013 |mode=cs2 |class=cs.DS }}</ref> नोड्स की व्याख्या दो आयामों में बिंदुओं के रूप में की जाती है, और इष्टतम पहुंच अनुक्रम उन बिंदुओं का सबसे छोटा [[आर्बरली संतुष्ट]] सुपरसेट है। स्प्ले ट्री और टैंगो ट्री के विपरीत, इकोनो की डेटा संरचना को एक्सेस अनुक्रम चरण के अनुसार निरंतर समय में कार्यान्वयन योग्य नहीं माना जाता है, इसलिए भले ही यह गतिशील रूप से इष्टतम हो, फिर भी यह गैर-स्थिर कारक द्वारा अन्य खोज ट्री डेटा संरचनाओं की तुलना में धीमी हो सकती है।
-इंटरलीव निचली सीमा गतिशील इष्टतमता पर एक असम्बद्ध रूप से इष्टतम है।
+इंटरलीव निचली सीमा गतिशील इष्टतमता पर असम्बद्ध रूप से इष्टतम है।
 ==यह भी देखें==
@@ Line 138: / Line 138: @@
 {{reflist}}
-{{CS-Trees}}
+{{DEFAULTSORT:Optimal Binary Search Trees}}[[Category: बाइनरी पेड़]]  [Category:Search tre
-{{Data structures}}
+[[Category: खोजें tr]]
-{{DEFAULTSORT:Optimal Binary Search Trees}}[[Category: बाइनरी पेड़]] [[Category: खोजें tr]] [[Category: खोजें tr]] [Category:Search tre
+[[Category: खोजें tr]]
 [[Category: Machine Translated Page]]
 [[Category:Created On 10/07/2023]]

Anonymous

Search

ऑप्टिमल बाइनरी सर्च ट्री: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:44, 19 July 2023

Contents

स्थैतिक इष्टतमता

परिभाषा

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

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

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

गतिशील इष्टतमता

परिभाषा

पेड़ों को बिखेरें

टैंगो पेड़

अन्य परिणाम

यह भी देखें

टिप्पणियाँ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ऑप्टिमल बाइनरी सर्च ट्री: Difference between revisions

Revision as of 12:44, 19 July 2023

स्थैतिक इष्टतमता

परिभाषा

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

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

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

गतिशील इष्टतमता

परिभाषा

पेड़ों को बिखेरें

टैंगो पेड़

अन्य परिणाम

यह भी देखें

टिप्पणियाँ

Navigation

Wiki tools

Page tools

Other projects

Categories