यहाँ हम देखेंगे कि B-ट्री से नोड को कैसे हटाया जाता है। मान लीजिए हमारे पास नीचे जैसा B-ट्री है:
B-ट्री का उदाहरण –
विलोपन के दो भाग हैं। सबसे पहले हमें तत्व ढूंढना होगा। वह रणनीति क्वेरी करने जैसी है। अब विलोपन के लिए, हमें कुछ नियमों का ध्यान रखना होगा। एक नोड में कम से कम m/2 तत्व होने चाहिए। इसलिए यदि हम एक तत्व हटाते हैं, और इसमें m-1 से कम तत्व शेष रहते हैं, तो यह स्वयं को समायोजित करेगा। यदि पूरा नोड हटा दिया जाता है, तो उसके बच्चों को मर्ज किया जाएगा, और यदि उनका आकार m के समान है, तो उन्हें दो भागों में विभाजित किया जाएगा, और फिर से माध्यिका मान ऊपर जाएगा।
मान लीजिए हम 46 को हटाना चाहते हैं। अब दो बच्चे हैं। [45], और [47, 49], फिर उन्हें मर्ज किया जाएगा, यह [45, 47, 49] होगा, अब 47 ऊपर जाएगा।
एल्गोरिदम
BTreeDelete(x, key) –
इनपुट – ट्री की जड़, और हटाने के लिए कुंजी
हम मान लेंगे, कि कुंजी सूची में मौजूद है
if x पत्ती है, then
x से कुंजी 'key' के साथ ऑब्जेक्ट हटाएं
else if x में कुंजी 'key' के साथ ऑब्जेक्ट नहीं है, then
चाइल्ड x->child[i] का पता लगाएं जिसकी कुंजी रेंज 'key' रखती है
y := x->child[i]
if y में m/2 तत्व हैं, then
यदि y के तत्काल बाएं या दाएं सहोदर नोड z में m/2 से कम से कम एक अधिक ऑब्जेक्ट है, तो x->key[i] को x से y में ले जाकर एक और ऑब्जेक्ट जोड़ें, और z से अंतिम या पहला ऑब्जेक्ट x में ले जाएं। यदि y गैर-पत्ती नोड है, तो z में अंतिम या पहला चाइल्ड पॉइंटर भी y में ले जाया जाता है
else
y के किसी भी तत्काल सहोदर में m/2 तत्व हैं, y को तत्काल सहोदर के साथ मर्ज करें
end if
BTreeDelete(y, key)
else
यदि x में 'key' से पहले y में कम से कम m/2 + 1 ऑब्जेक्ट हैं, then
'key' के पूर्ववर्ती k को, y द्वारा रूटेड उप-ट्री में ढूंढें। फिर k को उप-ट्री से पुनरावर्ती रूप से हटाएं और x में कुंजी को k से प्रतिस्थापित करें
else if ys में m/2 तत्व हैं, then
चाइल्ड z की जांच करें, जो x में 'key' के तुरंत बाद आता है
if z में कम से कम m/2+1 तत्व हैं, then
'key' के उत्तराधिकारी k को, z द्वारा रूटेड उप-ट्री में ढूंढें। पुनरावर्ती रूप से k को उप-ट्री से हटाएं, और x में कुंजी को k से प्रतिस्थापित करें
else
दोनों y और z में m/2 तत्व हैं, फिर उन्हें एक नोड में मर्ज करें, और 'key' को नए नोड में भी नीचे धकेलें। पुनरावर्ती रूप से इस नए नोड से 'key' को हटाएं
end if
end if
end if
