बी-ट्री डेटा संरचना

सभी को नमस्कार! हमने पाठ्यक्रम "डेवलपर्स के लिए एल्गोरिदम" के लिए एक नया सेट लॉन्च किया और आज हम इस पाठ्यक्रम के छात्रों के लिए तैयार एक दिलचस्प अनुवाद साझा करना चाहते हैं।



खोज पेड़ों में, जैसे कि बाइनरी सर्च ट्री, एवीएल ट्री, रेड-ब्लैक ट्री, आदि। प्रत्येक नोड में केवल एक मान (कुंजी) और अधिकतम दो वंशज होते हैं। हालांकि, एक विशेष प्रकार का खोज वृक्ष है जिसे बी-ट्री (उच्चारण बी-ट्री) कहा जाता है। इसमें, नोड में एक से अधिक मूल्य (कुंजी) और दो से अधिक वंशज होते हैं। B- ट्री को 1972 में Bayer और McCraith द्वारा विकसित किया गया था और इसे Height Balanced m-way Search Tree कहा जाता था। इसका आधुनिक नाम बी-ट्री बाद में प्राप्त हुआ।

बी-ट्री को निम्नानुसार परिभाषित किया जा सकता है:
बी-ट्री एक संतुलित खोज ट्री है जिसमें प्रत्येक नोड में कई कुंजियाँ होती हैं और दो से अधिक बच्चे होते हैं।

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

ऑर्डर बी के एक बी-पेड़ में निम्नलिखित गुण हैं:

संपत्ति 1: सभी पत्तियों की गहराई समान है।
प्रॉपर्टी 2: रूट को छोड़कर सभी नोड्स में कम से कम (m / 2) - 1 कीज़ और अधिकतम m-1 कीज़ होनी चाहिए।
संपत्ति 3: पत्तियों के बिना सभी नोड्स, रूट (यानी, सभी आंतरिक नोड्स) को छोड़कर, न्यूनतम / 2 वंशज होना चाहिए।
गुण 4: यदि जड़ एक पत्ती रहित नोड है, तो इसके कम से कम 2 वंशज होने चाहिए।
संपत्ति 5: n-1 कुंजी के साथ पत्तियों के बिना एक नोड में n बच्चे होने चाहिए।
गुण 6: नोड की सभी कुंजियों को उनके मूल्यों के आरोही क्रम में व्यवस्थित किया जाना चाहिए।

उदाहरण के लिए, 4-क्रम वाले बी-ट्री में अधिकतम 3 मुख्य मान और प्रत्येक नोड के लिए अधिकतम 4 बच्चे होते हैं।


बी-ट्री 4 ऑर्डर

बी-ट्री ऑपरेशन

निम्नलिखित ऑपरेशन बी-ट्री पर किए जा सकते हैं:

1. खोज
2. डालने
3. निष्कासन

बी पेड़ की खोज करें

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

चरण 1: खोज करने के लिए आइटम पढ़ें।
चरण 2: खोजे गए आइटम की तुलना पेड़ के रूट नोड में पहले मुख्य मूल्य के साथ करें।
चरण 3: यदि वे मेल खाते हैं, तो प्रिंट करें: "नोड मिला!" और खोज को पूरा करें।
चरण 4: यदि वे मेल नहीं खाते हैं, तो आइटम का मूल्य वर्तमान कुंजी मूल्य से अधिक या कम है।
चरण 5: यदि आप जिस आइटम की तलाश कर रहे हैं वह छोटा है, तो बाईं सबट्री को खोजना जारी रखें।
चरण 6: यदि वांछित आइटम बड़ा है, तो नोड में अगले प्रमुख मूल्य के साथ आइटम की तुलना करें और चरण 3, 4, 5 और 6 को दोहराएं जब तक कि एक मिलान नहीं मिलता है या जब तक कि खोज की गई वस्तु की पत्ती नोड में अंतिम कुंजी मूल्य के साथ तुलना नहीं की जाती है।
चरण 7: यदि सूची नोड में अंतिम कुंजी मान खोज से मेल नहीं खाता, तो "आइटम नहीं मिला!" और खोज को पूरा करें।

बी-ट्री सम्मिलित ऑपरेशन

बी-ट्री में, एक नया आइटम केवल एक पत्ती नोड में जोड़ा जा सकता है। इसका मतलब यह है कि एक नया कुंजी-मूल्य युग्म हमेशा केवल लीफ नोड में जोड़ा जाता है। सम्मिलित इस प्रकार है:

चरण 1: जाँच करें कि क्या पेड़ खाली है।
चरण 2: अगर पेड़ खाली है, तो एक नया कुंजी मूल्य के साथ एक नया नोड बनाएं और इसे रूट नोड के रूप में लें।
चरण 3: यदि पेड़ खाली नहीं है, तो एक उपयुक्त पत्ती नोड ढूंढें जिसमें बाइनरी सर्च ट्री के तर्क का उपयोग करके एक नया मान जोड़ा जाएगा।
चरण 4: यदि वर्तमान लीफ नोड में एक खाली सेल है, तो नोड के अंदर प्रमुख मूल्यों के बढ़ते क्रम का पालन करते हुए, वर्तमान लीफ नोड में एक नया कुंजी-मान जोड़ें।
चरण 5: यदि वर्तमान नोड पूर्ण है और इसमें मुक्त कोशिकाएं नहीं हैं, तो मूल नोड को मूल मान भेजकर पत्ती नोड को विभाजित करें। जब तक भेजा जाने वाला मूल्य नोड के लिए प्रतिबद्ध है, तब तक चरण को दोहराएं।
चरण 6: यदि पेड़ की जड़ के साथ अलगाव होता है, तो औसत पेड़ की नई जड़ बन जाता है और पेड़ की ऊंचाई एक के बाद बढ़ जाती है।

एक उदाहरण:

आइए इसमें 1 से 10 तक संख्या जोड़कर आदेश 3 का बी-ट्री बनाएं।

डालें (1):
चूंकि "1" पेड़ का पहला तत्व है, इसे एक नए नोड में डाला जाता है और यह नोड पेड़ की जड़ बन जाता है।



डालें (2):
तत्व 2 को मौजूदा लीफ नोड में जोड़ा जाता है। अब हमारे पास केवल एक नोड है, इसलिए यह एक ही समय में जड़ और पत्ती दोनों है। इस शीट में एक खाली सेल है। फिर "2" इस खाली सेल में जाता है।



डालें (3):
तत्व 3 को मौजूदा लीफ नोड में जोड़ा जाता है। अब हमारे पास केवल एक नोड है, जो जड़ और पत्ती दोनों है। इस शीट में एक खाली सेल नहीं है। इसलिए, हम मूल नोड को औसत मान (2) भेजकर इस नोड को अलग करते हैं। हालाँकि, वर्तमान नोड में मूल नोड नहीं है। इसलिए, औसत मूल्य पेड़ का मूल नोड बन जाता है।



डालें (4):
तत्व "4" मान "2" के साथ रूट नोड से बड़ा है, जबकि रूट नोड एक पत्ती नहीं है। इसलिए, हम "2" के सही उपशीर्षक के साथ आगे बढ़ते हैं। हम "3" मान के साथ लीफ नोड में आते हैं, जिसमें एक खाली सेल होता है। इस प्रकार, हम इस खाली सेल में "4" तत्व सम्मिलित कर सकते हैं।



डालें (5):
तत्व "5" मान "2" के साथ रूट नोड से बड़ा है, जबकि रूट नोड एक पत्ती नहीं है। इसलिए, हम "2" के सही उपशीर्षक के साथ आगे बढ़ते हैं। हम लीफ नोड में आते हैं और पाते हैं कि यह पहले से ही भरा हुआ है और इसमें खाली कोशिकाएँ नहीं हैं। फिर हम मूल नोड (2) को औसत मान (4) भेजकर इस नोड को विभाजित करते हैं। मूल नोड में इसके लिए एक खाली सेल है, इसलिए "4" मान को नोड में जोड़ा जाता है जिसमें पहले से ही "2" का मान होता है, और एक नया तत्व "5" एक नई शीट के रूप में जोड़ा जाता है।



