Computer in Hindi | Business in Hindi: b tree in hindi
Showing posts with label b tree in hindi. Show all posts
Showing posts with label b tree in hindi. Show all posts

Monday, January 11, 2021

b tree in data structure in Hindi - Data structure In Hindi

January 11, 2021 0
b tree in data structure in Hindi - Data structure In Hindi

 इस ट्यूटोरियल में, आप सीखेंगे कि b tree in data structure क्या है। साथ ही, आपको C, C ++, Java और पायथन में B - Tree पर सर्च ऑपरेशन के काम के उदाहरण मिलेंगे।

b tree in data structure एक विशेष प्रकार का स्व-संतुलन खोज Tree है जिसमें प्रत्येक नोड में एक से अधिक कुंजी हो सकती हैं और दो से अधिक Child हो सकते हैं। यह b search tree का एक सामान्यीकृत रूप है।

इसे ऊंचाई वाले संतुलित m-way tree के रूप में भी जाना जाता है।



B tree in hindi
B tree in hindi

Why b tree in data structure?


हार्ड-डिस्क की तरह भौतिक भंडारण मीडिया तक पहुँचने में कम समय की आवश्यकता के बढ़ने के साथ
b tree की आवश्यकता उत्पन्न हुई। 

द्वितीयक भंडारण उपकरण एक बड़ी क्षमता के साथ धीमे हैं। इस तरह की डेटा संरचनाओं की आवश्यकता थी जो डिस्क एक्सेस को कम करती हैं।

अन्य डेटा संरचनाएं जैसे कि एक
b search tree, एवल ट्री, रेड-ब्लैक ट्री, आदि एक नोड में केवल एक कुंजी स्टोर कर सकते हैं। 

यदि आपको बड़ी संख्या में चाबियाँ जमा करनी हैं, तो ऐसे पेड़ों की ऊंचाई बहुत बड़ी हो जाती है और पहुंच का समय बढ़ जाता है।

हालांकि,
b tree एक ही नोड में कई चाबियाँ संग्रहीत कर सकते हैं और कई बच्चे नोड्स हो सकते हैं। यह तेजी से डिस्क एक्सेस की अनुमति देते हुए ऊंचाई को कम करता है।


B-tree in Hindi and it's Properties

  •     प्रत्येक नोड x के लिए, कुंजियाँ बढ़ते क्रम में संग्रहीत की जाती हैं।
  •     प्रत्येक नोड में, बूलियन मान x.leaf होता है जो x पत्ती होने पर सत्य होता है।
  •     यदि n पेड़ का क्रम है, तो प्रत्येक आंतरिक नोड में प्रत्येक बच्चे के लिए एक सूचक के साथ अधिकांश n - 1 कुंजी हो सकती हैं।
  •     रूट को छोड़कर प्रत्येक नोड में अधिकांश n बच्चे और कम से कम n / 2 बच्चे हो सकते हैं।
  •     सभी पत्तियों में एक ही गहराई (यानी पेड़ की ऊंचाई-एच) होती है।
  •     मूल में कम से कम 2 बच्चे हैं और इसमें न्यूनतम 1 कुंजी है।
  •     यदि n-1 है, तो ऊँचाई h और न्यूनतम डिग्री t, 2, h + logt (n + 1) / 2 के किसी भी n-key B- वृक्ष के लिए।

Operations b tree in data structure in Hindi

Learn Searching in B tree in Hindi

बी-ट्री में एक तत्व की खोज करना Binary Search Tree में एक तत्व की खोज का सामान्यीकृत रूप है। निम्न चरणों का पालन किया जाता है।

  •     रूट नोड से शुरू, नोड की पहली कुंजी के साथ तुलना करें।
  •     यदि k = the first key of the node, तो नोड और इंडेक्स वापस करें।
  •     यदि k.leaf = true है, तो NULL (यानी नहीं मिला) लौटें।
  •     यदि k < the first key of the root node, तो इस कुंजी के बाएं बच्चे को पुनरावर्ती खोजें।
  •     यदि वर्तमान नोड और k > the first key में एक से अधिक कुंजी है, तो नोड में अगली कुंजी के साथ तुलना करें।
  •     यदि k < next key तो इस कुंजी के बाएं बच्चे को खोजें (यानी। k पहली और दूसरी कुंजियों के बीच स्थित है)।
  •     और, कुंजी के सही बच्चे को खोजें।
  •     पत्ती तक पहुंचने तक चरण 1 से 4 दोहराएं।


