डेटा संरचना में बी-पेड़ सम्मिलन

यहां हम देखेंगे कि बी-ट्री में इंसर्शन कैसे किया जाता है। मान लीजिए हमारे पास नीचे जैसा बी-ट्री है -

बी-ट्री का उदाहरण -

तत्व डालने के लिए, विचार बीएसटी के समान है, लेकिन हमें कुछ नियमों का पालन करना होगा। प्रत्येक नोड में m बच्चे और m-1 तत्व होते हैं। यदि हम एक नोड में एक तत्व सम्मिलित करते हैं, तो दो स्थितियाँ होती हैं। यदि नोड में m-1 से कम तत्व हैं, तो नया तत्व सीधे नोड में डाला जाएगा। यदि इसमें m-1 तत्व हैं, तो सभी तत्वों को लेकर, और जो तत्व डाला जाएगा, उनमें से माध्यिका लें, और माध्य मान उसी मानदंड को निष्पादित करके उस नोड के मूल में भेज दिया जाता है, फिर दो बनाएं नोड के बाएं आधे और दाएं आधे हिस्से से अलग सूचियां

मान लीजिए हम पेड़ में 79 डालना चाहते हैं। सबसे पहले इसकी जड़ से जांच की जाएगी, यह 56 से अधिक है। फिर यह सबसे दाहिने उप-वृक्ष पर आ जाएगा। अब यह 81 से कम है, इसलिए बाएं उप-वृक्ष पर जाएं। इसके बाद इसे रूट में डाला जाएगा। अब तीन तत्व हैं [66, 78, 79]। माध्यिका मान 78 है, इसलिए 78 ऊपर जाएगा, और रूट नोड [79, 81] बन जाएगा, और नोड के तत्वों को दो नोड्स में विभाजित किया जाएगा। एक में 66 और दूसरे के पास 79 होंगे।

बी-ट्री 79 डालने के बाद।

एल्गोरिदम

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