डेटा संरचना में बी ट्री: खोज, सम्मिलित करना, हटाना

बी ट्री क्या है?

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

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

बी-ट्री के लिए नियम

बी-ट्री बनाने के लिए यहां कुछ महत्वपूर्ण नियम दिए गए हैं:

• सभी पत्ते एक ही स्तर पर बनाए जाएंगे।
• एक बी-ट्री डिग्री की संख्या द्वारा निर्धारित होती है, जिसे "क्रम" भी कहा जाता है (एक बाहरी कर्ता, जैसे कि एक प्रोग्रामर द्वारा निर्दिष्ट), जिसे संदर्भित किया जाता है m आगे. का मूल्य m यह उस डिस्क के ब्लॉक आकार पर निर्भर करता है जिस पर डेटा मुख्य रूप से स्थित होता है।
• नोड के बाएं उपवृक्ष में उपवृक्ष के दाएं भाग की तुलना में कम मान होंगे। इसका मतलब है कि नोड्स को बाएं से दाएं बढ़ते क्रम में भी क्रमबद्ध किया जाता है।
• रूट नोड और उसके चाइल्ड नोड्स में अधिकतम कितनी कुंजियाँ हो सकती हैं, इसकी गणना इस सूत्र द्वारा की जाती है: m − 1। उदाहरण के लिए:

  m = 4
  max keys: 4 − 1 = 3

• रूट को छोड़कर प्रत्येक नोड में न्यूनतम संख्या में कुंजियाँ होनी चाहिए। [m/2] − 1। उदाहरण के लिए:

  m = 4
  min keys: 4/2 − 1 = 1

• किसी नोड में चाइल्ड नोड्स की अधिकतम संख्या उसकी डिग्री के बराबर होती है, जो कि है m.
• एक नोड की न्यूनतम संतानें ऑर्डर की आधी होती हैं, जो कि m/2 होती है (अधिकतम मान लिया जाता है)।
• एक नोड में सभी कुंजियाँ बढ़ते क्रम में व्यवस्थित होती हैं।

बी-ट्री का उपयोग क्यों करें?

बी-ट्री का उपयोग करने के कारण निम्नलिखित हैं:

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

बी ट्री का इतिहास

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

खोजें Operaउत्पादन

खोज प्रक्रिया बी ट्री पर सबसे सरल प्रक्रिया है। इसके लिए निम्नलिखित एल्गोरिदम का उपयोग किया जाता है:

• जिस कुंजी (मान) की खोज करनी है, उसे “k” मान लें।
• मूल से खोजना शुरू करें और पुनरावर्ती रूप से नीचे की ओर जाएँ।
• यदि k मूल मान से छोटा है, तो बाएँ उपवृक्ष में खोजें; यदि k मूल मान से बड़ा है, तो दाएँ उपवृक्ष में खोजें।
• यदि नोड में k पाया गया है, तो बस नोड को वापस कर दें।
• यदि नोड में k नहीं मिलता है, तो अधिक कुंजी वाले चाइल्ड तक नीचे जाएँ।
• यदि k वृक्ष में नहीं मिलता है, तो हम NULL लौटाते हैं।

सम्मिलित करें Operaउत्पादन

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

• खोज ऑपरेशन चलाएं और सम्मिलन का उपयुक्त स्थान ढूंढें।
• नई कुंजी को उचित स्थान पर डालें, लेकिन यदि नोड में पहले से ही अधिकतम संख्या में कुंजियाँ हैं:
• नोड, नई डाली गई कुंजी के साथ, मध्य तत्व से अलग हो जाएगा।
• मध्य तत्व अन्य दो संतान नोड्स के लिए पैरेंट बन जाएगा।
• नोड्स को कुंजियों को आरोही क्रम में पुनः व्यवस्थित करना होगा।

उपरोक्त उदाहरण में:

• नोड में उपयुक्त स्थान पर कुंजी की खोज करें।
• लक्ष्य नोड में कुंजी डालें और नियमों की जांच करें।
• इंसर्शन के बाद, क्या नोड में न्यूनतम 1 या उससे अधिक कुंजियाँ हैं? इस स्थिति में, हाँ, हैं। अगला नियम देखें।
• इंसर्शन के बाद, क्या नोड में अधिकतम 3 कुंजियों से अधिक कुंजियाँ हैं? इस स्थिति में, नहीं। इसका अर्थ है कि बी ट्री किसी भी नियम का उल्लंघन नहीं कर रहा है, और इंसर्शन प्रक्रिया पूरी हो गई है।

