स्व-संतुलन द्विआधारी खोज वृक्ष

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

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

कंप्यूटर विज्ञान में, एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री (बीएसटी) कोई भी नोड (कंप्यूटर विज्ञान) -आधारित बाइनरी सर्च ट्री है जो मनमाने आइटम सम्मिलन और विलोपन की स्थिति में स्वचालित रूप से अपनी ऊंचाई (रूट के नीचे के स्तर की अधिकतम संख्या) को छोटा रखता है। .

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

ऊंचाई-संतुलित बाइनरी पेड़ों के लिए, ऊंचाई को लघुगणक के रूप में परिभाषित किया गया है $O(\log n)$ संख्या में $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$.

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

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

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

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

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

कार्यान्वयन

इस प्रकार के पेड़ को लागू करने वाली डेटा संरचनाओं में शामिल हैं:

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

अनुप्रयोग

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

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

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

यह भी देखें

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

बाहरी संबंध

• 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