एवीएल पेड़ बनाम बी-पेड़

Question

एक एवीएल पेड़ बी-पेड़ से अलग कैसे होता है?

Answer 1

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

Answer 2

एवीएल आत्म संतुलन है, यह गारंटी देता है कि सभी परिचालन औसतन (सबसे खराब) हैं और सबसे खराब मामले हैं।

Answer 3

एक एवीएल पेड़ एक स्व-संतुलन बाइनरी खोज पेड़ है, जो ओ (लॉग एन) ऊंचाई को बनाए रखने के लिए संतुलित है।

एक बी-पेड़ एक संतुलित पेड़ है, लेकिन यह एक बाइनरी पेड़ नहीं है। नोड्स में अधिक बच्चे होते हैं, जो प्रति-नोड खोज समय बढ़ाते हैं लेकिन खोज की आवश्यकता वाले नोड्स की संख्या कम हो जाती है। यह उन्हें डिस्क-आधारित पेड़ों के लिए अच्छा बनाता है। अधिक जानकारी के लिए, Wikipedia article देखें।

Answer 4

एवीएल पेड़ और बी-पेड़ दोनों समान हैं कि वे डेटा संरचनाएं हैं, उनकी आवश्यकताओं के माध्यम से, कारण अपने संबंधित पेड़ों की ऊंचाई को कम किया जाना चाहिए। यह "शॉर्टनेस" ओ (लॉग एन) समय में प्रदर्शन करने की अनुमति देता है, क्योंकि पढ़ने की सबसे बड़ी संख्या पेड़ की ऊंचाई से मेल खाती है।

5 
/\ 
    3 7 
//\ 
1 6 9 

यह एक AVL पेड़ है, और इसके मूल में एक द्विआधारी खोज वृक्ष है। हालांकि, यह आत्म-संतुलन है, जिसका अर्थ यह है कि जैसे ही आप पेड़ में तत्व जोड़ते हैं, वैसे ही यह ऊंचाई की वर्दी के रूप में बनाए रखने के लिए खुद को पुन: स्थापित करेगा। असल में, यह लंबी शाखाओं की अनुमति नहीं देगा।

ए बी-पेड़ यह भी करता है, लेकिन एक अलग पुन: संतुलन योजना के माध्यम से। यह लिखने के लिए थोड़ा जटिल है, लेकिन यदि आप Google को "बी-पेड़ एनीमेशन" खोजते हैं तो वहां कुछ वास्तव में अच्छे सेब हैं जो बी-पेड़ को अच्छी तरह से समझाते हैं।

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

जब डेटा संग्रह इतना बड़ा होता है कि यह स्मृति में फिट नहीं होता है, तो समाधान एक बी-पेड़ (दिलचस्प तथ्य है: "बी" वास्तव में क्या खड़ा है) पर कोई सहमति नहीं है। एक बी-पेड़ में एक नोड में कई बच्चे होते हैं और बच्चों के नोड के लिए कई पॉइंटर्स होते हैं। इस तरह, एक डिस्क पढ़ने के दौरान (जो एक डिस्क डिस्क को पढ़ने के लिए लगभग 10 एमएस ले सकता है), प्रासंगिक नोड डेटा की अधिकतम मात्रा लौटा दी जाती है, साथ ही पॉइंटर्स "पत्ती नोड" डिस्क ब्लॉक पर भी लौटा दी जाती है। यह लॉग (एन) समय में डेटा को पुनर्प्राप्त करने के लिए डेटा का पुनर्प्राप्ति समय देता है, जिससे बी-पेड़ विशेष रूप से डेटाबेस और बड़े डेटासेट पुनर्प्राप्ति कार्यान्वयन के लिए उपयोगी होता है।

Answer 5

बी-पेड़ ऊपर वर्णित सभी विचारों का उपयोग करता है। विशेष रूप से, एक बी पेड़:

1)keeps keys in sorted order for sequential traversing 
2)uses a hierarchical index to minimize the number of disk reads 
3)uses partially full blocks to speed insertions and deletions 
4)keeps the index balanced with an elegant recursive algorithm 

इसके अलावा, एक बी पेड़ बेकार सुनिश्चित करते हुए कम से कम आंतरिक नोड्स कम से कम आधे भरे हुए हैं। एक बी-पेड़ सम्मिलित होने और हटाने के मनमाना संख्या को संभाल सकता है।

