स्व-संतुलन बाइनरी सर्च ट्री: Difference between revisions

Revision as of 01:06, 4 July 2023

असंतुलित वृक्ष का उदाहरण; रूट से नोड तक पथ का अनुसरण करने पर औसतन 3.27 नोड एक्सेस की आवश्यकता होती है

ऊंचाई-संतुलित होने के बाद वही वृक्ष; औसत पथ प्रयास घटकर 3.00 नोड पहुंच हो गया

कंप्यूटर विज्ञान में, एक स्व-संतुलन द्विआधारी अन्वेषण वृक्ष (बीएसटी) कोई भी नोड -आधारित एक द्विआधारी अन्वेषण वृक्ष होता है जो एकपक्षीय वस्तु एकीकरण और विलोपन की स्थिति में स्वचालित रूप से अपनी ऊंचाई (जड़ के नीचे के स्तर की अधिकतम संख्या) को छोटा रखता है।^[1]

जब ये परिचालन स्व-संतुलन द्विआधारी अन्वेषण वृक्ष के लिए डिज़ाइन किए जाते हैं, तो इसमें वृक्ष की ऊंचाई को असीमित रूप से बढ़ाने के विरुद्ध सतर्क उपाय सम्मलित होते हैं, जिससें इन अमूर्त डेटा प्रकार को स्व-संतुलन विशेषता प्राप्त होती है।

ऊंचाई-संतुलित बाइनरी वृक्षों के लिए, ऊंचाई को वस्तुओं की संख्या $n$ में लघुगणक $O(\log n)$ के रूप में परिभाषित किया जाता है। यह कई द्विआधारी अन्वेषण वृक्ष जैसे कि एवीएल वृक्ष और लाल-काले वृक्ष की स्थितियां है। स्प्ले वृक्ष और ट्रीप्स स्व -संतुलन वाले होते हैं परन्तु ऊंचाई-संतुलित नहीं होती हैं, क्योंकि उनकी ऊंचाई वस्तुओं की संख्या में लघुगणक होने के लिए आश्वस्त नहीं करती है।

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

अवलोकन

सही या बिल्कुल सही संतुलन बनाए रखने के लिए स्व-संतुलन बाइनरी वृक्षों पर वृक्ष का घूमना बहुत आम आंतरिक संचालन है।

द्विआधारी अन्वेषण वृक्ष (बीएसटी) पर सामान्यतः परिचालन में वृक्ष की ऊंचाई के सीधे आनुपातिक समय लगता है, इसलिए ऊंचाई को छोटा रखना आवश्क होता है। h ऊँचाई वाले एक द्विआधारी वृक्ष में अधिकतम 2⁰+2¹+···+2^h = 2^h+1−1 नोड्स हो सकते हैं। यह इस प्रकार है कि n नोड्स और h ऊँचाई वाले किसी भी वृक्ष के लिए:

n\leq 2^{h+1}-1

और इसका तात्पर्य है:

h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor

.

दूसरे शब्दों में, n नोड्स वाले द्विआधारी वृक्ष की न्यूनतम ऊँचाई log₂(n) होती है, जिसेराउंडेड (गोलाकार) किया जाता है ; जो $\lfloor \log _{2}n\rfloor$ होता है।^[1]

चूकिं, बीएसटी वस्तु प्रविष्टि के लिए सबसे सरल एल्गोरिदम सामान्य स्थितियों में ऊँचाई n वाला एक वृक्ष उत्पन्न कर सकता है। उदाहरण के लिए, जब वस्तु को क्रमबद्ध कुंजी (डेटाबेस) क्रम में डाला जाता है, तो वृक्ष एन नोड्स के साथ एक लिंक की गई सूची में बदल जाता है। दोनों स्थितियों के बीच प्रदर्शन में अंतर बहुत बड़ा हो सकता है: उदाहरण के लिए, जब n = 1,000,000, न्यूनतम ऊंचाई $\lfloor \log _{2}(1,000,000)\rfloor =19$ होती है।

यदि डेटा वस्तु समय से पहले ज्ञात होता हैं, तो यादृच्छिक क्रम में मान जोड़कर, ऊंचाई को औसत अर्थ में छोटा रखा जा सकता है, जिसके परिणामस्वरूप एक यादृच्छिक द्विआधारी अन्वेषण वृक्ष निर्मित होता है। चूकिं, ऐसी कई स्थितियाँ हैं (जैसे ऑनलाइन एल्गोरिदम) जहां यह यादृच्छिक एल्गोरिदम कार्य नहीं करते है।

