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

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

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

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

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

ऊंचाई-संतुलित बाइनरी वृक्षों के लिए, ऊंचाई को वस्तुओं की संख्या $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$होता है।

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

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

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

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

एसिम्प्टोटिक (स्पर्शोन्मुख) ( "बिग-ओ" ) अर्थ में, n वस्तु युक्त एक स्व-संतुलन बीएसटी संरचना किसी वस्तु को देखने, सम्मिलित करने और हटाने की अनुमति देती है। $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