उपरोक्त उदाहरण में:

• नोड अधिकतम कुंजियों की संख्या तक पहुंच गया है।
• नोड विभाजित हो जाएगा, और मध्य कुंजी शेष दो नोड्स का मूल नोड बन जाएगी।
• यदि कुंजियों की संख्या सम हो, तो मध्य नोड का चयन बाएँ या दाएँ झुकाव के आधार पर किया जाएगा।

उपरोक्त उदाहरण में:

• इस नोड में अधिकतम कुंजियों से कम कुंजियाँ हैं।
• 1 को 3 के बगल में रखा गया है, लेकिन आरोही क्रम के नियम का उल्लंघन हुआ है।
• इस समस्या को हल करने के लिए, कुंजियों को क्रमबद्ध किया जाता है।

इसी प्रकार, 13 और 2 को नोड में आसानी से डाला जा सकता है क्योंकि वे नोड्स के लिए "अधिकतम कुंजियों से कम" नियम को पूरा करते हैं।

उपरोक्त उदाहरण में:

• नोड में अधिकतम कुंजियों के बराबर कुंजियाँ होती हैं।
• कुंजी को लक्ष्य नोड में डाला जाता है, लेकिन यह अधिकतम कुंजियों के नियम का उल्लंघन करता है।
• लक्ष्य नोड विभाजित हो गया है, तथा बायीं ओर झुकाव वाली मध्य कुंजी अब नए चाइल्ड नोड की पैरेंट है।
• नये नोड्स को आरोही क्रम में व्यवस्थित किया गया है।

इसी प्रकार, उपरोक्त नियमों और मामलों के आधार पर, शेष मानों को बी ट्री में आसानी से डाला जा सकता है।

मिटाना Operaउत्पादन

डिलीट ऑपरेशन में इंसर्ट और सर्च ऑपरेशन की तुलना में अधिक नियम होते हैं। निम्नलिखित एल्गोरिदम लागू होता है:

• खोज प्रक्रिया चलाएं और नोड्स में लक्षित कुंजी का पता लगाएं।
• लक्ष्य कुंजी के स्थान के आधार पर तीन शर्तें लागू होती हैं, जैसा कि निम्नलिखित अनुभागों में बताया गया है।

यदि लक्ष्य कुंजी लीफ नोड में है

• Target लीफ नोड में न्यूनतम कुंजियों से अधिक कुंजियाँ हैं। इसे हटाने से बी ट्री के नियम का उल्लंघन नहीं होगा।
• Target यह लीफ नोड में है, और इसमें न्यूनतम कुंजी नोड हैं। इसे हटाने से बी ट्री के गुण का उल्लंघन होगा।
• लक्ष्य नोड अपने ठीक बाएं या ठीक दाएं नोड (सहयोगी) से कुंजी उधार ले सकता है।
• भाई-बहन कहेंगे हाँ यदि इसमें न्यूनतम संख्या से अधिक कुंजियाँ हैं।
• कुंजी पैरेंट नोड से उधार ली जाएगी, अधिकतम मान पैरेंट को स्थानांतरित किया जाएगा, पैरेंट नोड का अधिकतम मान टारगेट नोड को स्थानांतरित किया जाएगा, और टारगेट का मान हटा दिया जाएगा।
• Target कुंजी लीफ नोड में है, लेकिन किसी भी सहोदर नोड में न्यूनतम संख्या से अधिक कुंजियाँ नहीं हैं: कुंजी खोजें, सहोदर नोड्स और जनक नोड्स के न्यूनतम मान के साथ विलय करें, कुल कुंजियाँ अब न्यूनतम से अधिक होंगी, और लक्षित कुंजी को जनक नोड के न्यूनतम मान से बदल दिया जाएगा।

यदि लक्ष्य कुंजी किसी आंतरिक नोड में है

