B ट्री और B + ट्री डेटा संरचना C ++ में

b tree b tree data structure c

यह C ++ ट्यूटोरियल बी ट्री और बी + ट्री डेटा संरचनाओं को समझाता है। उनका उपयोग डेटा को स्टोर करने के लिए किया जाता है जब मुख्य डेटा को मुख्य मेमोरी में संग्रहीत नहीं किया जा सकता है:

बी-ट्री एक स्व-संतुलित पेड़ और साथ ही एक विशेष एम-वे ट्री है जो डिस्क एक्सेस के लिए उपयोग किया जाता है।

जब संग्रहीत किए जाने वाले डेटा की मात्रा बहुत अधिक होती है, तो हम संपूर्ण डेटा को मुख्य मेमोरी में संग्रहीत नहीं कर सकते हैं। इसलिए हम डिस्क में डेटा स्टोर करते हैं। मुख्य मेमोरी एक्सेस की तुलना में डिस्क से डेटा एक्सेस में अधिक समय लगता है।

जब डिस्क में संग्रहीत डेटा की कुंजी की संख्या बहुत अधिक होती है, तो डेटा को आमतौर पर ब्लॉक के रूप में एक्सेस किया जाता है। इन ब्लॉकों तक पहुंचने का समय पेड़ की ऊंचाई के सीधे आनुपातिक है।

=> निरपेक्ष सी ++ प्रशिक्षण श्रृंखला के लिए यहां क्लिक करें।

आप क्या सीखेंगे:

• सी ++ में बी-ट्री
  • बी-ट्री के बुनियादी संचालन
    • (१) खोज
    • # 2) सम्मिलन
    • # 3) विलोपन
  • बी पेड़ों के अनुप्रयोग
• सी + + में पेड़ +
  • बी + पेड़ के फायदे
• बी-ट्री और बी + ट्री के बीच अंतर
• निष्कर्ष
  • अनुशंसित पाठ

सी ++ में बी-ट्री

बी-ट्री एक सपाट पेड़ है यानी बी ट्री की ऊंचाई न्यूनतम रखी जाती है। इसके बजाय, बी-ट्री के प्रत्येक नोड में कई चाबियाँ डाली जाती हैं। एवीएल पेड़ों जैसे अन्य संतुलित पेड़ों की तुलना में बी-पेड़ की ऊंचाई को न्यूनतम रखने से, पहुंच तेज होती है।

एक विशिष्ट बी-पेड़ नीचे दिखाया गया है:

मैक पर अजगर के लिए सबसे अच्छा विचारधारा

आमतौर पर, बी-ट्री में नोड आकार को ब्लॉक आकार के समान रखा जाता है।

नीचे सूचीबद्ध बी-ट्री के कुछ गुण हैं।

• बी-ट्री के सभी पत्ते समान स्तर पर हैं।
• ऑर्डर मी के एक बी-ट्री में अधिकांश एम -1 कुंजी और मी बच्चे हो सकते हैं।
• बी-ट्री में प्रत्येक नोड में अधिकांश मी बच्चे हैं।
• रूट नोड में कम से कम दो नोड्स होने चाहिए।
• रूट नोड और लीफ नोड को छोड़कर प्रत्येक नोड में एम / 2 बच्चे होते हैं।

अगला, हम बी-ट्री के कुछ बुनियादी कार्यों पर चर्चा करते हैं।

बी-ट्री के बुनियादी संचालन

नीचे दिए गए हैं बी-ट्री के कुछ बुनियादी संचालन।

(१) खोज

B वृक्ष में खोज BST के समान है। उपरोक्त पेड़ में यदि हम आइटम 3 की तलाश करना चाहते हैं, तो हम निम्नानुसार आगे बढ़ेंगे:

• 3 मूल तत्वों के साथ तुलना करें। यहाँ, ३<6 and 3 <15. So we proceed to the left subtree.
• बाएं उपश्रेण में 4 के साथ 3 की तुलना करें। 3 के रूप में<4, we proceed to the left subtree of node 4.
• अगले नोड में दो कुंजी हैं, 2 और 3. 3> 2 जबकि 3 = 3। इसलिए हमें इस नोड पर कुंजी मिल गई है। पाया स्थान पर लौटें।

बी ट्री में खोज करना पेड़ की ऊंचाई पर निर्भर करता है। आमतौर पर किसी दिए गए आइटम को खोजने के लिए O (लॉग एन) समय लगता है।

# 2) सम्मिलन

बी ट्री में एक नए आइटम का सम्मिलन पत्ती नोड्स स्तर पर किया जाता है।

निम्नलिखित बी पेड़ में एक नया आइटम डालने के लिए चरणों (एल्गोरिदम) का क्रम है।

