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

Latest revision as of 10:57, 26 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}}
-{{refimprove|date=November 2010}}
+[[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>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 17: / 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 नोड्स के साथ एक जोड़ी गई सूची में बदल जाता है। दोनों स्थितियों के बीच प्रदर्शन में अंतर बहुत बड़ा हो सकता है: उदाहरण के लिए, जब 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> समय समय में उस गुण के साथ एक निश्चित कुंजी श्रेणी में नोड्स की संख्या की गणना कर सकता है। इन एक्सटेंशन का उपयोग, उदाहरण के लिए, डेटाबेस क्वेरीज़ या अन्य सूची-प्रसंस्करण एल्गोरिदम को अनुकूलित करने के लिए किया जा सकता है।
 == यह भी देखें ==
 * [[डेटा संरचना खोजें]]
 * डे-स्टाउट-वॉरेन एल्गोरिदम
-* [[संलयन वृक्ष]]
+* [[संलयन वृक्ष|संलयन ट्री]]
 * [[सूची छोड़ें]]
-* छँटाई
+* छँटाई(सोर्टिंग)
 == संदर्भ ==
@@ Line 68: / Line 67: @@
 {{Data structures}}
-{{DEFAULTSORT:Self-Balancing Binary Search Tree}}[[Category: बाइनरी पेड़]] [[Category: पेड़ (डेटा संरचनाएं)]]
+{{DEFAULTSORT:Self-Balancing Binary Search Tree}}
+[[Category:Collapse templates|Self-Balancing Binary Search Tree]]
+[[Category:Created On 27/06/2023|Self-Balancing Binary Search Tree]]
-[[Category: Machine Translated Page]]
+[[Category:Lua-based templates|Self-Balancing Binary Search Tree]]
-[[Category:Created On 27/06/2023]]
+[[Category:Machine Translated Page|Self-Balancing Binary Search Tree]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Self-Balancing Binary Search Tree]]
+[[Category:Pages with script errors|Self-Balancing Binary Search Tree]]
+[[Category:Sidebars with styles needing conversion|Self-Balancing Binary Search Tree]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Self-Balancing Binary Search Tree]]
+[[Category:Templates generating microformats|Self-Balancing Binary Search Tree]]
+[[Category:Templates that add a tracking category|Self-Balancing Binary Search Tree]]
+[[Category:Templates that are not mobile friendly|Self-Balancing Binary Search Tree]]
+[[Category:Templates that generate short descriptions|Self-Balancing Binary Search Tree]]
+[[Category:Templates using TemplateData|Self-Balancing Binary Search Tree]]
+[[Category:Wikipedia metatemplates|Self-Balancing Binary Search Tree]]
+[[Category:पेड़ (डेटा संरचनाएं)|Self-Balancing Binary Search Tree]]
+[[Category:बाइनरी पेड़|Self-Balancing Binary Search Tree]]

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

Latest revision as of 10:57, 26 July 2023

Contents

अवलोकन

कार्यान्वयन

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 10:57, 26 July 2023

अवलोकन

कार्यान्वयन

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories