अनुशंसित, 2020

संपादक की पसंद

बी-ट्री और बाइनरी ट्री के बीच अंतर

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

बी-ट्री और बाइनरी ट्री के बीच एक और अंतर यह है कि बी-ट्री के सभी बाल नोड्स एक ही स्तर पर होने चाहिए, जबकि बाइनरी ट्री में ऐसी बाधा नहीं होती है। एक बाइनरी ट्री में अधिकतम 2 उपप्रकार या नोड्स हो सकते हैं, जबकि B- वृक्ष में M कोई भी उप-वृक्ष या नोड नहीं हो सकते हैं जहाँ M, B- वृक्ष का क्रम है।

तुलना चार्ट

तुलना के लिए आधार
बी-वृक्ष
बाइनरी ट्री
आवश्यक बाधाएक नोड में अधिकतम एम संख्या बच्चे के नोड्स (जहां एम ट्री का क्रम होता है) हो सकता है।एक नोड में अधिकतम 2 संख्या में उपप्रकार हो सकते हैं।
उपयोग किया गया
इसका उपयोग तब किया जाता है जब डेटा डिस्क पर संग्रहीत होता है।इसका उपयोग तब किया जाता है जब रिकॉर्ड और डेटा रैम में संग्रहीत होते हैं।
पेड़ की ऊँचाईलॉग M एन (जहां एम एम-वे ट्री का क्रम है)लॉग 2 एन
आवेदनकई DBMS में कोड इंडेक्सिंग डेटा संरचना।कोड अनुकूलन, हफ़मैन कोडिंग, आदि।

बी-ट्री की परिभाषा

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

कुछ शर्तें हैं जो बी-ट्री के लिए सही होनी चाहिए:

  • पेड़ की ऊंचाई यथासंभव कम से कम झूठ बोलना चाहिए।
  • पेड़ की पत्तियों के ऊपर, कोई खाली उपप्रकार नहीं होना चाहिए।
  • पेड़ की पत्तियों को समान स्तर पर आना चाहिए।
  • सभी नोड्स में छुट्टी नोड्स को छोड़कर कम से कम बच्चों की संख्या होनी चाहिए।

आदेश एम के बी-पेड़ के गुण

  • प्रत्येक नोड में अधिकतम बच्चों की संख्या और न्यूनतम एम / 2 बच्चों की संख्या या 2 से अधिकतम तक की संख्या हो सकती है।
  • प्रत्येक नोड में अधिकतम M-1 कुंजी वाले बच्चों की तुलना में एक कुंजी कम है।
  • कुंजियों की व्यवस्था नोड्स के भीतर कुछ विशिष्ट क्रम में है। कुंजी के बाईं ओर मौजूद सबट्री में सभी कुंजियाँ कुंजी के पूर्ववर्ती हैं, और कुंजी के दाईं ओर मौजूद उत्तराधिकारियों को कहा जाता है।
  • एक पूर्ण नोड के सम्मिलन के समय, पेड़ दो भागों में विभाजित होता है, और माध्य मान के साथ कुंजी मूल नोड पर डाली जाती है।
  • जब नोड्स हटाए जाते हैं, तो विलय संचालन होता है।

बाइनरी ट्री की परिभाषा

एक बाइनरी ट्री एक ट्री संरचना है जो अपने बच्चे के नोड्स के लिए अधिकतम दो बिंदुओं पर हो सकती है। इसका मतलब है कि उच्चतम डिग्री का नोड 2 हो सकता है और शून्य या एक-डिग्री नोड भी हो सकता है।

एक बाइनरी ट्री के कुछ वेरिएंट होते हैं जैसे कि सख्ती से बाइनरी ट्री, बाइनरी ट्री, एक्सटेंडेड बाइनरी ट्री, आदि।

  • कड़ाई से द्विआधारी वृक्ष एक ऐसा पेड़ है जहां प्रत्येक गैर-टर्मिनल नोड में उपप्रकार और सही उपप्रकार होना चाहिए।
  • एक पेड़ को पूर्ण बाइनरी ट्री कहा जाता है जब यह प्रत्येक स्तर पर 2 i नोड्स होने की स्थिति को संतुष्ट करता है जहां मैं स्तर है।
  • थ्रेडेड बाइनरी एक द्विआधारी पेड़ है जिसमें 0 या तो नोड्स या 2 नंबर नोड्स होते हैं।

ट्रैवर्सल तकनीक

ट्री ट्रैवर्सल पेड़ डेटा संरचना पर किए गए सबसे लगातार ऑपरेशन में से एक है जिसमें प्रत्येक नोड एक बार व्यवस्थित तरीके से देखा गया।

  • इनवर्टर- इस ट्री ट्रैवर्सल में लेफ्ट सबट्री को रीसर्चली विजिट किया जाता है, फिर रूट नोड का दौरा किया जाता है और अंतिम राइट सबट्री में विजिट किया जाता है।
  • प्रीपर- इस ट्री ट्रैवर्सल में रूट नोड को पहले बाईं ओर और फिर अंतिम राइट सबट्री पर देखा जाता है।
  • पोस्टऑर्डर- यह तकनीक बाएं सबट्री तो राइट सबट्री और आखिरी रूट नोड पर जाती है।

बी-ट्री और बाइनरी ट्री के बीच महत्वपूर्ण अंतर

  1. बी-ट्री में, बच्चे की अधिकतम संख्या एक गैर-टर्मिनल नोड हो सकती है, वह एम है जहां एम बी-ट्री का क्रम है। दूसरी ओर, एक बाइनरी ट्री में अधिकतम दो उपप्रकार या बाल नोड हो सकते हैं।
  2. बी-ट्री का उपयोग तब किया जाता है जब डेटा को डिस्क में संग्रहित किया जाता है जबकि बाइनरी ट्री का उपयोग तब किया जाता है जब डेटा को रैम जैसी तेज मेमोरी में संग्रहीत किया जाता है।
  3. बी-ट्री के लिए आवेदन का एक अन्य क्षेत्र DBMS में कोड इंडेक्सिंग डेटा संरचना है, इसके विपरीत, बाइनरी ट्री को कोड ऑप्टिमाइज़ेशन, हफ़मैन कोडिंग, आदि में नियोजित किया जाता है।
  4. बी-ट्री की अधिकतम ऊंचाई लॉग एम एन (एम पेड़ का क्रम है) है। जैसा कि के खिलाफ, बाइनरी ट्री अधिकतम ऊंचाई लॉग 2 एन (एन नोड की संख्या है और आधार 2 है क्योंकि यह बाइनरी के लिए है)।

निष्कर्ष

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

Top