डालें (6):
तत्व "6" जड़ "2" और "4" के तत्वों से बड़ा है, जो एक पत्ती नहीं है। हम तत्व "4" के सही उपशीर्षक के साथ आगे बढ़ते हैं। हम "5" के मूल्य के साथ एक शीट तक पहुंचते हैं, जिसमें एक खाली सेल होता है, इसलिए "6" तत्व को इसमें रखा गया है।



डालें (7):
तत्व "7" जड़ "2" और "4" के तत्वों से बड़ा है, जो एक पत्ती नहीं है। हम तत्व "4" के सही उपशीर्षक के साथ आगे बढ़ते हैं। हम पत्ती नोड तक पहुंचते हैं और देखते हैं कि यह भरा हुआ है। हम मूल नोड "2" और "4" के तत्वों के साथ "6" का औसत मान भेजकर इस नोड को विभाजित करते हैं। हालाँकि, मूल नोड भी पूर्ण है, इसलिए हम नोड को "2" और "4" तत्वों के साथ विभाजित करते हैं, और मूल नोड में "4" मान भेजते हैं। केवल यह नोड अभी तक नहीं है। इस स्थिति में, तत्व "4" के साथ नोड पेड़ की नई जड़ बन जाता है।



डालें (8):
तत्व 8 4 के मान के साथ रूट नोड से बड़ा है, और रूट नोड एक पत्ती नहीं है। हम तत्व "4" से सही सबट्री के साथ आगे बढ़ते हैं और "6" मान के साथ नोड पर आते हैं। "8" "6" से अधिक है और तत्व "6" के साथ नोड एक शीट नहीं है, इसलिए हम "6" के सही उपप्रकार के साथ आगे बढ़ते हैं। हम "7" के साथ लीफ नोड तक पहुंचते हैं, जिसमें एक खाली सेल होता है, इसलिए हम इसमें "8" डालते हैं।



डालें (9):
तत्व 9 4 के मान के साथ रूट नोड से बड़ा है, और रूट नोड एक पत्ती नहीं है। हम तत्व "4" से सही सबट्री के साथ आगे बढ़ते हैं और "6" मान के साथ नोड पर आते हैं। "9" "6" से अधिक है और तत्व "6" के साथ नोड एक शीट नहीं है, इसलिए हम "6" के सही उपप्रकार के साथ आगे बढ़ते हैं। हम "7" और "8" मूल्यों के साथ लीफ नोड तक पहुंचते हैं। वह भरा हुआ है। हम मूल नोड को औसत मान (8) भेजकर इस नोड को विभाजित करते हैं। मूल नोड "6" में एक खाली कक्ष होता है, इसलिए हम इसमें "8" डालते हैं। इस स्थिति में, नोड सूची में एक नया तत्व "9" जोड़ा जाता है।



डालें (10):
तत्व "10" मान "4" के साथ रूट नोड से बड़ा है, जबकि रूट नोड एक पत्ती नहीं है। हम तत्व "4" से सही सबट्री के साथ आगे बढ़ते हैं और "6" और "8" मान के साथ नोड पर आते हैं। "10" "6" और "8" से अधिक है और इन तत्वों के साथ नोड एक शीट नहीं है, इसलिए हम "8" के सही उपशीर्षक के साथ आगे बढ़ते हैं। हम "9" के मूल्य के साथ पत्ती नोड तक पहुंचते हैं। उसके पास एक खाली सेल है, इसलिए हमने वहां "10" रखा।



हम सुझाव देते हैं कि आप स्वतंत्र रूप से अभ्यास में समझते हैं कि इस दृश्य का उपयोग करके बी-पेड़ों की व्यवस्था कैसे की जाती है।

हम सभी को एक नि: शुल्क खुले सबक की प्रतीक्षा है, जो 12 जुलाई को आयोजित किया जाएगा। जल्द मिलते हैं!