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

Latest revision as of 11:14, 28 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]

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

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

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 कंप्यूटर विज्ञान:

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

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

परिभाषा

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

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

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

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

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

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

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

स्पले ट्री

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

टैंगो ट्री

टैंगो ट्री 2004 में एरिक डेमाइन और अन्य द्वारा प्रस्तावित डेटा संरचना है जो टाइम में किसी भी पर्याप्त-लंबे एक्सेस अनुक्रम x को निष्पादित करने के लिए सिद्ध हुई है। $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> [[बाइनरी सर्च ट्री]] है जो एक्सेस के दिए गए अनुक्रम (या एक्सेस संभावनाओं) के लिए सबसे छोटा संभव सर्च टाइम (या [[अपेक्षित मूल्य|अपेक्षित रूट]]) प्रदान करता है। सर्वोत्तम बीएसटी को सामान्यतः दो प्रकारों स्थिर और गतिशील में विभाजित किया जाता है।
-स्थैतिक इष्टतमता समस्या में, पेड़ के निर्माण के बाद उसे संशोधित नहीं किया जा सकता है। इस मामले में, पेड़ के नोड्स का कुछ विशेष लेआउट मौजूद है जो दी गई पहुंच संभावनाओं के लिए सबसे छोटा अपेक्षित खोज समय प्रदान करता है। तत्वों की पहुंच संभावनाओं पर जानकारी देते हुए सांख्यिकीय रूप से इष्टतम पेड़ का निर्माण या अनुमान लगाने के लिए विभिन्न एल्गोरिदम मौजूद हैं।
+स्थैतिक सर्वोत्तमता समस्या में, ट्री के निर्माण के पश्चात् उसे संशोधित नहीं किया जा सकता है। इस स्थिति में, ट्री के नोड्स का कुछ विशेष लेआउट उपस्थित है जो दी गई पहुंच संभावनाओं के लिए सबसे छोटा अपेक्षित सर्च टाइम प्रदान करता है। एलिमेंट की पहुंच संभावनाओं पर जानकारी देते हुए सांख्यिकीय रूप से सर्वोत्तम ट्री का निर्माण या अनुमान लगाने के लिए विभिन्न एल्गोरिदम उपस्थित हैं।
-गतिशील इष्टतमता समस्या में, पेड़ को किसी भी समय संशोधित किया जा सकता है, आमतौर पर पेड़ के घूमने की अनुमति देकर। ऐसा माना जाता है कि पेड़ की जड़ से शुरू होने वाला एक कर्सर होता है जिसे वह स्थानांतरित कर सकता है या संशोधन करने के लिए उपयोग कर सकता है। इस मामले में, इन परिचालनों का कुछ न्यूनतम-लागत अनुक्रम मौजूद है जो कर्सर को लक्ष्य पहुंच अनुक्रम में प्रत्येक नोड पर क्रम से जाने का कारण बनता है। सभी मामलों में #डायनामिक ऑप्टिमिटी ट्री की तुलना में [[ बिखरा हुआ पेड़ ]] में निरंतर [[प्रतिस्पर्धी अनुपात]] होने का अनुमान लगाया गया है, हालांकि यह अभी तक साबित नहीं हुआ है।
+गतिशील सर्वोत्तमता समस्या में, ट्री को किसी भी टाइम संशोधित किया जा सकता है, सामान्यतः ट्री के घूमने की अनुमति देकर ऐसा माना जाता है कि ट्री की रूट  से प्रारंभ होने वाला कर्सर होता है जिसे वह स्थानांतरित कर सकता है या संशोधन करने के लिए उपयोग कर सकता है। इस स्थिति में, इन परिचालनों का कुछ न्यूनतम-निवेश अनुक्रम उपस्थित है जो कर्सर को लक्ष्य पहुंच अनुक्रम में प्रत्येक नोड पर क्रम से जाने का कारण बनता है। सभी स्थितियों में डायनामिक ऑप्टिमिटी ट्री की तुलना में [[ बिखरा हुआ पेड़ |मैनिफोल्ड ट्री]] में निरंतर [[प्रतिस्पर्धी अनुपात]] होने का अनुमान लगाया गया है, चूँकि यह अभी तक सिद्ध नहीं हुआ है।
-== स्थैतिक इष्टतमता ==
+== स्थिर अनुकूलता                                                                                                                                                                                                                  ==
 === परिभाषा ===
