এখানে আমরা দেখব, কীভাবে বি-ট্রি থেকে একটি নোড মুছে ফেলা যায়। ধরুন আমাদের নিচের মত একটি BTree আছে −
বি-ট্রির উদাহরণ −
মুছে ফেলার দুটি অংশ আছে। প্রথমে আমাদের উপাদানটি খুঁজে বের করতে হবে। সেই কৌশলটি প্রশ্ন করার মতো। এখন মুছে ফেলার জন্য, আমাদের কিছু নিয়মের যত্ন নিতে হবে। একটি নোডে কমপক্ষে 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