स्व-संतुलन वाले द्विआधारी वृक्ष कुंजी प्रविष्टि समय पर वृक्ष पर परिवर्तन (जैसे कि वृक्ष का घूमना) करके इस समस्या को हल करते हैं, जिससें ऊंचाई log₂(n) को आनुपातिक रखा जा सके। चूकिं एक निश्चित ओवरहेड सम्मलित होता है, यह हमेशा आवश्यक लुकअप लागत से बड़ा नहीं होता है और सभी परिचालनों के तेजी से निष्पादन को सुनिश्चित करके उचित घोषित किया जा सकता है।

जबकि अपेक्षित न्यूनतम ऊंचाई के साथ और $O(\log n)$ समय संचालन (लुकअप/सम्मिलन/हटाना) के साथ बीएसटी बनाए रखना संभव है, ऐसी संरचना को बनाए रखने के लिए आवश्यक अतिरिक्त स्थान की आवश्यकताएं अन्वेषण समय में कमी से अधिक होती हैं। तुलना के लिए, एक एवीएल वृक्ष को सर्वोत्तम ऊंचाई के 1.44 के कारक के भीतर होने का आश्वासन दिया जाता है, जबकि एक सरल कार्यान्वयन में संचय के मात्र दो अतिरिक्त बिट्स कीआवश्यकता होती है।^[1]इसलिए, सामान्यतः स्व-संतुलन बीएसटी एल्गोरिदम ऊंचाई को इस निचली सीमा के एक स्थिर कारक के भीतर रखते हैं।

एसिम्प्टोटिक (स्पर्शोन्मुख) ( "बिग-ओ" ) अर्थ में, n वस्तु युक्त एक स्व-संतुलन बीएसटी संरचना किसी वस्तु को देखने, सम्मिलित करने और हटाने की अनुमति देती है। $O(\log n)$ सबसे खराब स्थिति का समय, और सभी वस्तुओं का क्रमानुसार पुनरावृत्ति समय $O(n)$ होता है। कुछ कार्यान्वयन के लिए ये प्रति-परिचालन समय सीमाएँ होती हैं, जबकि अन्य के लिए ये संचालन के अनुक्रम पर परिशोधित विश्लेषण सीमाएँ होती हैं। ये समय सभी डेटा संरचनाओं के बीच स्पर्शोन्मुख रूप से सर्वोत्तम होते हैं जो मात्र तुलनाओं के माध्यम से कुंजी में परिवर्तन करते हैं।

कार्यान्वयन

इस प्रकार के वृक्ष को प्रयुक्त करने वाली डेटा संरचनाओं में सम्मलित हैं:

2-3 वृक्ष
एए वृक्ष
एवीएल वृक्ष
बी-वृक्ष
लाल-काला वृक्ष
बलि का बकरा वृक्ष
छींटे का वृक्ष
टैंगो वृक्ष
जाल बिछाना
वजन-संतुलित वृक्ष

अनुप्रयोग

स्व-संतुलन द्विआधारी अन्वेषण वृक्षों का उपयोग प्राथमिकता कतारों जैसी आदेशित सूचियों के निर्माण और रखरखाव के लिए प्राकृतिक तरीके से किया जा सकता है। इनका उपयोग सहयोगी सरणियों के लिए भी किया जा सकता है; कुंजी-मूल्य जोड़े को केवल कुंजी के आधार पर एक क्रम के साथ डाला जाता है। इस क्षमता में, स्व-संतुलन वाले बीएसटी के पास अपने मुख्य प्रतिद्वंद्वी, हैश तालिकाओं पर सहयोगी सरणी कुशल प्रतिनिधित्व होते हैं। स्व-संतुलन बीएसटी का एक लाभ यह होता है कि वे कुंजी क्रम में वस्तुओं की शीघ्रता से (वास्तव में, असम्बद्ध रूप से सर्वोत्तम) गणना करने की अनुमति देते हैं, जो हैश टेबल प्रदान नहीं करते हैं। एक हानि यह है कि उनके लुकअप एल्गोरिदम अधिक जटिल हो जाते हैं जब एक ही कुंजी के साथ कई वस्तु हो सकते हैं। स्व-संतुलन बीएसटी का सबसे खराब स्थिति वाला लुकअप प्रदर्शन अन्य हैश टेबल ( $O(\log n)$ की तुलना में $O(n)$ ) की तुलना में श्रेष्ट होता है^[2], परन्तु औसत-स्थितियों में ( $O(\log n)$ की तुलना में $O(1)$ ) प्रदर्शन अत्यधिक बेकार होता है।

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