-डोनाल्ड ई. नुथ द्वारा परिभाषित स्थैतिक इष्टतमता समस्या में,<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> नुथ के नियमों को निम्नलिखित के रूप में देखा जा सकता है:
+इस प्रकार अपने गतिशील प्रोग्रामिंग एल्गोरिदम के अतिरिक्त, नुथ ने सर्वोत्तम बाइनरी सर्च ट्री का लगभग (अनुमान) उत्पादन करने के लिए दो अनुमान (या नियम) प्रस्तावित किए जाते है। लगभग सर्वोत्तम बाइनरी सर्च ट्री का अध्ययन करना आवश्यक था क्योंकि नुथ के एल्गोरिथ्म टाइम और समिष्ट की जटिलता निषेधात्मक हो सकती है जो की  <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> नुथ के नियमों को निम्नलिखित के रूप में देखा जा सकता है:
-* नियम I (रूट-मैक्स): सबसे अधिक बार आने वाले नाम को पेड़ की जड़ में रखें, फिर उपवृक्षों पर भी इसी तरह आगे बढ़ें।
-* नियम II (द्विभाजन): जड़ का चयन करें ताकि बाएं और दाएं उपवृक्ष के कुल वजन को जितना संभव हो सके बराबर किया जा सके, फिर उपवृक्षों पर भी इसी तरह आगे बढ़ें।
-नुथ का अनुमान लगभग इष्टतम बाइनरी सर्च ट्री को लागू करता है <math>O(n \log n)</math> समय और <math>O(n)</math> अंतरिक्ष। इष्टतम नुथ के अनुमान से कितनी दूर हो सकता है इसका विश्लेषण आगे [[कर्ट मेहलहॉर्न]] द्वारा प्रस्तावित किया गया था।<ref name="Mehlhorm1975" />
+* नियम I (रूट-मैक्स): सबसे अधिक बार आने वाले नाम को ट्री की रूट  में रखें, फिर सबट्री पर भी इसी तरह आगे बढ़ें।
+* नियम II (द्विभाजन): रूट  का चयन करें जिससे बाएं और दाएं सबट्री के कुल वजन को जितना संभव हो सके समान किया जा सकता है, फिर सबट्री पर भी इसी तरह आगे बढ़ें।
+नुथ का अनुमान लगभग सर्वोत्तम बाइनरी सर्च ट्री को प्रयुक्त करता है इस प्रकार <math>O(n \log n)</math> टाइम और <math>O(n)</math> समिष्ट सर्वोत्तम नुथ के अनुमान से कितनी दूर हो सकता है इसका विश्लेषण आगे [[कर्ट मेहलहॉर्न]] द्वारा प्रस्तावित किया गया था।<ref name="Mehlhorm1975" />
 === मेहलहॉर्न का सन्निकटन एल्गोरिथ्म ===
-जबकि ओ(एन<sup>2</sup>) नथ के एल्गोरिदम द्वारा लिया गया समय जानवर-बल खोज के लिए आवश्यक घातीय समय से काफी बेहतर है, यह अभी भी व्यावहारिक होने के लिए बहुत धीमा है जब पेड़ में तत्वों की संख्या बहुत बड़ी है।
+जबकि o(n<sup>2</sup>) नथ के एल्गोरिदम द्वारा लिया गया टाइम ब्रूट-फ़ोर्स सर्च के लिए आवश्यक घातीय टाइम से अधिक उत्तम है, यह अभी भी व्यावहारिक होने के लिए बहुत धीमा है जब ट्री में एलिमेंट की संख्या बहुत बड़ी है।
-में, कर्ट मेहलहॉर्न ने नुथ के नियमों के संबंध में महत्वपूर्ण गुणों को साबित करने वाला एक पेपर प्रकाशित किया। मेहलहॉर्न के प्रमुख परिणाम बताते हैं कि नुथ के अनुमानों में से केवल एक (नियम II) हमेशा लगभग इष्टतम बाइनरी खोज पेड़ उत्पन्न करता है। दूसरी ओर, रूट-मैक्स नियम अक्सर निम्नलिखित सरल तर्क के आधार पर बहुत खराब खोज वृक्षों का कारण बन सकता है।<ref name="Mehlhorm1975" />  होने देना
+में, कर्ट मेहलहॉर्न ने नुथ के नियमों के संबंध में महत्वपूर्ण गुणों को सिद्ध करने वाला पेपर प्रकाशित किया था। मेहलहॉर्न के प्रमुख परिणाम बताते हैं कि नुथ के अनुमानों में से केवल (नियम II) सदैव लगभग सर्वोत्तम बाइनरी सर्च ट्री उत्पन्न करता है। दूसरी ओर, रूट-मैक्स नियम अधिकांशतः निम्नलिखित सरल तर्क के आधार पर बहुत व्यर्थ सर्च ट्री का कारण बन सकता है।<ref name="Mehlhorm1975" /> मान लीजिए
-  <math display="inline">\begin{align}
+<math display="inline">\begin{align}
 n = 2^k - 1,~~A_i = 2^{-k} + \varepsilon_i~~\operatorname{with}~~\sum^{n}_{i = 1} \varepsilon_i = 2^{-k}
 \end{align}
 </math> और
