Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> प्रोग्रामिंग

डेटा संरचना में B+ ट्री इंसर्शन


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

B+ ट्री का उदाहरण -

डेटा संरचना में B+ ट्री इंसर्शन

एक तत्व सम्मिलित करने के लिए, विचार बी-ट्री के समान है, यदि एक तत्व डाला जाता है, तो वह लीफ नोड पर संग्रहीत किया जाएगा। अगर वह किसी आंतरिक नोड में मौजूद है, तो वह पत्ते पर अपने आप में सही बच्चे के रूप में भी होगा।

मान लीजिए हम पेड़ में 65 डालना चाहते हैं। तो वह 60 से अधिक है, और 75 से कम है। फिर इसे मध्य उप-वृक्ष में डाला जाएगा। अब, 65, 63 के बाद नोड में डाला जाएगा, फिर उस नोड को दो भागों में विभाजित किया जाएगा, 65 ऊपर जाएगा, और 65 इसके दाहिने नोड पर भी होगा।

B+ ट्री 65 डालने के बाद।

डेटा संरचना में B+ ट्री इंसर्शन

एल्गोरिदम

BPlusTreeInsert(root, key) -

इनपुट -पेड़ की जड़, और डालने की कुंजी

We will assume, that the key is not present into the list
Start from root node, perform exact match for key as ‘key’ till a leaf node. Let the search path
be x1, x2, … , xh. The x1 is first node so root, then xh is leaf node. Each node xi is parent of xi+1
Insert the new object where key is ‘key’, and value is v into xh.
i := h
while xi overflows, do
   divide xi into two nodes, by moving the larger half of the keys into a new node p.
   if xi is leaf node, link p into the linked list among leaf nodes.
   identify a key k, to be inserted into the parent level along with child pointer pointing p.
   The choice of k depends on the type of the node xi. If xi is leaf node, we will perform
   copy up. So smallest key in p, is copied as k to the parent level. On the other hand, if xi is
   non-leaf node, then we will perform push up. So smallest key in p, will be copied into k,
   in the parent node.
   if i = 0, then
      create a new index node as the new root. In the new root store node with key k,
      and two child xi and p.
      return
   else
      insert a key k and a child pointer pointing to p, into node xi-1.
      i := i – 1
   end if
done

  1. डेटा संरचना में अंतराल ढेर

    यहां हम देखेंगे कि अंतराल ढेर क्या है। अंतराल ढेर पूर्ण बाइनरी ट्री हैं, जिसमें, संभवतः अंतिम को छोड़कर प्रत्येक नोड में दो तत्व होते हैं। बता दें कि नोड P में दो तत्वों की प्राथमिकताएं a और b हैं। यहाँ हम a b पर विचार कर रहे हैं। हम कहते हैं कि नोड पी बंद अंतराल [ए, बी] का प्रतिनिधित्व करता है। यहा

  1. डेटा संरचना में बाइनरी ट्री एडीटी

    मूल अवधारणा एक बाइनरी ट्री को एक ऐसे पेड़ के रूप में परिभाषित किया जाता है जिसमें किसी भी नोड में दो से अधिक बच्चे नहीं हो सकते। किसी भी नोड की उच्चतम डिग्री दो होती है। यह इंगित करता है कि बाइनरी ट्री की डिग्री या तो शून्य या एक या दो होती है। उपरोक्त अंजीर में, बाइनरी ट्री में एक जड़ और दो उप

  1. डेटा संरचना में वर्चुअल ट्री में स्प्ले

    आभासी पेड़ में, कुछ किनारों को ठोस माना जाता है और कुछ को धराशायी माना जाता है। सामान्य खेल केवल ठोस वृक्षों में ही किया जाता है। वर्चुअल ट्री में नोड y पर splay करने के लिए, निम्न विधि लागू की जाती है। एल्गोरिथ्म पेड़ को तीन बार देखता है, प्रत्येक पास में एक बार, और उसे बदल देता है। पहले पास में,