स्व-संतुलन बीएसटी लचीली डेटा संरचनाएं होती हैं, अतिरिक्त जानकारी को कुशलतापूर्वक लेख्यांकित करने या नए परिचालन करने के लिए उन्हें विस्तारित करना आसान होता है। उदाहरण के लिए, कोई एक निश्चित संपत्ति वाले प्रत्येक उपट्री में नोड्स की संख्या लेख्यांकित कर सकता है, जिससे वह $O(\log n)$ समय समय में उस संपत्ति के साथ एक निश्चित कुंजी श्रेणी में नोड्स की संख्या की गणना कर सकता है। इन एक्सटेंशन का उपयोग, उदाहरण के लिए, डेटाबेस क्वेरीज़ या अन्य सूची-प्रसंस्करण एल्गोरिदम को अनुकूलित करने के लिए किया जा सकता है।

यह भी देखें

डेटा संरचना खोजें
डे-स्टाउट-वॉरेन एल्गोरिदम
संलयन वृक्ष
सूची छोड़ें
छँटाई

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.
↑ Cuckoo hashing provides worst-case lookup performance of $O(1)$ .

बाहरी संबंध

Dictionary of Algorithms and Data Structures: Height-balanced binary search tree
GNU libavl, a LGPL-licensed library of binary tree implementations in C, with documentation

[knuth-1] 1.0 ^1.1 ^1.2 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.

[2] Cuckoo hashing provides worst-case lookup performance of $O(1)$ .

[1]

[2]

@@ Line 1: / Line 1: @@
 {{short description|Any node-based binary search tree that automatically keeps its height the same}}
 [[Image:Unbalanced binary tree.svg|thumb|right|251px|असंतुलित वृक्ष का उदाहरण; रूट से नोड तक पथ का अनुसरण करने पर औसतन 3.27 नोड एक्सेस की आवश्यकता होती है]]