- <math display="inline">\begin{align}
+<math display="inline">\begin{align}
 \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{align}
-</math> भारित पथ लंबाई को ध्यान में रखते हुए <math>P
+</math> भारित पाथ लंबाई को ध्यान में रखते हुए <math>P
-</math> पिछली परिभाषा के आधार पर निर्मित वृक्ष से, हमारे पास निम्नलिखित हैं:
+</math> पिछली परिभाषा के आधार पर निर्मित ट्री से, हमारे पास निम्नलिखित हैं:
+<math display="inline">\begin{align}
+ 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{align}
+ </math>
+इस प्रकार, रूट-मैक्स नियम के अनुसार परिणामी ट्री ऐसा ट्री होगा जो केवल दाईं ओर बढ़ता है (ट्री के सबसे गहरे स्तर को छोड़कर), और बाईं ओर सदैव टर्मिनल नोड्स होंगे। इस ट्री की पाथ लंबाई से घिरा हुआ है <math display="inline">\Omega (\frac{n}{2})</math> और, जब संतुलित सर्च ट्री के साथ तुलना की जाती है (पाथ से घिरा हुआ) <math display="inline">O (2 \log n)</math>), समान आवृत्ति वितरण के लिए अधिक व्यर्थ प्रदर्शन करते है।<ref name="Mehlhorm1975" />
- <math display="inline">\begin{align}
+इसके अतिरिक्त, मेहलहॉर्न ने नुथ के काम में सुधार किया और बहुत ही सरल एल्गोरिथ्म प्रस्तुत किया जो नियम II का उपयोग करता है और केवल सांख्यिकीय रूप से सर्वोत्तम ट्री के प्रदर्शन का सूक्ष्मता से अनुमान लगाता है। {{tmath|O(n)}} टाइम <ref name="Mehlhorm1975" /> एल्गोरिथ्म बाएँ और दाएँ सबट्री के कुल वजन (संभावना द्वारा) को सबसे निकट से संतुलित करने के लिए ट्री की रूट  को चुनकर द्विभाजन नियम के समान विचार का पालन करता है। और फिर रणनीति को प्रत्येक सबट्री पर पुनरावर्ती रूप से प्रयुक्त किया जाता है।
-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{align}
-</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" />एल्गोरिथ्म बाएँ और दाएँ उपवृक्षों के कुल वजन (संभावना द्वारा) को सबसे निकट से संतुलित करने के लिए पेड़ की जड़ को चुनकर द्विभाजन नियम के समान विचार का पालन करता है। और फिर रणनीति को प्रत्येक उपवृक्ष पर पुनरावर्ती रूप से लागू किया जाता है।
-यह रणनीति एक अच्छा सन्निकटन उत्पन्न करती है, इसे सहज रूप से देखा जा सकता है, यह देखते हुए कि किसी भी पथ के साथ उपवृक्षों का वजन ज्यामितीय रूप से घटते क्रम के बहुत करीब होता है। वास्तव में, यह रणनीति एक पेड़ उत्पन्न करती है जिसकी भारित पथ लंबाई अधिकतम होती है
+यह रणनीति अच्छा सन्निकटन उत्पन्न करती है, इसे सहज रूप से देखा जा सकता है, यह देखते हुए कि किसी भी पाथ के साथ सबट्री का वजन ज्यामितीय रूप से घटते क्रम के बहुत निकट होता है। वास्तव में, यह रणनीति ट्री उत्पन्न करती है जिसकी भारित पाथ लंबाई अधिकतम होती है
 :<math>2+(1 - \log(\sqrt{5} - 1))^{-1}H = 2 + \frac H {1 - \log(\sqrt{5} - 1)}</math>
-जहाँ H संभाव्यता वितरण की [[एन्ट्रापी (सूचना सिद्धांत)]] है। चूँकि कोई भी इष्टतम बाइनरी सर्च ट्री कभी भी भारित पथ लंबाई से बेहतर नहीं कर सकता है
+जहाँ H संभाव्यता वितरण की [[एन्ट्रापी (सूचना सिद्धांत)]] है। चूँकि कोई भी सर्वोत्तम बाइनरी सर्च ट्री कभी भी भारित पाथ लंबाई से उत्तम नहीं कर सकता है
 :<math>(1/\log3)H = \frac H {\log 3}</math>
-यह सन्निकटन बहुत करीब है.<ref name="Mehlhorm1975" />
+यह सन्निकटन बहुत निकट है.<ref name="Mehlhorm1975" />
+===हू-टकर और गार्सिया-वाच एल्गोरिदम===
+{{main|गार्सिया-वॉच एल्गोरिदम}}
-===हू-टकर और गार्सिया-वाच एल्गोरिदम===
+विशेष स्थिति में कि सभी <math>A_i</math> मान शून्य हैं, सर्वोत्तम ट्री टाइम में पाया जा सकता है <math>O(n\log n)</math>. यह पहली बार टी. सी. हू और [[एलन टकर]] द्वारा 1971 में प्रकाशित पेपर में सिद्ध किया गया था। गार्सिया और वाच्स द्वारा पश्चात् में सरलीकरण, गार्सिया-वाच एल्गोरिदम, समान क्रम में समान तुलना करता है। एल्गोरिथ्म [[लालची एल्गोरिदम|ग्रीडी एल्गोरिदम]] का उपयोग करके ट्री का निर्माण करता है जिसमें प्रत्येक पत्ते के लिए सर्वोत्तम ऊंचाई होती है, किन्तु क्रम से बाहर है, और फिर उसी ऊंचाई के साथ और बाइनरी सर्च ट्री का निर्माण करता है।<ref>{{citation
-{{main|Garsia–Wachs algorithm}}
-विशेष मामले में कि सभी <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 84: / Line 84: @@
   | title = The Art of Computer Programming, Vol. 3: Sorting and Searching
   | year = 1998| title-link = The Art of Computer Programming }}. See also History and bibliography, pp. 453–454.</ref>
+== गतिशील सर्वोत्तमता ==
+{{unsolved|कंप्यूटर विज्ञान|क्या स्प्ले ट्री किसी अन्य बाइनरी सर्च ट्री एल्गोरिदम की तरह ही अच्छा प्रदर्शन करते हैं?}}
-== गतिशील इष्टतमता ==
-{{unsolved|computer science|Do splay trees perform as well as any other binary search tree algorithm?}}
 === परिभाषा ===
-गतिशील इष्टतमता की कई अलग-अलग परिभाषाएँ हैं, जिनमें से सभी प्रभावी रूप से रनिंग-टाइम के संदर्भ में एक स्थिर कारक के बराबर हैं।<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>, ..., x<sub>m</sub> का क्रम दिया गया है कीज पर प्रत्येक एक्सेस के लिए, हमें अपने बीएसटी के रूट पर [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] दिया जाता है और हम निम्नलिखित में से कोई भी ऑपरेशन करने के लिए पॉइंटर का उपयोग कर सकते हैं:
 # पॉइंटर को वर्तमान नोड के बाएँ चाइल्ड पर ले जाएँ।
@@ Line 100: / Line 98: @@
 # वर्तमान नोड और उसके पैरेंट पर एकल ट्री रोटेशन निष्पादित करें।
