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

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

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

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

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

परिभाषा

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\textstyle {\begin{aligned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_{j}\\&=\sum _{i=1}^{n}A_{i}i\\&\geqq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1)}{2}}\geqq {\frac {n}{2}}.\end{aligned}}}$ इस प्रकार, रूट-मैक्स नियम के अनुसार परिणामी पेड़ एक ऐसा पेड़ होगा जो केवल दाईं ओर बढ़ता है (पेड़ के सबसे गहरे स्तर को छोड़कर), और बाईं ओर हमेशा टर्मिनल नोड्स होंगे। इस पेड़ की पथ लंबाई से घिरा हुआ है ${\textstyle \Omega ({\frac {n}{2}})}$ और, जब एक संतुलित खोज वृक्ष के साथ तुलना की जाती है (पथ से घिरा हुआ)। ${\textstyle O(2\log n)}$), समान आवृत्ति वितरण के लिए काफी खराब प्रदर्शन करेगा। 

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

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

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

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

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

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

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

Main article: Garsia–Wachs algorithm

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

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

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

परिभाषा

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

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

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

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

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

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

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

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

Main article: Splay tree

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

टैंगो पेड़

Main article: Tango tree

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

अन्य परिणाम

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

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

यह भी देखें

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

टिप्पणियाँ

[Category:Search tre