• आइटम को सम्मिलित करने के लिए पत्ती के नोड्स पर एक स्थान खोजने के लिए बी ट्री को पार करें।
• यदि पत्ती नोड में कुंजियाँ हैं
• यदि पत्ती नोड कुंजियाँ = m-1, तो
  • बढ़ती हुई वस्तुओं में एक नई वस्तु डालें।
  • नोड्स के माध्य को लें और नोड को दो नोड्स में विभाजित करें।
  • माध्यिका को उसके मूल नोड में धकेलें।
  • यदि मूल नोड कुंजी = m-1 है, तो माता-पिता नोड के लिए उपरोक्त चरणों को भी दोहराएं। यह तब तक किया जाता है जब तक हमें उपयुक्त पत्ती नोड नहीं मिल जाता है।
• अंत में, तत्व डालें।

हमने निम्नानुसार बी ट्री में सम्मिलन का प्रदर्शन किया है।

आइए हम नीचे दिखाए गए पेड़ में आइटम 70 डालें।

विंडोज़ 10 डिफ़ॉल्ट गेटवे उपलब्ध नहीं है

दिया गया पेड़ न्यूनतम डिग्री ’m’ = 3 के साथ है। इसलिए, प्रत्येक नोड में 2 * m -1 = 5 कुंजियाँ हो सकती हैं।

अब हम आइटम 70 सम्मिलित करते हैं। जैसा कि हमारे पास नोड में 5 कुंजी हो सकती हैं, हम तत्व 70 की जड़ तत्व 30 से तुलना करते हैं। 70> 30 के बाद से, हम आइटम को सही उपशीर्षक में सम्मिलित करेंगे।

सही उपशीर्षक में, हमारे पास 40, 50, 60 कीज़ के साथ एक नोड है। जैसा कि प्रत्येक नोड में 5 चाबियाँ हो सकती हैं, हम इस नोड में आइटम 70 को स्वयं सम्मिलित करेंगे।

सम्मिलन के बाद, बी-ट्री इस प्रकार दिखता है।

# 3) विलोपन

प्रविष्टि की तरह, कुंजी का विलोपन भी पत्ती के नोड स्तर पर किया जाता है। लेकिन सम्मिलन के विपरीत, विलोपन अधिक जटिल है। हटाए जाने की कुंजी या तो लीफ नोड या आंतरिक नोड हो सकती है।

एक कुंजी को हटाने के लिए, हम चरणों के नीचे दिए गए अनुक्रम (एल्गोरिथम) का पालन करते हैं।

१। लीफ नोड का पता लगाएं।

दो। नोड> m / 2 में कुंजियों की संख्या के मामले में, फिर दिए गए कुंजी को नोड से हटा दें।

३। यदि लीफ नोड में एम / 2 कीज़ नहीं हैं, तो हमें बी ट्री को बनाए रखने के लिए दाएं या बाएं सबप्रिसेस से चाबी लेकर चाबी को पूरा करना होगा।

हम इन चरणों का पालन करते हैं:

• यदि बाईं सबट्री में m / 2 तत्व होते हैं तो हम इसके सबसे बड़े तत्व को मूल नोड में धकेल देते हैं और फिर इंटरवेस्टिंग तत्व को उस स्थान पर ले जाते हैं जहां कुंजी को हटा दिया गया था।
• यदि सही सबट्री में m / 2 तत्व होते हैं तो हम इसके सबसे छोटे तत्व को मूल नोड में धकेल देते हैं और फिर इंटरवेस्टिंग तत्व को उस स्थान पर ले जाते हैं जहाँ कुंजी को हटा दिया गया था।

चार। यदि किसी नोड में m / 2 नोड नहीं है, तो उपरोक्त चरणों का प्रदर्शन नहीं किया जा सकता है, इस प्रकार हम दो पत्ती नोड्स और मूल नोड के हस्तक्षेप तत्व को जोड़कर एक नया पत्ती नोड बनाते हैं।

५। यदि कोई अभिभावक m / 2 नोड्स के बिना है, तो हम प्रश्न में मूल नोड के लिए उपरोक्त चरणों को दोहराते हैं। ये चरण तब तक दोहराए जाते हैं जब तक हमें एक संतुलित बी पेड़ नहीं मिल जाता।

नीचे दिए गए बी पेड़ से एक नोड को हटाने के लिए एक चित्रण है।

एक बार फिर निम्नलिखित बी पेड़ पर विचार करें।

मान लें कि हम B पेड़ से कुंजी 60 हटाना चाहते हैं। यदि हम बी ट्री की जांच करते हैं, तो हम पा सकते हैं कि डिलीट की जाने वाली चाबी लीफ नोड में मौजूद है। हम इस लीफ नोड से कुंजी 60 हटाते हैं।

अब पेड़ नीचे दिखाया गया है:

हम देख सकते हैं कि कुंजी ६० को हटाने के बाद, बी ट्री लीफ नोड आवश्यक गुणों को संतुष्ट करता है और हमें बी ट्री में कोई और संशोधन करने की आवश्यकता नहीं है।

कैसे जावा फ़ाइलों के साथ .jar फ़ाइलें खोलने के लिए 10

हालाँकि, अगर हमें कुंजी 20 को हटाना होता, तो केवल 10 कुंजी बाईं पत्ती के नोड में रहती। इस स्थिति में, हमें रूट 30 को लीफ नोड में स्थानांतरित करना होगा और कुंजी 40 को रूट पर ले जाना होगा।

इस प्रकार बी पेड़ से एक कुंजी को हटाते समय, देखभाल की जानी चाहिए और बी पेड़ के गुणों का उल्लंघन नहीं किया जाना चाहिए।

बी ट्री में ट्रावर्सल

बी ट्री में ट्रावर्सल भी बीएसटी में इनवर्टर ट्रैवर्सल के समान है। हम बाईं ओर से पुनरावर्ती शुरू करते हैं और फिर रूट पर आते हैं और बाएं सबट्री की ओर बढ़ते हैं।

बी पेड़ों के अनुप्रयोग

• B पेड़ों का उपयोग डेटा को विशेष रूप से बड़े डेटाबेस में अनुक्रमित करने के लिए किया जाता है क्योंकि डिस्क पर बड़े डेटाबेस में संग्रहीत डेटा तक पहुंच बहुत समय लेने वाली होती है।
• बड़े अनसोल्ड डेटा सेट में डेटा की खोज में बहुत समय लगता है लेकिन बी ट्री का उपयोग कर इंडेक्सिंग के साथ इसे बेहतर बनाया जा सकता है।

सी + + में पेड़ +

बी + ट्री बी ट्री का एक विस्तार है। बी + ट्री और बी ट्री में अंतर यह है कि बी ट्री में कीज़ और रिकॉर्ड को आंतरिक के साथ-साथ लीफ नोड्स में भी संग्रहीत किया जा सकता है जबकि बी + ट्री में रिकॉर्ड को लीफ नोड्स के रूप में संग्रहीत किया जाता है और कीज़ केवल आंतरिक नोड्स में संग्रहीत की जाती हैं।

रिकॉर्ड एक दूसरे से जुड़े हुए सूची के फैशन में जुड़े हुए हैं। यह व्यवस्था B + पेड़ों की खोजों को तेज और कुशल बनाती है। B + ट्री के आंतरिक नोड्स को इंडेक्स नोड्स कहा जाता है।

बी + पेड़ों में दो ऑर्डर होते हैं यानी एक आंतरिक नोड्स के लिए और दूसरा पत्ती या बाहरी नोड्स के लिए।

B + ट्री का एक उदाहरण नीचे दिखाया गया है।

जैसा कि बी + ट्री बी-ट्री का एक विस्तार है, बी-ट्री विषय के तहत हमने जिन बुनियादी कार्यों पर चर्चा की थी, वह अभी भी पकड़ में है।

डालने के साथ-साथ हटाते समय, हमें B + Trees के मूल गुणों को बरकरार रखना चाहिए। हालाँकि, B + ट्री में डिलीट ऑपरेशन केवल तुलनात्मक रूप से आसान है क्योंकि डेटा केवल लीफ नोड्स में संग्रहीत होता है और इसे लीफ नोड्स से हमेशा डिलीट किया जाएगा।

बी + पेड़ के फायदे

• हम डिस्क एक्सेस के बराबर संख्या में रिकॉर्ड प्राप्त कर सकते हैं।
• बी ट्री की तुलना में बी + ट्री की ऊंचाई कम है और संतुलित रहता है।
• हम इंडेक्सिंग के लिए कुंजियों का उपयोग करते हैं।
• B + ट्री में डेटा क्रमिक रूप से या सीधे प्राप्त किया जा सकता है क्योंकि लिंक लिस्ट में लीफ नोड्स व्यवस्थित हैं।
• केवल डेटा लीफ नोड्स में संग्रहीत है और एक लिंक की गई सूची के रूप में खोज तेज़ है।

बी-ट्री और बी + ट्री के बीच अंतर

निष्कर्ष

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

बी-ट्री सर्च थोड़ा धीमा है क्योंकि डेटा को आंतरिक नोड्स में संग्रहीत किया जाता है और साथ ही इसमें लीफ नोड्स भी। बी + ट्री बी-ट्री का एक विस्तार है और यहां डेटा केवल लीफ नोड्स में संग्रहीत किया जाता है। इस कारक के कारण, B + वृक्ष में खोज तेज और कुशल है।

=> संपूर्ण C ++ ट्यूटोरियल सूची के लिए यहां जाएं।

अनुशंसित पाठ

• AVL ट्री और ढेर डेटा संरचना C ++ में
• सी + + में चित्र संरचना के साथ लिंक्ड सूची डेटा संरचना
• कतार डेटा संरचना चित्रण के साथ C ++ में
• चित्रण के साथ C ++ में स्टैक डेटा संरचना
• चित्रण के साथ C ++ में परिपत्र लिंक्ड सूची डेटा संरचना
• C ++ में डेटा स्ट्रक्चर्स का परिचय
• चित्रण के साथ C ++ में प्राथमिकता कतार डेटा संरचना
• संदेह के साथ सी ++ में संदिग्ध रूप से सूचीबद्ध डेटा संरचना