ডেটা স্ট্রাকচরে B-ট্রি ইন্সারশন

এখানে আমরা দেখব, B-ট্রিতে ইন্সারশন কিভাবে করা যায়। ধরি আমাদের নিচের মতো একটি B-ট্রি আছে −

B-ট্রির উদাহরণ −

একটি উপাদান ইন্সার্ট করার ধারণা BST-এর সাথে খুব মিলতুল্য, কিন্তু আমাদের কিছু নিয়ম মেনে চলতে হবে। প্রতিটি নোডের m চাইল্ড এবং m-1 উপাদান থাকে। যদি আমরা একটি নোডে উপাদান ইন্সার্ট করি, তবে দুটি পরিস্থিতি হয়। যদি নোডে উপাদান m-1-এর চেয়ে কম থাকে, তবে নতুন উপাদানটি সরাসরি নোডে ইন্সার্ট হবে। যদি m-1 উপাদান থাকে, তবে সকল উপাদান এবং ইন্সার্ট করানো উপাদান নিয়ে মেডিয়ান বের করুন, এবং মেডিয়ান মান সেটি নোডের রুটে পাঠিয়ে দিন একই কেরিয়েটরি অনুসরণ করে, তারপর নোডের বাম ও ডান আধার থেকে দুটি আলাদা লিস্ট তৈরি করুন।

ধরি আমরা ট্রিতে 79 ইন্সার্ট করতে চাই। প্রথমে রুটের সাথে চেক হবে, এটি 56-র চেয়ে বড়। তাহলে এটি ডানমোস্ট সাব-ট্রিতে যাবে। এখন এটি 81-র চেয়ে ছোট, তাই বাম সাব-ট্রিতে যাবে। তারপর এটি রুটে ইন্সার্ট হবে। এখন তিনটি উপাদান [66, 78, 79] আছে। মেডিয়ান মান 78, তাই 78 উপরে যাবে, এবং রুট নোড হবে [79, 81], এবং নোডের উপাদানগুলো দুটি নোডে ভাগ হবে। একটি 66 ধারণ করবে, এবং অন্যটি 79 ধারণ করবে।

79 ইন্সার্ট করার পর B-ট্রি।

অ্যালগরিদম

BTreeInsert(root, key)−

ইনপুট − ট্রির রুট, এবং ইন্সার্ট করার কী আমরা অনুমান করব, কীটি লিস্টে উপস্থিত নেই

x := Read root
if x is full, then
  y := new node
  z := new node
  Locate the middle object oi, stored in x, move the objects to the left of oi in to node y
  Move the object to the right of oi into node z.
  If x is an index node, then move the child pointers accordingly
  x->child[1] := address of y
  x->child[2] := address of z
end if