Searching b tree example


  •     हमें डिग्री 3 के नीचे के Tree में k= 17 की खोज करनी चाहिए।
B-tree in hindi
B-tree in hindi

  • k रूट में नहीं मिला है, इसलिए इसे रूट की के साथ तुलना करें।

b tree insertion
b tree insertion
  • K> 11 के बाद से, रूट नोड के सही बच्चे पर जाएं।


b tree example
b tree example

 

  • K की तुलना 16 से करें। k> 16 के बाद से k की तुलना अगली कुंजी 18 से करें।

B tree in hindi
B tree in hindi

  • K <18 के बाद से, k 16 और 18 के बीच स्थित है। 16 के दाहिने बच्चे या 18 के बाएं बच्चे में खोजें।


b tree in data structure
b tree in data structure

  • k पाया जाता है।

b tree example
b tree example


Algorithm For B tree in Hindi

BtreeSearch(x, k)
 i = 1
 while i ≤ n[x] and k ≥ keyi[x]        // n[x] means number of keys in x node
    do i = i + 1
if i  n[x] and k = keyi[x]
    then return (x, i)
if leaf [x]
    then return NIL
else
    return BtreeSearch(ci[x], k)

B tree example program in c

#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct BTreeNode {
  int val[MAX + 1], count;
  struct BTreeNode *link[MAX + 1];
};

struct BTreeNode *root;

// Create a node
struct BTreeNode *createNode(int val, struct BTreeNode *child) {
  struct BTreeNode *newNode;
  newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
  newNode->val[1] = val;
  newNode->count = 1;
  newNode->link[0] = root;
  newNode->link[1] = child;
  return newNode;
}

// Insert node
void insertNode(int val, int pos, struct BTreeNode *node,
        struct BTreeNode *child) {
  int j = node->count;
  while (j > pos) {
    node->val[j + 1] = node->val[j];
    node->link[j + 1] = node->link[j];
    j--;
  }
  node->val[j + 1] = val;
  node->link[j + 1] = child;
  node->count++;
}

// Split node
void splitNode(int val, int *pval, int pos, struct BTreeNode *node,
         struct BTreeNode *child, struct BTreeNode **newNode) {
  int median, j;

  if (pos > MIN)
    median = MIN + 1;
  else
    median = MIN;

  *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
  j = median + 1;
  while (j <= MAX) {
    (*newNode)->val[j - median] = node->val[j];
    (*newNode)->link[j - median] = node->link[j];
    j++;
  }
  node->count = median;
  (*newNode)->count = MAX - median;

  if (pos <= MIN) {
    insertNode(val, pos, node, child);
  } else {
    insertNode(val, pos - median, *newNode, child);
  }
  *pval = node->val[node->count];
  (*newNode)->link[0] = node->link[node->count];
  node->count--;
}

// Set the value
int setValue(int val, int *pval,
           struct BTreeNode *node, struct BTreeNode **child) {
  int pos;
  if (!node) {
    *pval = val;
    *child = NULL;
    return 1;
  }

  if (val < node->val[1]) {
    pos = 0;
  } else {
    for (pos = node->count;
       (val < node->val[pos] && pos > 1); pos--)
      ;
    if (val == node->val[pos]) {
      printf("Duplicates are not permitted\n");
      return 0;
    }
  }
  if (setValue(val, pval, node->link[pos], child)) {
    if (node->count < MAX) {
      insertNode(*pval, pos, node, *child);
    } else {
      splitNode(*pval, pval, pos, node, *child, child);
      return 1;
    }
  }
  return 0;
}

// Insert the value
void insert(int val) {
  int flag, i;
  struct BTreeNode *child;

  flag = setValue(val, &i, root, &child);
  if (flag)
    root = createNode(i, child);
}

// Search node
void search(int val, int *pos, struct BTreeNode *myNode) {
  if (!myNode) {
    return;
  }

  if (val < myNode->val[1]) {
    *pos = 0;
  } else {
    for (*pos = myNode->count;
       (val < myNode->val[*pos] && *pos > 1); (*pos)--)
      ;
    if (val == myNode->val[*pos]) {
      printf("%d is found", val);
      return;
    }
  }
  search(val, pos, myNode->link[*pos]);

  return;
}

// Traverse then nodes
void traversal(struct BTreeNode *myNode) {
  int i;
  if (myNode) {
    for (i = 0; i < myNode->count; i++) {
      traversal(myNode->link[i]);
      printf("%d ", myNode->val[i + 1]);
    }
    traversal(myNode->link[i]);
  }
}

int main() {
  int val, ch;

  insert(8);
  insert(9);
  insert(10);
  insert(11);
  insert(15);
  insert(16);
  insert(17);
  insert(18);
  insert(20);
  insert(23);

  traversal(root);

  printf("\n");
  search(11, &ch, root);
}

b tree insertion Operation

  •      यदि पेड़ खाली है, तो रूट नोड आवंटित करें और कुंजी डालें।
  •      नोड में कुंजियों की अनुमत संख्या को अपडेट करें।
  •      सम्मिलन के लिए उपयुक्त नोड खोजें।
  •      यदि नोड भरा हुआ है, तो नीचे दिए गए चरणों का पालन करें।
  •      तत्वों को बढ़ते क्रम में डालें।
  •      अब, इसकी सीमा से अधिक तत्व हैं। तो, मंझला में विभाजित करें।
  •      माध्य कुंजी को ऊपर की ओर धकेलें और बाएँ कुंजियों को बाएँ बच्चे के रूप में और दाएँ कुंजियों को दाएँ बच्चे के रूप में बनाएँ।
  •      यदि नोड भरा नहीं है, तो नीचे दिए गए चरणों का पालन करें।
  •      बढ़ते क्रम में नोड डालें।

b tree insertion Example

आइए नीचे दिए गए चित्रों के साथ सम्मिलन ऑपरेशन को समझते हैं।

सम्मिलित किए जाने वाले तत्व 8, 9, 10, 11, 15, 16, 17, 18, 20, 23 हैं।

b tree example
b tree example

 b tree insertion Algorithm

 

BreeInsertion(T, k)
r  root[T]
if n[r] = 2t - 1
    s = AllocateNode()
    root[T] = s
    leaf[s] = FALSE
    n[s] <- 0
    c1[s] <- r
    BtreeSplitChild(s, 1, r)
    BtreeInsertNonFull(s, k)
else BtreeInsertNonFull(r, k)
BtreeInsertNonFull(x, k)
i = n[x]
if leaf[x]
    while i  1 and k < keyi[x]
        keyi+1 [x] = keyi[x]
        i = i - 1
    keyi+1[x] = k
    n[x] = n[x] + 1
else while i  1 and k < keyi[x]
        i = i - 1
    i = i + 1
    if n[ci[x]] == 2t - 1
        BtreeSplitChild(x, i, ci[x])
        if k &rt; keyi[x]
            i = i + 1
    BtreeInsertNonFull(ci[x], k)
BtreeSplitChild(x, i)
BtreeSplitChild(x, i, y)
z = AllocateNode()
leaf[z] = leaf[y]
n[z] = t - 1
for j = 1 to t - 1
    keyj[z] = keyj+t[y]
if not leaf [y]
    for j = 1 to t
        cj[z] = cj + t[y]
n[y] = t - 1
for j = n[x] + 1 to i + 1
    cj+1[x] = cj[x]
ci+1[x] = z
for j = n[x] to i
    keyj+1[x] = keyj[x]
keyi[x] = keyt[y]
n[x] = n[x] + 1