Data Structure in Hindi – B Tree

B tree in data structure in hindi, B tree in hindi, B tree kya hai,

  • b tree in data structure in hindi,
    • Operations on B tree in hindi,
      • Searching operation on b tree in hindi,
      • Inserting operation on b tree in hindi,
      • Deletion operation on b tree in hindi,

b tree in data structure in hindi, Operations on B tree in hindi, Searching operation on b tree in hindi, Inserting operation on b tree in hindi, Deletion operation on b tree in hindi,

B Tree in Data Structure in Hindi

B tree एक विशेष m-way tree है जिसका उपयोग disk access के लिए व्यापक रूप से किया जा सकता है। order m के एक b-tree में अधिकांश m-1 keys और m children हो सकते हैं। B tree का उपयोग करने का एक मुख्य कारण एक ही नोड में बड़ी संख्या में keys और large key values को स्टोर करने की क्षमता है, जो tree की ऊंचाई को अपेक्षाकृत (relatively) कम रखते हैं।

Order m के एक B tree में M way tree की सभी properties होती है। इसके अलावा, इसमें निम्नलिखित properties हैं।

  1. B-tree में प्रत्येक नोड में अधिकांश m children होते हैं।
  2. B-tree में प्रत्येक नोड में root नोड और leaf नोड को छोड़कर कम से कम m/2 children होते हैं।
  3. Root नोड में कम से कम 2 node होने चाहिए।
  4. सभी leaf node समान level पर होने चाहिए।

यह आवश्यक नहीं है कि, सभी नोड्स में children की संख्या समान हो लेकिन, प्रत्येक नोड में m/2 संख्या के नोड्स होने चाहिए।

order 4 का एक B tree निम्नलिखित छवि में दिखाया गया है।

B Tree

B-tree पर कुछ ऑपरेशन करते समय, B-tree की किसी भी property का उल्लंघन हो सकता है जैसे कि एक नोड के पास न्यूनतम children की संख्या। B-tree के गुणों (properties) को बनाए रखने के लिए, tree विभाजित (split) या जुड़ (join) सकता है।

Operations on B tree in hindi

Searching operation on b tree:

B-tree में searching, binary search tree के समान है। उदाहरण के लिए, यदि हम निम्नलिखित B-tree में एक item 49 की खोज करते हैं। तो प्रक्रिया कुछ इस तरह होगी:

  1. Item 49 की तुलना root node 78 के साथ करें। जैसा की 49 <78 तो,इसके left sub-tree पर जाएं।
  2. Since, 40<49<56, traverse right sub-tree of 40.
  3. 49>45, move to right. Compare 49.
  4. match found, return.

B tree में searching, tree की height पर निर्भर करता है। search algorithm, B tree में किसी भी तत्व को खोजने के लिए O(log n) समय लेता है।

B Tree

Inserting operation on b tree

Insertion, leaf node level पर किया जाता है। B tree में एक item डालने के लिए निम्नलिखित algorithm का पालन करने की आवश्यकता है।

  1. उपयुक्त (appropriate) leaf node को खोजने के लिए B tree को पार (traverse) करें, जिस पर नोड को डाला जा सकता है।
  2. यदि leaf node में keys m-1 से कम है तो बढ़ते हुए क्रम में element डालें।
  3. और अगर leaf node में m-1 keys हैं, तो निम्न चरणों का पालन करें।
    • elements के बढ़ते क्रम में नया element डालें।
    • मध्यभाग (median) में नोड को दो नोड्स में विभाजित करें।।
    • Median element को उसके parent नोड तक push करें।
    • यदि parent नोड में भी m-1 संख्या की keys हैं, तो समान चरणों का पालन करके इसे भी विभाजित करें।

Deletion operation on b tree

Leaf nodes पर deletion भी किया जाता है। जिस नोड को हटाया जाना है वह या तो leaf node या internal नोड हो सकता है। b tree से एक नोड को हटाने के लिए निम्नलिखित algorithm का पालन किया जाना चाहिए।

  1. Leaf node का पता लगाएं।
  2. यदि leaf node में keys m/2 से अधिक हैं तो नोड से desired key हटा दें।
  3. यदि leaf node में m/2 keys नहीं हैं, तो आठ या left sibling से element लेकर keys को पूरा करें।
    • यदि left sibling में element m/2 से अधिक होते है, तो उसके सबसे बड़े element को उसके parent तक धकेलें और हस्तक्षेप करने वाले element को उस नोड तक नीचे ले जाएं जहां key को हटा दिया गया है।
    • यदि right sibling में m/2 elements से अधिक होता है, तो उसके सबसे छोटे तत्व को parent तक धकेलें और हस्तक्षेप करने वाले तत्व को उस नोड तक नीचे ले जाएं जहां key को हटा दिया गया है।
  4. यदि दोनों में से किसी में भी sibling में m/2 element नहीं हैं, तो दो leaf nodes और parent नोड के हस्तक्षेप element को जोड़कर एक नया leaf node बनाएँ।
  5. यदि parent m/2 nodes से कम के साथ रह जाते हैं, तो parent पर भी उपरोक्त प्रक्रिया लागू करें।

यदि वह नोड जिसे delete किया जाना है, एक internal नोड है, तो नोड को उसके in-order उत्तराधिकारी (successor) या पूर्ववर्ती (predecessor) के साथ बदलें। चूंकि, उत्तराधिकारी या पूर्ववर्ती हमेशा leaf node पर होगा, इसलिए प्रक्रिया समान होगी, क्योंकि नोड को leaf node से हटाया जा रहा है।

Leave a Reply

DMCA.com Protection Status