Answer 6

एक एवीएल पेड़ एक स्व संतुलन बाइनरी पेड़ है जो ओ (एलजीएन) औसत और खोज सम्मिलित करने और संचालन हटाने के लिए सबसे खराब मामला सक्षम करता है। इसका उपयोग स्मृति समर्थित खोज पेड़ों (मध्यम आकार के डेटासेट) में किया जाता है।

ए बी-ट्री मुख्य रूप से भंडारण समर्थित खोज पेड़ के रूप में बहुत बड़े डेटासेट के लिए उपयोग किया जाता है क्योंकि इसे डिस्क पर कम पढ़ने की आवश्यकता होती है (क्योंकि प्रत्येक नोड में एन कुंजी होती है जहां एन> 1)। एक बी-ट्री को एक (एन, एन + 1) बी-ट्री कहा जाता है जहां एन प्रति नोड की चाबियों की संख्या है और एन + 1 प्रति नोड बच्चों की संख्या है। प्रति नोड जितनी अधिक कुंजी आपको डिस्क से पढ़ने की आवश्यकता होगी और यह स्वाभाविक रूप से एक उथले पेड़ (कम स्तर) भी होगा।

Answer 7

आम आदमी शब्दों में -

AVL पेड़ और द्विआधारी खोज वृक्ष हैं दोनों एक ही लेकिन AVL पेड़ की कोई समस्या है कि बाएं उप पेड़ और सही उप पेड़ की ऊंचाई के बीच अंतर या तो 0, 1 या होना चाहिए -1 ।

यदि कोई बाइनरी खोज पेड़ इन शर्तों को पूरा करता है तो इसे एवीएल पेड़ कहा जाएगा।

बाइनरी खोज पेड़ + हेइट कंडीशन एक एवीएल पेड़ है।

देखें: एल्गोरिथम का परिचय Cormen https://books.google.co.in/books द्वारा ...

Answer 8

अन्य answerers पहले से ही दोनों AVL और बी-ट्री के बारे में काफी गहराई तकनीकी जानकारी प्रदान की है, लेकिन मैं इन के बारे में एक अपेक्षाकृत नौसिखिया जानकारी जोड़ना चाहते हैं दो :) -

• AVL पेड़ एक द्विआधारी पेड़ है, जबकि बी पेड़ एक मल्टी-वे पेड़ (एन-ary पेड़) यानी AVL पेड़ में किसी भी नोड अधिकतम दो बच्चे नोड्स पर हो सकता है और जानकारी/डेटा का एक टुकड़ा जबकिबी-पेड़ में कोई भी नोड एन नोड्स और जानकारी/डेटा का एन -1 टुकड़ा हो सकता है। बी-पेड़ के लिए, एन को इसके आदेश के रूप में भी जाना जाता है।

Answer 9

वे वास्तव में बहुत अलग हैं, हालांकि वे काफी हद तक एक ही उद्देश्य प्रदान करते हैं: एक सहयोगी तालिका का समर्थन करते हैं। ऐतिहासिक रूप से, एवीएल पेड़ को इन-मेमोरी ऑपरेशंस के लिए बी-पेड़ से बेहतर प्रदर्शन करने के लिए लिया गया था, लेकिन सीपीयू चक्रों की तुलना में मेमोरी एक्सेस करने पर यह विशेष रूप से सच था।

हालांकि आम तौर पर चर लंबाई चाबी के लिए डेटाबेस की दुकान में इस्तेमाल किया, बी पेड़ निश्चित लंबाई और कम रिकॉर्ड (कुंजी + डेटा) के लिए सबसे अच्छा प्रदर्शन करते हैं। इस तरह के प्रयोगों के लिए, कि काफी AVL पेड़ में स्मृति का उपयोग करता है के लिए, मात हो सकता है दोनों स्मृति पदचिह्न के मामले में (के रूप में वे डेटा अधिक दृढ़तापूर्वक की दुकान) और गति (वे बहुत बेहतर कैश इलाके होगा)।

L2 बी पेड़ बहुत तेजी से साहचर्य टेबल और दृश्यों को लागू करने के लिए एक डाटा संरचनाओं पुस्तकालय है। इसमें एवीएल पेड़ भी हैं, और दो के प्रदर्शन के बीच तुलना करना आसान है।