यहां हम देखेंगे कि बी-ट्री से नोड को कैसे हटाया जाए। मान लीजिए कि हमारे पास नीचे की तरह एक बीट्री है -
बी-ट्री का उदाहरण -
विलोपन के दो भाग होते हैं। सबसे पहले हमें तत्व को खोजना होगा। वह रणनीति पूछताछ की तरह है। अब डिलीट करने के लिए हमें कुछ नियमों का ध्यान रखना होगा। एक नोड में कम से कम m/2 तत्व होने चाहिए। इसलिए यदि हम एक तत्व को हटाते हैं, और इसमें m-1 से कम तत्व शेष हैं, तो यह स्वयं को समायोजित कर लेगा। यदि पूरा नोड हटा दिया जाता है, तो उसके बच्चे मर्ज हो जाएंगे, और यदि उनका आकार m के समान है, तो उन्हें दो भागों में विभाजित करें, और फिर से माध्य मान बढ़ जाएगा।
मान लीजिए हम 46 हटाना चाहते हैं। अब दो बच्चे हैं। [45], और [47, 49], फिर उनका विलय हो जाएगा, यह [45, 47, 49] होगा, अब 47 ऊपर जाएगा।
एल्गोरिदम
BTreeDelete(x, key) −
इनपुट -पेड़ की जड़, और हटाने की कुंजी
हम मान लेंगे, कि कुंजी सूची में मौजूद है
if x is leaf, then delete object with key ‘key’ from x else if x does not contain the object with key ‘key’, then locate the child x->child[i] whose key range is holding ‘key’ y := x->child[i] if y has m/2 elements, then If the sibling node z immediate to the left or right of y, has at least one more object than m/2, add one more object by moving x->key[i] from x to y, and move that last or first object from z to x. If y is non-leaf node, then last or first child pointer in z is also moved to y else any immediate sibling of y has m/2 elements, merge y with immediate sibling end if BTreeDelete(y, key) else if y that precedes ‘key’ in x, has at-least m/2 + 1 objects, then find predecessor k of ‘key’, in the sub-tree rooted by y. then recursively delete k from the sub-tree and replace key with k in x else if ys has m/2 elements, then check the child z, which is immediately follows ‘key’ in x if z has at least m/2+1 elements, then find successor k of ‘key’, in the sub-tree rooted by z. recursively delete k from sub-tree, and replace key with k in x else both y and z has m/2 elements, then merge then into one node, and push ‘key’ down to the new node as well. Recursively delete ‘key’ from this new node end if end if