• या तो क्रमानुसार पूर्ववर्ती (predigestion) या क्रमानुसार अनुवर्ती (sequence) चुनें।
• यदि पूर्ववर्ती इकाई क्रम में है, तो उसके बाएं उपवृक्ष से अधिकतम कुंजी का चयन किया जाएगा।
• यदि कोई अनुक्रमिक उत्तराधिकारी है, तो उसके दाएँ उपवृक्ष से न्यूनतम कुंजी का चयन किया जाएगा।
• यदि लक्ष्य कुंजी के क्रमानुसार पूर्ववर्ती में न्यूनतम कुंजियों से अधिक कुंजियाँ हैं, तो ही यह लक्ष्य कुंजी को क्रमानुसार पूर्ववर्ती की अधिकतम कुंजी से प्रतिस्थापित कर सकता है।
• यदि लक्ष्य कुंजी के क्रमानुसार पूर्ववर्ती कुंजी में न्यूनतम कुंजी से अधिक कुंजी नहीं हैं, तो क्रमानुसार उत्तराधिकारी कुंजी की न्यूनतम कुंजी खोजें।
• यदि लक्ष्य कुंजी के क्रम-पूर्ववर्ती और परवर्ती दोनों में न्यूनतम कुंजी से कम कुंजियाँ हैं, तो पूर्ववर्ती और परवर्ती को मर्ज करें।

यदि लक्ष्य कुंजी रूट नोड में है

• इसे क्रमानुसार पूर्ववर्ती उपवृक्ष के अधिकतम तत्व से बदलें।
• यदि विलोपन के बाद, लक्ष्य में न्यूनतम से कम कुंजियाँ हैं, तो लक्ष्य नोड अपने सहोदर से उसके जनक के माध्यम से अधिकतम मान उधार लेगा।
• लक्ष्य इकाई द्वारा जनक इकाई का अधिकतम मान लिया जाएगा, लेकिन उसमें सहोदर इकाई के अधिकतम मान वाले नोड्स भी शामिल होंगे।

अब, आइए एक उदाहरण से डिलीट ऑपरेशन को समझें।

ऊपर दिया गया आरेख बी-ट्री में डिलीट ऑपरेशन के विभिन्न मामलों को दर्शाता है। यह बी-ट्री 5वें क्रम का है, जिसका अर्थ है कि किसी भी नोड में न्यूनतम 3 चाइल्ड नोड हो सकते हैं और अधिकतम 5 चाइल्ड नोड हो सकते हैं। जबकि किसी भी नोड में न्यूनतम और अधिकतम 2 और 4 कुंजी हो सकती हैं।

उपरोक्त उदाहरण में:

• लक्ष्य नोड में हटाने के लिए लक्ष्य कुंजी मौजूद है।
• लक्ष्य नोड में न्यूनतम कुंजियों से अधिक कुंजियाँ हैं।
• बस कुंजी को हटा दें।

उपरोक्त उदाहरण में:

• लक्ष्य नोड में न्यूनतम कुंजियों के बराबर कुंजियाँ हैं, इसलिए हम इसे सीधे हटा नहीं सकते क्योंकि इससे शर्तों का उल्लंघन होगा।

अब, निम्नलिखित चित्र बताता है कि इस कुंजी को कैसे हटाया जाए:

• लक्ष्य नोड अपने निकटतम संबंधी से एक कुंजी उधार लेगा, इस मामले में, क्रम में पूर्ववर्ती (बायां संबंधी), क्योंकि इसका कोई क्रम में उत्तराधिकारी (दायां संबंधी) नहीं है।
• क्रम में मौजूद पूर्ववर्ती नोड का अधिकतम मान जनक नोड को स्थानांतरित किया जाएगा, और जनक नोड उस अधिकतम मान को लक्ष्य नोड को स्थानांतरित करेगा (नीचे दिए गए आरेख को देखें)।

निम्नलिखित उदाहरण यह दर्शाता है कि किसी कुंजी को उसके क्रमित उत्तराधिकारी से किस प्रकार हटाया जाए, जिसके लिए मान की आवश्यकता होती है।

• लक्ष्य नोड अपने निकटतम संबंधी से एक कुंजी उधार लेगा, इस मामले में, क्रम में उत्तराधिकारी (दायां संबंधी), क्योंकि इसके क्रम में पूर्ववर्ती (बायां संबंधी) के पास न्यूनतम कुंजियों के बराबर कुंजियाँ हैं।
• इन-ऑर्डर उत्तराधिकारी का न्यूनतम मान पैरेंट को हस्तांतरित कर दिया जाएगा, तथा पैरेंट अधिकतम मान लक्ष्य नोड को हस्तांतरित कर देगा।

नीचे दिए गए उदाहरण में, लक्ष्य नोड का कोई सहोदर नोड नहीं है जो लक्ष्य नोड को अपनी कुंजी दे सके। इसलिए, विलय करना आवश्यक है। ऐसी कुंजी को हटाने की प्रक्रिया देखें:

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

मिटाना Operaछद्म Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

आउटपुट: बी-ट्री से सबसे बड़ा तत्व हटा दिया जाता है।

अक्सर पूछे जाने वाले प्रश्न