-[[Image:AVLtreef.svg|thumb|right|251px|ऊंचाई-संतुलित होने के बाद वही पेड़; औसत पथ प्रयास घटकर 3.00 नोड पहुंच हो गया]][[कंप्यूटर विज्ञान]] में, एक सेल्फ-बैलेंसिंग [[बाइनरी सर्च ट्री]] (बीएसटी) कोई भी [[ नोड (कंप्यूटर विज्ञान) |नोड (कंप्यूटर विज्ञान)]] -आधारित बाइनरी सर्च ट्री है जो मनमाने आइटम सम्मिलन और विलोपन की स्थिति में स्वचालित रूप से अपनी ऊंचाई (रूट के नीचे के स्तर की अधिकतम संख्या) को छोटा रखता है। .<ref name="knuth">[[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998. {{ISBN|0-201-89685-0}}. Section 6.2.3: Balanced Trees, pp.458–481.</ref>
+[[Image:AVLtreef.svg|thumb|right|251px|ऊंचाई-संतुलित होने के बाद वही वृक्ष; औसत पथ प्रयास घटकर 3.00 नोड पहुंच हो गया]][[कंप्यूटर विज्ञान]] में, एक स्व-संतुलन [[बाइनरी सर्च ट्री|द्विआधारी अन्वेषण वृक्ष]] (बीएसटी) कोई भी [[ नोड (कंप्यूटर विज्ञान) |नोड]] -आधारित एक द्विआधारी अन्वेषण वृक्ष होता है जो एकपक्षीय वस्तु एकीकरण और विलोपन की स्थिति में स्वचालित रूप से अपनी ऊंचाई (जड़ के नीचे के स्तर की अधिकतम संख्या) को छोटा रखता है।<ref name="knuth">[[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998. {{ISBN|0-201-89685-0}}. Section 6.2.3: Balanced Trees, pp.458–481.</ref>
-जब ये ऑपरेशन स्व-संतुलन बाइनरी सर्च ट्री के लिए डिज़ाइन किए जाते हैं, तो इसमें पेड़ की ऊंचाई को असीमित रूप से बढ़ाने के खिलाफ एहतियाती उपाय शामिल होते हैं, ताकि इन [[अमूर्त डेटा प्रकार]] को स्व-संतुलन विशेषता प्राप्त हो।
+जब ये परिचालन स्व-संतुलन द्विआधारी अन्वेषण वृक्ष के लिए डिज़ाइन किए जाते हैं, तो इसमें वृक्ष की ऊंचाई को असीमित रूप से बढ़ाने के विरुद्ध सतर्क उपाय सम्मलित होते हैं, जिससें इन [[अमूर्त डेटा प्रकार]] को स्व-संतुलन विशेषता प्राप्त होती है।
-ऊंचाई-संतुलित बाइनरी पेड़ों के लिए, ऊंचाई को लघुगणक के रूप में परिभाषित किया गया है <math>O(\log n)</math> संख्या में <math>n</math> वस्तुओं का. यह कई बाइनरी खोज पेड़ों का मामला है, जैसे कि [[एवीएल पेड़]] और लाल-काले पेड़। स्प्ले पेड़ और [[ फँसाना |फँसाना]] ्स स्व-संतुलन वाले हैं लेकिन ऊंचाई-संतुलित नहीं हैं, क्योंकि उनकी ऊंचाई वस्तुओं की संख्या में लघुगणक होने की गारंटी नहीं है।
+ऊंचाई-संतुलित बाइनरी वृक्षों के लिए, ऊंचाई को वस्तुओं की संख्या <math>n</math> में लघुगणक <math>O(\log n)</math> के रूप में परिभाषित किया जाता है। यह कई द्विआधारी अन्वेषण वृक्ष जैसे कि [[एवीएल पेड़|एवीएल वृक्ष]] और लाल-काले वृक्ष की स्थितियां है। स्प्ले वृक्ष और [[ फँसाना |ट्रीप्स]] स्व -संतुलन वाले होते हैं परन्तु ऊंचाई-संतुलित नहीं होती  हैं, क्योंकि उनकी ऊंचाई वस्तुओं की संख्या में लघुगणक होने के लिए आश्वस्त नहीं करती है।
-स्व-संतुलन बाइनरी खोज पेड़ परिवर्तनीय आदेशित [[सूची (कंप्यूटिंग)]] के लिए कुशल कार्यान्वयन प्रदान करते हैं, और इसका उपयोग अन्य अमूर्त डेटा संरचनाओं जैसे सहयोगी सरणी, [[प्राथमिकता कतार]] और सेट (अमूर्त डेटा प्रकार) के लिए किया जा सकता है।
+स्व-संतुलन द्विआधारी अन्वेषण वृक्ष परिवर्तनीय आदेशित [[सूची (कंप्यूटिंग)|सूचीयों]] के लिए कुशल कार्यान्वयन प्रदान करते हैं, और इसका उपयोग अन्य अमूर्त डेटा संरचनाओं जैसे सहयोगी सरणी, [[प्राथमिकता कतार]] और सेट (अमूर्त डेटा प्रकार) के लिए भी किया जा सकता है।
-== सिंहावलोकन ==
+== अवलोकन ==
-[[File:BinaryTreeRotations.svg|thumb|300px|सही या बिल्कुल सही संतुलन बनाए रखने के लिए स्व-संतुलन बाइनरी पेड़ों पर पेड़ का घूमना बहुत आम आंतरिक संचालन है।]]बाइनरी सर्च ट्री (बीएसटी) पर अधिकांश ऑपरेशन में पेड़ की ऊंचाई के सीधे आनुपातिक समय लगता है, इसलिए ऊंचाई को छोटा रखना वांछनीय है। ऊँचाई h वाले एक बाइनरी ट्री में अधिकतम ज्यामितीय श्रृंखला#बंद-फ़ॉर्म सूत्र|2 हो सकता है<sup>0</sup>+2<sup>1</sup>+···+2<sup>h</sup>=2<sup>h+1</sup>−1 नोड्स. यह इस प्रकार है कि n नोड्स और ऊँचाई h वाले किसी भी पेड़ के लिए:
+[[File:BinaryTreeRotations.svg|thumb|300px|सही या बिल्कुल सही संतुलन बनाए रखने के लिए स्व-संतुलन बाइनरी वृक्षों पर वृक्ष का घूमना बहुत आम आंतरिक संचालन है।]]द्विआधारी अन्वेषण वृक्ष (बीएसटी) पर सामान्यतः परिचालन में वृक्ष की ऊंचाई के सीधे आनुपातिक समय लगता है, इसलिए ऊंचाई को छोटा रखना आवश्क होता है। h ऊँचाई वाले एक द्विआधारी वृक्ष में अधिकतम 2<sup>0</sup>+2<sup>1</sup>+···+2<sup>''h''</sup> = 2<sup>''h''+1</sup>−1 नोड्स हो सकते हैं। यह इस प्रकार है कि n नोड्स और h ऊँचाई  वाले किसी भी वृक्ष के लिए:
 :<math>n\le 2^{h+1}-1</math>
@@ Line 16: / Line 16: @@
 :<math>h\ge\lceil\log_2(n+1)-1\rceil\ge \lfloor\log_2 n\rfloor</math>.
-दूसरे शब्दों में, n नोड्स वाले बाइनरी ट्री की न्यूनतम ऊंचाई है {{nowrap|[[logarithm|log]]<sub>2</sub>(''n''),}} [[फर्श और छत के कार्य]]; वह है, <math> \lfloor \log_2 n\rfloor</math>.<ref name="knuth"/>
+दूसरे शब्दों में, n नोड्स वाले द्विआधारी वृक्ष की न्यूनतम ऊँचाई  {{nowrap|[[logarithm|log]]<sub>2</sub>(''n'')}} होती है, जिसे[[फर्श और छत के कार्य|राउंडेड (गोलाकार)]] किया जाता है ; जो <math> \lfloor \log_2 n\rfloor</math>होता है।<ref name="knuth"/>
-हालाँकि, BST आइटम प्रविष्टि के लिए सबसे सरल एल्गोरिदम सामान्य स्थितियों में ऊँचाई n वाला एक पेड़ उत्पन्न कर सकता है। उदाहरण के लिए, जब आइटम को क्रमबद्ध [[कुंजी (डेटाबेस)]] क्रम में डाला जाता है, तो पेड़ एन नोड्स के साथ एक लिंक की गई सूची में बदल जाता है। दोनों स्थितियों के बीच प्रदर्शन में अंतर बहुत बड़ा हो सकता है: उदाहरण के लिए, जब n = 1,000,000, न्यूनतम ऊंचाई है <math> \lfloor \log_2(1,000,000) \rfloor = 19 </math>.
+चूकिं, बीएसटी वस्तु प्रविष्टि के लिए सबसे सरल एल्गोरिदम सामान्य स्थितियों में ऊँचाई n वाला एक वृक्ष उत्पन्न कर सकता है। उदाहरण के लिए, जब वस्तु  को क्रमबद्ध [[कुंजी (डेटाबेस)]] क्रम में डाला जाता है, तो वृक्ष एन नोड्स के साथ एक लिंक की गई सूची में बदल जाता है। दोनों स्थितियों के बीच प्रदर्शन में अंतर बहुत बड़ा हो सकता है: उदाहरण के लिए, जब n = 1,000,000, न्यूनतम ऊंचाई <math> \lfloor \log_2(1,000,000) \rfloor = 19 </math> होती है।
-यदि डेटा आइटम समय से पहले ज्ञात हैं, तो यादृच्छिक क्रम में मान जोड़कर, ऊंचाई को औसत अर्थ में छोटा रखा जा सकता है, जिसके परिणामस्वरूप एक यादृच्छिक [[यादृच्छिक बाइनरी खोज वृक्ष]] है। हालाँकि, ऐसी कई स्थितियाँ हैं (जैसे [[ऑनलाइन एल्गोरिदम]]) जहां यह [[यादृच्छिक एल्गोरिदम]] व्यवहार्य नहीं है।
+यदि डेटा वस्तु  समय से पहले ज्ञात होता हैं, तो यादृच्छिक क्रम में मान जोड़कर, ऊंचाई को औसत अर्थ में छोटा रखा जा सकता है, जिसके परिणामस्वरूप एक [[यादृच्छिक बाइनरी खोज वृक्ष|यादृच्छिक द्विआधारी अन्वेषण वृक्ष]] निर्मित होता है। चूकिं, ऐसी कई स्थितियाँ हैं (जैसे [[ऑनलाइन एल्गोरिदम]]) जहां यह [[यादृच्छिक एल्गोरिदम]] कार्य नहीं करते है।
-स्व-संतुलन वाले बाइनरी पेड़ कुंजी प्रविष्टि समय पर पेड़ पर परिवर्तन (जैसे कि [[पेड़ का घूमना]]) करके इस समस्या को हल करते हैं, ताकि ऊंचाई को आनुपातिक रखा जा सके। {{nowrap|log<sub>2</sub>(''n'').}} हालांकि एक निश्चित [[कम्प्यूटेशनल ओवरहेड]] शामिल है, यह हमेशा आवश्यक लुकअप लागत से बड़ा नहीं है और सभी परिचालनों के तेजी से निष्पादन को सुनिश्चित करके उचित ठहराया जा सकता है।
+स्व-संतुलन वाले द्विआधारी वृक्ष कुंजी प्रविष्टि समय पर वृक्ष पर परिवर्तन (जैसे कि [[पेड़ का घूमना|वृक्ष का घूमना]]) करके इस समस्या को हल करते हैं, जिससें ऊंचाई {{nowrap|log<sub>2</sub>(''n'')}} को आनुपातिक रखा जा सके। चूकिं एक निश्चित [[कम्प्यूटेशनल ओवरहेड|ओवरहेड]] सम्मलित होता है, यह हमेशा आवश्यक लुकअप लागत से बड़ा नहीं होता है और सभी परिचालनों के तेजी से निष्पादन को सुनिश्चित करके उचित घोषित किया जा सकता है।
-जबकि अपेक्षित न्यूनतम ऊंचाई के साथ बीएसटी बनाए रखना संभव है <math>O(\log n)</math> समय संचालन (लुकअप/सम्मिलन/हटाना), ऐसी संरचना को बनाए रखने के लिए आवश्यक अतिरिक्त स्थान की आवश्यकताएं खोज समय में कमी से अधिक होती हैं। तुलना के लिए, एक एवीएल पेड़ को इष्टतम ऊंचाई के 1.44 के कारक के भीतर होने की गारंटी दी जाती है, जबकि एक सरल कार्यान्वयन में भंडारण के केवल दो अतिरिक्त बिट्स की आवश्यकता होती है।<ref name="knuth"/>इसलिए, अधिकांश स्व-संतुलन बीएसटी एल्गोरिदम ऊंचाई को इस निचली सीमा के एक स्थिर कारक के भीतर रखते हैं।
+जबकि अपेक्षित न्यूनतम ऊंचाई के साथ और <math>O(\log n)</math> समय संचालन (लुकअप/सम्मिलन/हटाना) के साथ बीएसटी बनाए रखना संभव है, ऐसी संरचना को बनाए रखने के लिए आवश्यक अतिरिक्त स्थान की आवश्यकताएं अन्वेषण समय में कमी से अधिक होती हैं। तुलना के लिए, एक एवीएल वृक्ष को सर्वोत्तम ऊंचाई के 1.44 के कारक के भीतर होने का आश्वासन दिया जाता है, जबकि एक सरल कार्यान्वयन में संचय के मात्र  दो अतिरिक्त बिट्स कीआवश्यकता होती है।<ref name="knuth"/>इसलिए, सामान्यतः स्व-संतुलन बीएसटी एल्गोरिदम ऊंचाई को इस निचली सीमा के एक स्थिर कारक के भीतर रखते हैं।
-[[asymptotic]] ([[ बिग ओ अंकन ]]|बिग-ओ) अर्थ में, एन आइटम युक्त एक स्व-संतुलन बीएसटी संरचना किसी आइटम को देखने, सम्मिलित करने और हटाने की अनुमति देती है। <math>O(\log n)</math> सबसे खराब स्थिति का समय, और सभी वस्तुओं का [[क्रमानुसार पुनरावृत्ति]] <math>O(n)</math> समय। कुछ कार्यान्वयन के लिए ये प्रति-ऑपरेशन समय सीमाएँ हैं, जबकि अन्य के लिए ये संचालन के अनुक्रम पर परिशोधित विश्लेषण सीमाएँ हैं। ये समय सभी डेटा संरचनाओं के बीच स्पर्शोन्मुख रूप से इष्टतम हैं जो केवल तुलनाओं के माध्यम से कुंजी में हेरफेर करते हैं।
+[[asymptotic|एसिम्प्टोटिक (स्पर्शोन्मुख]]) ([[ बिग ओ अंकन | "बिग-ओ"]] ) अर्थ में, n वस्तु युक्त एक स्व-संतुलन बीएसटी संरचना किसी वस्तु  को देखने, सम्मिलित करने और हटाने की अनुमति देती है। <math>O(\log n)</math> सबसे खराब स्थिति का समय, और सभी वस्तुओं का [[क्रमानुसार पुनरावृत्ति]]  समय <math>O(n)</math>होता है। कुछ कार्यान्वयन के लिए ये प्रति-परिचालन समय सीमाएँ होती हैं, जबकि अन्य के लिए ये संचालन के अनुक्रम पर परिशोधित विश्लेषण सीमाएँ होती हैं। ये समय सभी डेटा संरचनाओं के बीच स्पर्शोन्मुख रूप से सर्वोत्तम होते हैं जो मात्र तुलनाओं के माध्यम से कुंजी में परिवर्तन करते हैं।
 == कार्यान्वयन ==
-इस प्रकार के पेड़ को लागू करने वाली डेटा संरचनाओं में शामिल हैं:
+इस प्रकार के वृक्ष को प्रयुक्त करने वाली डेटा संरचनाओं में सम्मलित हैं:
-* 2-3 पेड़
+* 2-3 वृक्ष
-*[[एए पेड़]]
+*[[एए पेड़|एए वृक्ष]]
 *एवीएल वृक्ष
 *[[बी-वृक्ष]]
-* लाल-काला पेड़
+* लाल-काला वृक्ष
-*[[बलि का बकरा पेड़]]
+*[[बलि का बकरा पेड़|बलि का बकरा वृक्ष]]
-* छींटे का पेड़
+* छींटे का वृक्ष
-* [[टैंगो पेड़]]
+* [[टैंगो पेड़|टैंगो वृक्ष]]
 * जाल बिछाना
 * वजन-संतुलित वृक्ष
 == अनुप्रयोग ==
-स्व-संतुलन बाइनरी खोज पेड़ों का उपयोग प्राथमिकता कतारों जैसी आदेशित सूचियों के निर्माण और रखरखाव के लिए प्राकृतिक तरीके से किया जा सकता है। इनका उपयोग सहयोगी सरणियों के लिए भी किया जा सकता है; कुंजी-मूल्य जोड़े को केवल कुंजी के आधार पर एक क्रम के साथ डाला जाता है। इस क्षमता में, स्व-संतुलन वाले बीएसटी के पास अपने मुख्य प्रतिद्वंद्वी, [[हैश तालिका]]ओं पर सहयोगी सरणी#कुशल प्रतिनिधित्व होते हैं। स्व-संतुलन बीएसटी का एक फायदा यह है कि वे कुंजी क्रम में वस्तुओं की तेजी से (वास्तव में, असम्बद्ध रूप से इष्टतम) गणना की अनुमति देते हैं, जो हैश टेबल प्रदान नहीं करते हैं। एक नुकसान यह है कि उनके लुकअप एल्गोरिदम अधिक जटिल हो जाते हैं जब एक ही कुंजी के साथ कई आइटम हो सकते हैं। सेल्फ-बैलेंसिंग बीएसटी का सबसे खराब स्थिति वाला लुकअप प्रदर्शन अन्य की तुलना में बेहतर है<ref>[[Cuckoo hashing]] provides worst-case lookup performance of <math>O(1)</math>.</ref> हैश टेबल (<math>O(\log n)</math> की तुलना में <math>O(n)</math>), लेकिन औसत-मामले में प्रदर्शन बदतर है (<math>O(\log n)</math> की तुलना में <math>O(1)</math>).
+स्व-संतुलन द्विआधारी अन्वेषण वृक्षों का उपयोग प्राथमिकता कतारों जैसी आदेशित सूचियों के निर्माण और रखरखाव के लिए प्राकृतिक तरीके से किया जा सकता है। इनका उपयोग सहयोगी सरणियों के लिए भी किया जा सकता है; कुंजी-मूल्य जोड़े को केवल कुंजी के आधार पर एक क्रम के साथ डाला जाता है। इस क्षमता में, स्व-संतुलन वाले बीएसटी के पास अपने मुख्य प्रतिद्वंद्वी, [[हैश तालिका|हैश तालिकाओं]] पर सहयोगी सरणी कुशल प्रतिनिधित्व होते हैं। स्व-संतुलन बीएसटी का एक लाभ यह होता है कि वे कुंजी क्रम में वस्तुओं की शीघ्रता से (वास्तव में, असम्बद्ध रूप से सर्वोत्तम) गणना करने की अनुमति देते हैं, जो हैश टेबल प्रदान नहीं करते हैं। एक हानि यह है कि उनके लुकअप एल्गोरिदम अधिक जटिल हो जाते हैं जब एक ही कुंजी के साथ कई वस्तु  हो सकते हैं। स्व-संतुलन बीएसटी का सबसे खराब स्थिति वाला लुकअप प्रदर्शन अन्य हैश टेबल (<math>O(\log n)</math> की तुलना में <math>O(n)</math>) की तुलना में श्रेष्ट होता है<ref>[[Cuckoo hashing]] provides worst-case lookup performance of <math>O(1)</math>.</ref>, परन्तु औसत-स्थितियों में (<math>O(\log n)</math> की तुलना में <math>O(1)</math>) प्रदर्शन अत्यधिक बेकार  होता है।
-स्व-संतुलन बीएसटी का उपयोग किसी भी एल्गोरिदम को कार्यान्वित करने के लिए किया जा सकता है जिसके लिए इष्टतम सबसे खराब स्थिति वाले स्पर्शोन्मुख प्रदर्शन को प्राप्त करने के लिए परिवर्तनीय आदेशित सूचियों की आवश्यकता होती है। उदाहरण के लिए, यदि [[बाइनरी ट्री सॉर्ट]] को स्व-संतुलन बीएसटी के साथ कार्यान्वित किया जाता है, तो हमारे पास वर्णन करने में बहुत आसान लेकिन [[स्पर्शोन्मुख रूप से इष्टतम]] है <math>O(n \log n)</math> छँटाई एल्गोरिथ्म. इसी तरह, [[कम्प्यूटेशनल ज्यामिति]] में कई एल्गोरिदम लाइन खंड चौराहे की समस्या और [[बिंदु स्थान]] की समस्या जैसी समस्याओं को कुशलतापूर्वक हल करने के लिए स्व-संतुलन बीएसटी पर भिन्नता का फायदा उठाते हैं। (हालांकि, औसत-मामले के प्रदर्शन के लिए, स्व-संतुलन बीएसटी अन्य समाधानों की तुलना में कम कुशल हो सकता है। बाइनरी ट्री सॉर्ट, विशेष रूप से, [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]] , [[जल्दी से सुलझाएं]] या [[ढेर बनाएं और छांटें]] की तुलना में धीमी होने की संभावना है, क्योंकि ट्री-बैलेंसिंग ओवरहेड के कारण साथ ही [[कैश (कंप्यूटिंग)]] एक्सेस पैटर्न।)
+स्व-संतुलन बीएसटी का उपयोग किसी भी एल्गोरिदम को कार्यान्वित करने के लिए किया जा सकता है जिसके लिए सर्वोत्तम सबसे खराब स्थिति वाले स्पर्शोन्मुख प्रदर्शन को प्राप्त करने के लिए परिवर्तनीय आदेशित सूचियों की आवश्यकता होती है। उदाहरण के लिए, यदि [[बाइनरी ट्री सॉर्ट|द्विआधारी वृक्ष सॉर्ट]] को स्व-संतुलन बीएसटी के साथ कार्यान्वित किया जाता है, तो हमारे पास वर्णन करने में बहुत आसान परन्तु [[स्पर्शोन्मुख रूप से इष्टतम|स्पर्शोन्मुख रूप से सर्वोत्तम]] <math>O(n \log n)</math> एल्गोरिथ्म होता है।. इसी तरह, [[कम्प्यूटेशनल ज्यामिति]] में कई एल्गोरिदम लाइन खंड चौराहे की समस्या और [[बिंदु स्थान]] की समस्या जैसी समस्याओं को कुशलतापूर्वक हल करने के लिए स्व-संतुलन बीएसटी पर भिन्नता का लाभ उठाते हैं। (चूकिं, औसत-स्थितियों के प्रदर्शन के लिए, स्व-संतुलन बीएसटी अन्य समाधानों की तुलना में कम कुशल हो सकता है, द्विआधारी वृक्ष सॉर्ट, विशेष रूप से, [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]], [[जल्दी से सुलझाएं|क्विकसॉर्ट]] या [[ढेर बनाएं और छांटें|हीपसॉर्ट]] की तुलना में ट्री-बैलेंसिंग ओवरहेड के कारण साथ ही [[कैश (कंप्यूटिंग)]] एक्सेस पैटर्न के कारण इनमे धीमी होने की संभावना होती है।)
-स्व-संतुलन बीएसटी लचीली डेटा संरचनाएं हैं, अतिरिक्त जानकारी को कुशलतापूर्वक रिकॉर्ड करने या नए ऑपरेशन करने के लिए उन्हें विस्तारित करना आसान है। उदाहरण के लिए, कोई एक निश्चित संपत्ति वाले प्रत्येक उपट्री में नोड्स की संख्या रिकॉर्ड कर सकता है, जिससे वह उस संपत्ति के साथ एक निश्चित कुंजी श्रेणी में नोड्स की संख्या की गणना कर सकता है। <math>O(\log n)</math> समय। इन एक्सटेंशन का उपयोग, उदाहरण के लिए, डेटाबेस क्वेरीज़ या अन्य सूची-प्रसंस्करण एल्गोरिदम को अनुकूलित करने के लिए किया जा सकता है।
+स्व-संतुलन बीएसटी लचीली डेटा संरचनाएं होती हैं, अतिरिक्त जानकारी को कुशलतापूर्वक लेख्यांकित करने या नए परिचालन करने के लिए उन्हें विस्तारित करना आसान होता है। उदाहरण के लिए, कोई एक निश्चित संपत्ति वाले प्रत्येक उपट्री में नोड्स की संख्या लेख्यांकित कर सकता है, जिससे वह  <math>O(\log n)</math> समय समय में उस संपत्ति के साथ एक निश्चित कुंजी श्रेणी में नोड्स की संख्या की गणना कर सकता है। इन एक्सटेंशन का उपयोग, उदाहरण के लिए, डेटाबेस क्वेरीज़ या अन्य सूची-प्रसंस्करण एल्गोरिदम को अनुकूलित करने के लिए किया जा सकता है।
 == यह भी देखें ==

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

स्व-संतुलन बाइनरी सर्च ट्री: Difference between revisions

Namespaces

More

Page actions

Revision as of 01:06, 4 July 2023

Contents

अवलोकन

कार्यान्वयन

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

स्व-संतुलन बाइनरी सर्च ट्री: Difference between revisions

Revision as of 01:06, 4 July 2023

अवलोकन

कार्यान्वयन

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories