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

Revision as of 10:05, 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 नोड्स के साथ एक जोड़ी गई सूची में बदल जाता है। दोनों स्थितियों के बीच प्रदर्शन में अंतर बहुत बड़ा हो सकता है: उदाहरण के लिए, जब 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: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>n</math> में लघुगणक <math>O(\log 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"/>
 चूकिं, बीएसटी वस्तु प्रविष्टि के लिए सबसे सरल एल्गोरिदम सामान्य स्थितियों में ऊँचाई n वाला एक ट्री उत्पन्न कर सकता है। उदाहरण के लिए, जब वस्तु  को क्रमबद्ध [[कुंजी (डेटाबेस)]] क्रम में डाला जाता है, तो ट्री n नोड्स के साथ एक जोड़ी गई सूची में बदल जाता है। दोनों स्थितियों के बीच प्रदर्शन में अंतर बहुत बड़ा हो सकता है: उदाहरण के लिए, जब n = 1,000,000 होता है तब न्यूनतम ऊंचाई <math> \lfloor \log_2(1,000,000) \rfloor = 19 </math> होती है।
@@ Line 22: / Line 22: @@
 यदि डेटा वस्तु  समय से पहले ज्ञात होता हैं, तो यादृच्छिक क्रम में मान जोड़कर, ऊंचाई को औसत अर्थ में छोटा रखा जा सकता है, जिसके परिणामस्वरूप एक [[यादृच्छिक बाइनरी खोज वृक्ष|यादृच्छिक बाइनरी सर्च ट्री]] निर्मित होता है। चूकिं, ऐसी कई स्थितियाँ हैं (जैसे [[ऑनलाइन एल्गोरिदम]]) जहां यह [[यादृच्छिक एल्गोरिदम]] कार्य नहीं करते है।
-सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री कुंजी प्रविष्टि समय पर ट्री पर परिवर्तन (जैसे कि [[पेड़ का घूमना|ट्री  का घूमना]]) करके इस समस्या को हल करते हैं, जिससें ऊंचाई {{nowrap|log<sub>2</sub>(''n'')}} को आनुपातिक रखा जाता है। चूकिं एक निश्चित [[कम्प्यूटेशनल ओवरहेड|ओवरहेड]] सम्मलित होता है, यह हमेशा आवश्यक लुकअप लागत से बड़ा नहीं होता है और इस प्रकार सभी परिचालनों के शीघ्रता से निष्पादन को सुनिश्चित करके उचित घोषित किया जा सकता है।
+सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री कुंजी प्रविष्टि समय पर ट्री पर परिवर्तन (जैसे कि [[पेड़ का घूमना|ट्री का घूमना]]) करके इस समस्या को हल करते हैं, जिससें ऊंचाई {{nowrap|log<sub>2</sub>(''n'')}} को आनुपातिक रखा जाता है। चूकिं एक निश्चित [[कम्प्यूटेशनल ओवरहेड|ओवरहेड]] सम्मलित होता है, यह हमेशा आवश्यक लुकअप लागत से बड़ा नहीं होता है और इस प्रकार सभी परिचालनों के शीघ्रता से निष्पादन को सुनिश्चित करके इसे उचित घोषित किया जा सकता है।
 इस प्रकार अपेक्षित न्यूनतम ऊंचाई के साथ और <math>O(\log n)</math> समय संचालन (लुकअप/सम्मिलन/हटाना) के साथ बीएसटी बनाए रखना संभव हो जाता है, ऐसी संरचना को बनाए रखने के लिए आवश्यक अतिरिक्त स्थान की आवश्यकताएं अन्वेषण समय में कमी से अधिक होती हैं। तुलना के लिए, एक एवीएल ट्री को सर्वोत्तम ऊंचाई के 1.44 के कारक के भीतर होने का आश्वासन दिया जाता है, जबकि एक सरल कार्यान्वयन में संचय के मात्र दो अतिरिक्त बिट्स कीआवश्यकता होती है।<ref name="knuth"/>इसलिए, सामान्यतः स्व-संतुलन बीएसटी एल्गोरिदम ऊंचाई को इस निचली सीमा के एक स्थिर कारक के भीतर रखते हैं।
-[[asymptotic|एसिम्प्टोटिक (स्पर्शोन्मुख]]) ([[ बिग ओ अंकन | "बिग-ओ"]] ) अर्थ में, n वस्तु युक्त सेल्फ-बैलेंसिंग बीएसटी संरचना किसी वस्तु को देखने, सम्मिलित करने और हटाने की अनुमति देती है। <math>O(\log n)</math> सबसे बेकार स्थिति का समय होता है, और सभी वस्तुओं का [[क्रमानुसार पुनरावृत्ति]]  समय <math>O(n)</math>होता है। कुछ कार्यान्वयन के लिए ये प्रति-परिचालन समय सीमाएँ होती हैं, जबकि अन्य के लिए ये संचालन के अनुक्रम पर परिशोधित विश्लेषण सीमाएँ होती हैं। ये समय सभी डेटा संरचनाओं के बीच स्पर्शोन्मुख रूप से सर्वोत्तम होते हैं जो मात्र तुलनाओं के माध्यम से कुंजी में परिवर्तन करते हैं।
+[[asymptotic|एसिम्प्टोटिक (स्पर्शोन्मुख]]) ([[ बिग ओ अंकन | "बिग-ओ"]] ) अर्थ में, n वस्तु युक्त सेल्फ-बैलेंसिंग बीएसटी संरचना किसी वस्तु को देखने, सम्मिलित करने और हटाने की अनुमति देती है। <math>O(\log n)</math> सबसे बेकार स्थिति का समय होता है, और सभी वस्तुओं का [[क्रमानुसार पुनरावृत्ति]]  समय <math>O(n)</math> होता है। कुछ कार्यान्वयन के लिए ये प्रति-परिचालन समय सीमाएँ होती हैं, जबकि अन्य के लिए ये संचालन के अनुक्रम पर परिशोधित विश्लेषण सीमाएँ होती हैं। ये समय सभी डेटा संरचनाओं के बीच स्पर्शोन्मुख रूप से सर्वोत्तम होते हैं जो मात्र तुलनाओं के माध्यम से कुंजी में परिवर्तन करते हैं।
 == कार्यान्वयन ==
@@ Line 39: / Line 39: @@
 * स्पल ट्री
 * [[टैंगो पेड़|टैंगो ट्री]]
-* ट्राप
+* [[ फँसाना |ट्रीप्स]]
 * वजन-संतुलित ट्री
 == अनुप्रयोग ==
-सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री ों का उपयोग प्राथमिकता कतारों जैसी आदेशित सूचियों के निर्माण और रखरखाव के लिए प्राकृतिक तरीके से किया जा सकता है। इनका उपयोग सहयोगी सरणियों के लिए भी किया जा सकता है; कुंजी-मूल्य जोड़े को केवल कुंजी के आधार पर एक क्रम के साथ डाला जाता है। इस क्षमता में, स्व-संतुलन वाले बीएसटी के पास अपने मुख्य प्रतिद्वंद्वी, [[हैश तालिका|हैश तालिकाओं]] पर सहयोगी सरणी कुशल प्रतिनिधित्व होते हैं। स्व-संतुलन बीएसटी का एक लाभ यह होता है कि वे कुंजी क्रम में वस्तुओं की शीघ्रता से (वास्तव में, असम्बद्ध रूप से सर्वोत्तम) गणना करने की अनुमति देते हैं, जो हैश टेबल प्रदान नहीं करते हैं। एक हानि यह है कि उनके लुकअप एल्गोरिदम अधिक जटिल हो जाते हैं जब एक ही कुंजी के साथ कई वस्तु  हो सकते हैं। स्व-संतुलन बीएसटी का सबसे खराब स्थिति वाला लुकअप प्रदर्शन अन्य हैश टेबल (<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(\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> समय समय में उस गुण के साथ एक निश्चित कुंजी श्रेणी में नोड्स की संख्या की गणना कर सकता है। इन एक्सटेंशन का उपयोग, उदाहरण के लिए, डेटाबेस क्वेरीज़ या अन्य सूची-प्रसंस्करण एल्गोरिदम को अनुकूलित करने के लिए किया जा सकता है।
 == यह भी देखें ==
@@ Line 54: / Line 54: @@
 * [[संलयन वृक्ष|संलयन ट्री]]
 * [[सूची छोड़ें]]
-* छँटाई
+* छँटाई(सोर्टिंग)
 == संदर्भ ==

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 10:05, 4 July 2023

Contents

अवलोकन

कार्यान्वयन

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:05, 4 July 2023

अवलोकन

कार्यान्वयन

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories