जहां तक मुझे पता है कि AVL पेड़ों और Binary Search Trees के बीच की जटिलता औसत मामले में समान है, एवीएल सबसे खराब स्थिति परिदृश्यों में बीएसटी को मारने के साथ। यह मुझे एक संकेत देता है कि एवीएल हमेशा उनके साथ बातचीत करने के हर संभव तरीके से बीएसटी से बेहतर होते हैं, शायद कार्यान्वयन को संतुलित करने के लिए थोड़ा जटिलता जोड़ते हैं।एवीएल पेड़ पर बाइनरी सर्च पेड़
क्या कोई कारण है कि किसी को भी एवीएल की बजाय बीएसटी का उपयोग करना चाहिए?
सबसे पहले, सर्वोत्तम संभव प्रदर्शन प्राप्त करना प्रोग्रामिंग का अंतिम लक्ष्य नहीं है। तो, भले ही विकल्प बी हमेशा तेज था और ए की तुलना में कम स्मृति का उपभोग करता था, इसका मतलब यह नहीं है कि यह हमेशा बेहतर विकल्प है, अगर यह अधिक जटिल है। अधिक जटिल कोड लिखने में अधिक समय लगता है, समझना मुश्किल है और इसमें बग शामिल होने की अधिक संभावना है। इसलिए, यदि सरल लेकिन कम कुशल विकल्प ए आपके लिए पर्याप्त है, तो इसका मतलब है कि यह बेहतर विकल्प है।
अब, यदि आप बिना संतुलन के सरल बाइनरी खोज पेड़ (बीएसटी) के साथ एवीएल पेड़ की तुलना करना चाहते हैं, तो एवीएल अधिक स्मृति का उपभोग करेगा (प्रत्येक नोड को इसके संतुलन कारक को याद रखना होगा) और प्रत्येक ऑपरेशन धीमा हो सकता है (क्योंकि आपको आवश्यकता है संतुलन कारक बनाए रखने और कभी-कभी घूर्णन करने के लिए)।
जैसा कि आपने कहा था, बिना संतुलन के बीएसटी में बहुत बुरा (रैखिक) सबसे खराब मामला है। लेकिन अगर आपको पता है कि यह सबसे बुरा मामला आपके साथ नहीं होगा, या यदि आप ठीक हैं तो ऑपरेशन दुर्लभ मामलों में धीमा है, तो संतुलन के बिना बीएसटी एवीएल से बेहतर हो सकता है।
बिल्कुल वही कारण जिनके लिए मैं इंतजार कर रहा था। धन्यवाद और स्वीकार किया। –
मेरी धारणा है: जब आप बीएसटी का उल्लेख करते हैं, तो आप संतुलन के बिना बीएसटी का मतलब रखते हैं।
यह तर्क दिया जा सकता है कि यदि आपको एक नेविगेट करने योग्य डेटा संरचना की आवश्यकता है और आपको पता है कि आपका डेटा सबसे खराब मामला नहीं है (क्रमबद्ध) और कुछ हद तक छोटा है, तो बीएसटी (शेष राशि के बिना) पर्याप्त होगा।
लेकिन संभावना से कहीं अधिक दुर्लभ मामला है।
एवीएल पेड़ भी एक बीएसटी है लेकिन यह खुद को पुनर्व्यवस्थित कर सकता है। यह व्यवहार इसे सबसे खराब मामलों में तेजी से बनाता है। यह खुद को पुनर्व्यवस्थित करता रहता है इसलिए सबसे खराब स्थिति में यह ओ (लॉग एन) समय का उपभोग करेगा जब सादा बीएसटी ओ (एन) ले जाएगा। तो, आपके प्रश्न का उत्तर: केवल सादा बीएसटी की तुलना में एवीएल पेड़ को लागू करना हमेशा बेहतर होता है।
चूंकि बैलेंस कारकों की जांच और अद्यतन करने और नोड्स घूर्णन करने के अतिरिक्त ओवरहेड हैं, इसलिए गैर-संतुलित बीएसटी की तुलना में एवीएल पेड़ों में सम्मिलन और हटाना बहुत धीमा हो सकता है।
तंग संतुलन के कारण, खोज कभी भी रैखिक-समान समय नहीं लेती है, इसलिए आप शायद उन स्थितियों में एवीएल पेड़ों का उपयोग करना चाहेंगे जहां खोज पेड़ को अपडेट करने से अधिक लगातार संचालन होती है।
एवीएल पेड़ फैशन से बाहर हैं, आजकल उन्हें लाल-काले पेड़ से हटा दिया गया है। – starblue