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

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

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

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

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

79 সন্নিবেশ করার পরে বি-ট্রি।

অ্যালগরিদম

BTreeInsert(root, key)−

ইনপুট৷ − গাছের মূল, এবং কী ঢোকানোর জন্য আমরা ধরে নেব, চাবিটি তালিকায় নেই

x :=পড়ুন rootif x পূর্ণ, তারপর y :=নতুন নোড z :=নতুন নোড মধ্যম অবজেক্ট oi সনাক্ত করুন, x-এ সংরক্ষিত, অবজেক্টগুলিকে oi-এর বাম দিকে নোড y-এ সরান নোড z মধ্যে oi ডান. যদি x একটি ইনডেক্স নোড হয়, তাহলে সেই অনুযায়ী চাইল্ড পয়েন্টারগুলিকে সরিয়ে দিন