ऑप्टिमल बाइनरी सर्च ट्री: 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> [[बाइनरी सर्च ट्री]] है जो एक्सेस के दिए गए अनुक्रम (या एक्सेस संभावनाओं) के लिए सबसे छोटा संभव सर्च टाइम (या [[अपेक्षित मूल्य|अपेक्षित रूट]]) प्रदान करता है। सर्वोत्तम बीएसटी को सामान्यतः दो प्रकारों स्थिर और गतिशील में विभाजित किया जाता है।
-स्थैतिक सर्वोत्तमता समस्या में, ट्री के निर्माण के पश्चात् उसे संशोधित नहीं किया जा सकता है। इस स्थिति में, ट्री के नोड्स का कुछ विशेष लेआउट उपस्थित है जो दी गई पहुंच संभावनाओं के लिए सबसे छोटा अपेक्षित सर्च टाइम प्रदान करता है। अवयवों की पहुंच संभावनाओं पर जानकारी देते हुए सांख्यिकीय रूप से सर्वोत्तम ट्री का निर्माण या अनुमान लगाने के लिए विभिन्न एल्गोरिदम उपस्थित हैं।
+स्थैतिक सर्वोत्तमता समस्या में, ट्री के निर्माण के पश्चात् उसे संशोधित नहीं किया जा सकता है। इस स्थिति में, ट्री के नोड्स का कुछ विशेष लेआउट उपस्थित है जो दी गई पहुंच संभावनाओं के लिए सबसे छोटा अपेक्षित सर्च टाइम प्रदान करता है। एलिमेंट की पहुंच संभावनाओं पर जानकारी देते हुए सांख्यिकीय रूप से सर्वोत्तम ट्री का निर्माण या अनुमान लगाने के लिए विभिन्न एल्गोरिदम उपस्थित हैं।
 गतिशील सर्वोत्तमता समस्या में, ट्री को किसी भी टाइम संशोधित किया जा सकता है, सामान्यतः ट्री के घूमने की अनुमति देकर ऐसा माना जाता है कि ट्री की रूट  से प्रारंभ होने वाला कर्सर होता है जिसे वह स्थानांतरित कर सकता है या संशोधन करने के लिए उपयोग कर सकता है। इस स्थिति में, इन परिचालनों का कुछ न्यूनतम-निवेश अनुक्रम उपस्थित है जो कर्सर को लक्ष्य पहुंच अनुक्रम में प्रत्येक नोड पर क्रम से जाने का कारण बनता है। सभी स्थितियों में डायनामिक ऑप्टिमिटी ट्री की तुलना में [[ बिखरा हुआ पेड़ |मैनिफोल्ड ट्री]] में निरंतर [[प्रतिस्पर्धी अनुपात]] होने का अनुमान लगाया गया है, चूँकि यह अभी तक सिद्ध नहीं हुआ है।
@@ 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}}, क्रूर-बल सर्च सामान्यतः व्यवहार्य समाधान नहीं है।
@@ Line 16: / Line 16: @@
 === नुथ का [[गतिशील प्रोग्रामिंग]] एल्गोरिदम                                                                                                                                                                                                          ===
-में, नुथ ने अपेक्षाकृत सीधा गतिशील प्रोग्रामिंग एल्गोरिदम प्रकाशित किया जो केवल 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) लेकर संशोधित एल्गोरिदम तैयार करने के लिए किया जा सकता है)
+इस एल्गोरिथ्म का सरल कार्यान्वयन वास्तव में ''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 (द्विभाजन): रूट  का चयन करें ताकि बाएं और दाएं सबट्री के कुल वजन को जितना संभव हो सके समान किया जा सके, फिर सबट्री पर भी इसी तरह आगे बढ़ें।
+* नियम II (द्विभाजन): रूट  का चयन करें जिससे बाएं और दाएं सबट्री के कुल वजन को जितना संभव हो सके समान किया जा सकता है, फिर सबट्री पर भी इसी तरह आगे बढ़ें।
 नुथ का अनुमान लगभग सर्वोत्तम बाइनरी सर्च ट्री को प्रयुक्त करता है इस प्रकार <math>O(n \log n)</math> टाइम और <math>O(n)</math> समिष्ट सर्वोत्तम नुथ के अनुमान से कितनी दूर हो सकता है इसका विश्लेषण आगे [[कर्ट मेहलहॉर्न]] द्वारा प्रस्तावित किया गया था।<ref name="Mehlhorm1975" />
 === मेहलहॉर्न का सन्निकटन एल्गोरिथ्म ===
-जबकि o(n<sup>2</sup>) नथ के एल्गोरिदम द्वारा लिया गया टाइम जानवर-बल सर्च के लिए आवश्यक घातीय टाइम से अधिक उत्तम है, यह अभी भी व्यावहारिक होने के लिए बहुत धीमा है जब ट्री में अवयवों की संख्या बहुत बड़ी है।
+जबकि o(n<sup>2</sup>) नथ के एल्गोरिदम द्वारा लिया गया टाइम ब्रूट-फ़ोर्स सर्च के लिए आवश्यक घातीय टाइम से अधिक उत्तम है, यह अभी भी व्यावहारिक होने के लिए बहुत धीमा है जब ट्री में एलिमेंट की संख्या बहुत बड़ी है।
 में, कर्ट मेहलहॉर्न ने नुथ के नियमों के संबंध में महत्वपूर्ण गुणों को सिद्ध करने वाला पेपर प्रकाशित किया था। मेहलहॉर्न के प्रमुख परिणाम बताते हैं कि नुथ के अनुमानों में से केवल (नियम II) सदैव लगभग सर्वोत्तम बाइनरी सर्च ट्री उत्पन्न करता है। दूसरी ओर, रूट-मैक्स नियम अधिकांशतः निम्नलिखित सरल तर्क के आधार पर बहुत व्यर्थ सर्च ट्री का कारण बन सकता है।<ref name="Mehlhorm1975" /> मान लीजिए
@@ Line 52: / Line 52: @@
 \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> पिछली परिभाषा के आधार पर निर्मित ट्री से, हमारे पास निम्नलिखित हैं:
@@ Line 62: / Line 62: @@
   </math>
-इस प्रकार, रूट-मैक्स नियम के अनुसार परिणामी ट्री ऐसा ट्री होगा जो केवल दाईं ओर बढ़ता है (ट्री के सबसे गहरे स्तर को छोड़कर), और बाईं ओर सदैव टर्मिनल नोड्स होंगे। इस ट्री की पथ लंबाई से घिरा हुआ है <math display="inline">\Omega (\frac{n}{2})</math> और, जब संतुलित सर्च ट्री के साथ तुलना की जाती है (पथ से घिरा हुआ) <math display="inline">O (2 \log n)</math>), समान आवृत्ति वितरण के लिए अधिक व्यर्थ प्रदर्शन करते है।<ref name="Mehlhorm1975" />
+इस प्रकार, रूट-मैक्स नियम के अनुसार परिणामी ट्री ऐसा ट्री होगा जो केवल दाईं ओर बढ़ता है (ट्री के सबसे गहरे स्तर को छोड़कर), और बाईं ओर सदैव टर्मिनल नोड्स होंगे। इस ट्री की पाथ लंबाई से घिरा हुआ है <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>
@@ Line 100: / Line 100: @@
 (यह चौथे ऑपरेशन की उपस्थिति है, जो एक्सेस के टाइम ट्री को पुनर्व्यवस्थित करता है, जो इसे गतिशील ऑप्टिमलिटी समस्या बनाता है।)
-प्रत्येक पहुंच के लिए, हमारा बीएसटी एल्गोरिदम उपरोक्त परिचालनों के किसी भी अनुक्रम को तब तक निष्पादित कर सकता है जब तक कि सूचक अंततः लक्ष्य मान x वाले नोड पर समाप्त न हो जाए।<sub>i</sub>. किसी दिए गए गतिशील बीएसटी एल्गोरिदम को एक्सेस के अनुक्रम को निष्पादित करने में लगने वाला टाइम उस अनुक्रम के टाइम किए गए ऐसे ऑपरेशनों की कुल संख्या के समान है। अवयवों के किसी भी सेट  पर पहुंच के किसी भी क्रम को देखते हुए, उन पहुंचों को निष्पादित करने के लिए कुछ न्यूनतम कुल संचालन की आवश्यकता होती है। हम इस न्यूनतम के निकट पहुंचना चाहेंगे.
+प्रत्येक पहुंच के लिए, हमारा बीएसटी एल्गोरिदम उपरोक्त परिचालनों के किसी भी अनुक्रम को तब तक निष्पादित कर सकता है जब तक कि सूचक अंततः लक्ष्य मान x वाले नोड पर समाप्त न हो जाए।<sub>i</sub>. किसी दिए गए गतिशील बीएसटी एल्गोरिदम को एक्सेस के अनुक्रम को निष्पादित करने में लगने वाला टाइम उस अनुक्रम के टाइम किए गए ऐसे ऑपरेशनों की कुल संख्या के समान है। एलिमेंट के किसी भी सेट  पर पहुंच के किसी भी क्रम को देखते हुए, उन पहुंचों को निष्पादित करने के लिए कुछ न्यूनतम कुल संचालन की आवश्यकता होती है। हम इस न्यूनतम के निकट पहुंचना चाहेंगे.
 चूँकि एक्सेस अनुक्रम क्या होगा, इसकी पूर्व जानकारी के बिना इस एल्गोरिदम को प्रयुक्त करना असंभव है, हम ओपीटी (x) को एक्सेस अनुक्रम x के लिए किए जाने वाले संचालन की संख्या के रूप में परिभाषित कर सकते हैं, और हम कह सकते हैं कि एल्गोरिदम है गतिशील सर्वोत्तमता यदि, किसी भी x के लिए, यह टाइम में [[ बिग ओ अंकन |बिग ओ अंकन]] (ओपीटी (एक्स)) में x प्रदर्शन करता है (अर्थात, इसका निरंतर प्रतिस्पर्धी अनुपात है)।<ref name="Demaine2004"/>
@@ Line 132: / Line 132: @@
 {{reflist}}
-{{DEFAULTSORT:Optimal Binary Search Trees}}[[Category: बाइनरी पेड़]]  [Category:Search tre
+{{DEFAULTSORT:Optimal Binary Search Trees}}  [Category:Search tre
-[[Category: खोजें tr]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Optimal Binary Search Trees]]
-[[Category: खोजें tr]]
+[[Category:CS1 English-language sources (en)]]
-[[Category: Machine Translated Page]]
+[[Category:Created On 10/07/2023|Optimal Binary Search Trees]]
-[[Category:Created On 10/07/2023]]
+[[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