-(यह चौथे ऑपरेशन की उपस्थिति है, जो एक्सेस के दौरान पेड़ को पुनर्व्यवस्थित करता है, जो इसे गतिशील ऑप्टिमलिटी समस्या बनाता है।)
+(यह चौथे ऑपरेशन की उपस्थिति है, जो एक्सेस के टाइम ट्री को पुनर्व्यवस्थित करता है, जो इसे गतिशील ऑप्टिमलिटी समस्या बनाता है।)
-प्रत्येक पहुंच के लिए, हमारा बीएसटी एल्गोरिदम उपरोक्त परिचालनों के किसी भी अनुक्रम को तब तक निष्पादित कर सकता है जब तक कि सूचक अंततः लक्ष्य मान x वाले नोड पर समाप्त न हो जाए।<sub>i</sub>. किसी दिए गए गतिशील बीएसटी एल्गोरिदम को एक्सेस के अनुक्रम को निष्पादित करने में लगने वाला समय उस अनुक्रम के दौरान किए गए ऐसे ऑपरेशनों की कुल संख्या के बराबर है। तत्वों के किसी भी सेट पर पहुंच के किसी भी क्रम को देखते हुए, उन पहुंचों को निष्पादित करने के लिए कुछ न्यूनतम कुल संचालन की आवश्यकता होती है। हम इस न्यूनतम के करीब पहुंचना चाहेंगे.
-हालांकि एक्सेस अनुक्रम क्या होगा, इसकी पूर्व जानकारी के बिना इस भगवान के एल्गोरिदम को लागू करना असंभव है, हम ओपीटी (एक्स) को एक्सेस अनुक्रम एक्स के लिए किए जाने वाले संचालन की संख्या के रूप में परिभाषित कर सकते हैं, और हम कह सकते हैं कि एक एल्गोरिदम # है गतिशील इष्टतमता यदि, किसी भी एक्स के लिए, यह समय में [[ बिग ओ अंकन ]] (ओपीटी (एक्स)) में एक्स प्रदर्शन करता है (अर्थात, इसका एक निरंतर प्रतिस्पर्धी अनुपात है)।<ref name="Demaine2004"/>
-कई डेटा संरचनाओं में यह गुण होने का अनुमान लगाया गया है, लेकिन कोई भी सिद्ध नहीं हुआ है। यह एक [[खुली समस्या]] है कि क्या इस मॉडल में गतिशील रूप से इष्टतम डेटा संरचना मौजूद है।
-=== पेड़ों को बिखेरें ===
-{{Main|Splay tree}}
+प्रत्येक पहुंच के लिए, हमारा बीएसटी एल्गोरिदम उपरोक्त परिचालनों के किसी भी अनुक्रम को तब तक निष्पादित कर सकता है जब तक कि सूचक अंततः लक्ष्य मान x वाले नोड पर समाप्त न हो जाए।<sub>i</sub>. किसी दिए गए गतिशील बीएसटी एल्गोरिदम को एक्सेस के अनुक्रम को निष्पादित करने में लगने वाला टाइम उस अनुक्रम के टाइम किए गए ऐसे ऑपरेशनों की कुल संख्या के समान है। एलिमेंट के किसी भी सेट  पर पहुंच के किसी भी क्रम को देखते हुए, उन पहुंचों को निष्पादित करने के लिए कुछ न्यूनतम कुल संचालन की आवश्यकता होती है। हम इस न्यूनतम के निकट पहुंचना चाहेंगे.
-स्प्ले ट्री बाइनरी सर्च ट्री का एक रूप है जिसका आविष्कार 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"/>
+चूँकि एक्सेस अनुक्रम क्या होगा, इसकी पूर्व जानकारी के बिना इस एल्गोरिदम को प्रयुक्त करना असंभव है, हम ओपीटी (x) को एक्सेस अनुक्रम x के लिए किए जाने वाले संचालन की संख्या के रूप में परिभाषित कर सकते हैं, और हम कह सकते हैं कि एल्गोरिदम है गतिशील सर्वोत्तमता यदि, किसी भी x के लिए, यह टाइम में [[ बिग ओ अंकन |बिग ओ अंकन]] (ओपीटी (एक्स)) में x प्रदर्शन करता है (अर्थात, इसका निरंतर प्रतिस्पर्धी अनुपात है)।<ref name="Demaine2004"/>
+कई डेटा संरचनाओं में यह गुण होने का अनुमान लगाया गया है, किन्तु कोई भी सिद्ध नहीं हुआ है। यह [[खुली समस्या|संवृत समस्या]] है कि क्या इस मॉडल में गतिशील रूप से सर्वोत्तम डेटा संरचना उपस्थित है।
-=== टैंगो पेड़ ===
+=== स्पले ट्री ===
-{{Main|Tango tree}}
+{{Main|सिप्ली ट्री}}
-[[टैंगो पेड़]] 2004 में एरिक डेमाइन और अन्य द्वारा प्रस्तावित एक डेटा संरचना है जो समय में किसी भी पर्याप्त-लंबे एक्सेस अनुक्रम एक्स को निष्पादित करने के लिए सिद्ध हुई है। <math>O(\log\log n \operatorname{OPT}(X))</math>. हालांकि यह गतिशील रूप से इष्टतम नहीं है, लेकिन इसका प्रतिस्पर्धी अनुपात <math>\log\log n</math> n के उचित मूल्यों के लिए अभी भी बहुत छोटा है।<ref name="Demaine2004"/>
+स्प्ले ट्री बाइनरी सर्च ट्री का रूप है जिसका आविष्कार 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"/>
+=== टैंगो ट्री ===
+{{Main|टैंगो ट्री}}
+[[टैंगो पेड़|टैंगो ट्री]] 2004 में एरिक डेमाइन और अन्य द्वारा प्रस्तावित डेटा संरचना है जो टाइम में किसी भी पर्याप्त-लंबे एक्सेस अनुक्रम x को निष्पादित करने के लिए सिद्ध हुई है। <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> नोड्स की व्याख्या दो आयामों में बिंदुओं के रूप में की जाती है, और सर्वोत्तम पहुंच अनुक्रम उन बिंदुओं का सबसे छोटा [[आर्बरली संतुष्ट|आर्बरली]] सैटिसफाइड  सुपरसेट है। स्प्ले ट्री और टैंगो ट्री के विपरीत, इकोनो की डेटा संरचना को एक्सेस अनुक्रम चरण के अनुसार निरंतर टाइम में कार्यान्वयन योग्य नहीं माना जाता है, इसलिए तथापि यह गतिशील रूप से सर्वोत्तम हो, फिर भी यह गैर-स्थिर कारक द्वारा अन्य सर्च ट्री डेटा संरचनाओं की तुलना में धीमी हो सकती है।
-इंटरलीव निचली सीमा गतिशील इष्टतमता पर एक असम्बद्ध रूप से इष्टतम है।
+इंटरलीव निचली सीमा गतिशील सर्वोत्तमता पर असम्बद्ध रूप से सर्वोत्तम है।
 ==यह भी देखें==
