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

असंतुलित ट्री का उदाहरण; रूट से नोड तक पथ का अनुसरण करने पर औसतन 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 नोड्स के साथ एक जोड़ी गई सूची में बदल जाता है। दोनों स्थितियों के बीच प्रदर्शन में अंतर बहुत बड़ा हो सकता है: उदाहरण के लिए, जब 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