B Tree in Hindi
यह एक विशेष प्रकार की tree है जिसके root मे हम एक से अधिक node रखकर उसमे से एक से अधिक branches निकाल सकते है
इस प्रकार के tree का M- Way tree भी कहा जाता है।
यहाँ एक balanced M-way tree को B tree कहते है ।
इस tree के node एक से अधिक या बहुत सारे records और children’s के pointer को रख सकते है ।
B tree को balanced sort tree भी कहा जात है यह binary tree नहीं है
B tree के गुण
- प्रत्येक node अधिक से अधिक N children’s रख सकती है व कम से कम N/2 या किसी अन्य संख्याओ के children जो 2 और n के बीच कही पर है ।
- हर node मे children node मे 1 की कम आ सकती है
- Node मे keys को परिभाषित क्रम मे व्यवस्थित किया जाता है ।
- Left sub tree की सभी keys, key की predecessor होती है ।
- Right sub tree की सभी keys , key की successor होती है ।
- जब एक पूरे भरे हुये node मे कोई key जोड़ी जाती है तो key दो node मे टूट जाती हिय और वह key जो बीच मे होगी उसे parent node मे रखा जाएगा तथा छोटी वैल्यू वाली key parent के left मे तथा बड़ी value वाली key parent के right मे रहेगी ।
- सभी leaves एक ही level पर होती है अतः V के ऊपर कोई भी खाली sub tree नहीं होगा ।
B tree मे Node जोड़ना
B tree मे किसी भी key को जोड़ने से पहले यह देखा जाता है
की key कहाँ जोड़ी जानी है यदि key पहले से निर्मित( बनी हुई) node मे जाती है
तो key को जोड़ना आसान है वह node को दो भागो(node) मे बाट देती है
वह key जिसका मान बीच मे होता है वह node मे रहता है
और इसके बाए child मे इस key के right मे स्थित समस्त keys आ जाती है
B tree मे insertion एक उदाहरण के द्वारा समझाया गया है
माना हमे निम्नलिखित keys का 4 order का tree बनाना है
44 33 30 48 50 20 22 60 55 77
सबसे पहली key 44 है हमे tree मे जोड़ना है
चूंकि यह पहली key के द्वारा ही root node का निर्माण होगा .
इसी प्रकार हम 33 और 30 को भी उनके स्थान के अनुरूप node मे जोड़ देंगे ।
चूंकि हमने यह 4 order का tree बनाया है
इसीलिए इसकी एक node मे अधिकतम 3 keys ही रख सकते है
अतः अब जो भी key इसमे जोड़ी जायेगी
वह (root) node को दो भागो मे विभक्त कर देगी । यहां हमे 48 जोड़ना है ।
उसके अब हम 50 को इसके स्थान के अनुरूप जोड़ देंगे ।
फिर से हम अब हम 20 और 22 को इसके स्थान के अनुरूप देंगे ।
अब हमे 60 को जोड़ना है जैसे की हम देख सकते है
60, 50 के बाद जुड़ेगा और 50 वाली node पूर्णतया भर चुकी है ।
इसीलिए 60 के जुडने पर यह node हो भागों मे विभक्त हो जाएगी
और यह node उन दोनों का parent node का मान root node मे merge हो जाएगा ।
अब हमे 55 को इसके स्थान के अनुरूप जोड़ देंगे।
अब हमे 77 को जोड़ना है । जैसे की हम देख सकते है ।
77, 60 के बाद जुड़ेगा ।
अतः यहाँ पर भी node विभिक्त होगी और चूंकि अभी भी root node मे स्थान रिक्त है
इसलिए इस node का मान root मे चला जाएगा ।
अब यह tree balanced है और इस प्रकार बनाया गया है की इसकी समस्त leaves एक ही level पर है ।
B- Tree मे से Nodeमिटाना
जैसे की हम जोड़ने मे पहले key तथा उसका स्थान देखते है ।
उसी प्रकार मिटाने मे भी key तथा उसके स्थान को ढूंढते है ।
यदि मिटाई जाने वाली key एक terminal (leaf) है जो मिटाना सरल है
अर्थात केवल उस key को node मे से मिटा देना होगा है ।
यदि मिटाई जाने वाली key एक terminal (leaf) नहीं है
तो इसके successor के मन से बदल दिया जाता है
इस प्रकार यदि successor, terminal node मे है तो वहाँ से वह मिटा दिया जाएगा ।
इस प्रकार यदि successor , non-terminal node मे है
तो उसका successor, replace होगा और यही सारी शर्ते इस successor के साथ भी लगेंगी ।
अतः यह देखा जाए तो प्रत्येक प्रकार के deletion मे terminal node मे से एक key अवश्य मिटेगी ।
यदि हम H को delete करते है तो बहुत आसान है
अर्थात केवल H को node मे से delete कर देंगे।
यदि हम J को मिटाते है तो इसके successor , K को इसके स्थान पर copy करना होगा ।
यदि हम F को मिटाते है तो यहाँ underflow की स्थिति उत्पन्न हो जाएगी ।
देखा जाए तो यहाँ F के खत्म होते ही G का एक child खत्म हो जाएगा ।
अतः G के remove करके E के child node मे भेज दिया जाएगा ,
तो इसमे निम्न स्थिति उत्पन्न हो जाएगी ।
इस प्रकार दिये गए क्रम का B- tree बनाया जा सकता है
और किसी B-tree मे से किसी वांछित key को मिटाया भी जा सकता है ।
Note:- यह पोस्ट केसी लगी आपको अपनी राय comment कर कर बताए ।