-* [[वृक्ष डेटा संरचना]]
+* [[वृक्ष डेटा संरचना|ट्री डेटा संरचना]]
-* छींटे का पेड़
+* स्पले ट्री
-* टैंगो पेड़
+* टैंगो ट्री
 * बाइनरी सर्च ट्री की ज्यामिति
 * निचली सीमा को इंटरलीव करें
-==टिप्पणियाँ==
+==टिप्पणियाँ                                                                                                                                                                                                    ==
 {{reflist}}
-{{CS-Trees}}
+{{DEFAULTSORT:Optimal Binary Search Trees}}  [Category:Search tre
-{{Data structures}}
-{{DEFAULTSORT:Optimal Binary Search Trees}}[[Category: बाइनरी पेड़]] [[Category: खोजें tr]] [[Category: खोजें tr]] [Category:Search tre
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Optimal Binary Search Trees]]
-[[Category:Created On 10/07/2023]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Created On 10/07/2023|Optimal Binary Search Trees]]
+[[Category:Lua-based templates|Optimal Binary Search Trees]]
+[[Category:Machine Translated Page|Optimal Binary Search Trees]]
+[[Category:Pages with script errors|Optimal Binary Search Trees]]
+[[Category:Templates Vigyan Ready|Optimal Binary Search Trees]]
+[[Category:Templates that add a tracking category|Optimal Binary Search Trees]]
+[[Category:Templates that generate short descriptions|Optimal Binary Search Trees]]
+[[Category:Templates using TemplateData|Optimal Binary Search Trees]]
+[[Category:खोजें tr|Optimal Binary Search Trees]]
+[[Category:बाइनरी पेड़|Optimal Binary Search Trees]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 11:14, 28 July 2023

Contents

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

परिभाषा

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

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

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

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

परिभाषा

स्पले ट्री

टैंगो ट्री

अन्य परिणाम

यह भी देखें

टिप्पणियाँ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 11:14, 28 July 2023

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

परिभाषा

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

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

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

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

परिभाषा

स्पले ट्री

टैंगो ट्री

अन्य परिणाम

यह भी देखें

टिप्पणियाँ

Navigation

Wiki tools

Page tools

Other projects

Categories