विभिन्न प्रोग्रामिंग समस्याओं के लिए स्ट्रिंग्स को अनिवार्य रूप से सबसे महत्वपूर्ण और सामान्य विषयों के रूप में देखा जा सकता है। स्ट्रिंग प्रसंस्करण में कई वास्तविक दुनिया अनुप्रयोग होते हैं, जैसे:

• Search Engines
• Genome Analysis
• Data Analytics

पाठ्य सामग्री के रूप में हमारे सामने प्रस्तुत सभी सामग्री को केवल  strings के अलावा और कुछ भी नहीं देखा जा सकता है।

trie data structure In Hindi

Tries एक अत्यंत विशेष और उपयोगी डेटा-संरचना है जो एक स्ट्रिंग के उपसर्ग पर आधारित हैं। उनका उपयोग डेटा के “Retrieval” का प्रतिनिधित्व करने के लिए किया जाता है और इस प्रकार Trie नाम।

prefix trie : What is prefix:

एक स्ट्रिंग का उपसर्ग कुछ भी नहीं है लेकिन (n, n<=mod(S)) किसी भी अक्षर को एक स्ट्रिंग की शुरुआत से सख्ती से शुरुआत माना जा सकता है। उदाहरण के लिए, शब्द “abacaba” में निम्नलिखित उपसर्ग हैं:

a
ab
aba
abac
abaca
abacab

Trie एक विशेष Data structure है जिसका उपयोग स्ट्रिंग्स को स्टोर करने के लिए किया जाता है जिसे ग्राफ की तरह देखा जा सकता है। यह नोड्स और किनारों के होते हैं। प्रत्येक नोड में अधिकतम 26 बच्चे होते हैं और प्रत्येक माता-पिता नोड को अपने बच्चों से जोड़ते हैं। ये 26 पॉइंटर्स अंग्रेजी वर्णमाला के 26 अक्षरों में से प्रत्येक के लिए पॉइंटर्स के अलावा और कुछ नहीं हैं। हर किनारे के लिए एक अलग एज बनाए रखा गया है।

एक trie data structure में उनके prefix के आधार पर स्ट्रिंग्स को ऊपर से नीचे तरीके से संग्रहीत किया जाता है। लंबाई 1 के सभी उपसर्गों को स्तर 1 तक संग्रहीत किया जाता है, लंबाई 2 के सभी prefixes को स्तर 2 और इसी तरह तक हल किया जाता है।

For example For trie data structure, consider the following diagram :- :

trie data structure

अब, कोई सोच रहा होगा कि एकल स्ट्रिंग को संसाधित करने के लिए डेटा संरचना जैसे ट्राई का उपयोग क्यों किया जाए? दरअसल, ट्राई का इस्तेमाल आम तौर पर स्ट्रिंग्स के समूहों पर किया जाता है, न कि एक स्ट्रिंग के बजाय। जब कई तार दिए जाते हैं, तो हम उनके आधार पर कई तरह की समस्याओं को हल कर सकते हैं। 

उदाहरण के लिए, एक अंग्रेजी शब्दकोश और एक स्ट्रिंग पर विचार करें, स्ट्रिंग से मेल खाते शब्दकोश स्ट्रिंग (s)से अधिकतम लंबाई का उपसर्ग खोजें। एक Naive approach का उपयोग करके इस समस्या को हल करने के लिए हमें दिए गए स्ट्रिंग के उपसर्ग को शब्दकोश में हर दूसरे शब्द के उपसर्ग के साथ मेल करना होगा और अधिकतम नोट करना होगा। यह एक  expensive प्रक्रिया है जिस पर समय लगेगा। trie in data structure इस समस्या को अधिक कुशल तरीके से हल कर सकती है।

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

तो,  Trie में किसी भी स्ट्रिंग का insertion रूट नोड से शुरू होता है। लंबाई एक के सभी उपसर्ग रूट नोड के प्रत्यक्ष बच्चे हैं। इसके अलावा, लंबाई 2 के सभी उपसर्ग लेवल एक पर मौजूद नोड्स के बच्चे बन जाते हैं।

टायर में स्ट्रिंग डालने के लिए  pseudo code निम्नानुसार दिखेगा:

trie data structure

 इस ट्यूटोरियल में, आप सीखेंगे कि 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

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

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

b tree insertion

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

b tree example

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

B tree in hindi

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

b tree in data structure

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

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 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

 एक binary search tree (BST) एक पेड़ है जिसमें सभी नोड्स नीचे वर्णित गुणों का पालन करते हैं -

•     बाएं sub-tree की कुंजी (Key) का मूल्य उसके parent (root) node's key के मूल्य से कम है।
  

•     सही sub-tree की कुंजी का मूल्य उसके parent (रूट) नोड की कुंजी(Key) के मूल्य से अधिक या उसके बराबर है।

इस प्रकार, binary search tree (BST) अपने सभी sub-tree को दो खंडों में विभाजित करता है; right sub-tree और left sub-tree और इसे इस प्रकार परिभाषित किया जा सकता है -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

binary search tree in hindi

BST एक तरह से व्यवस्थित नोड्स का संग्रह है जहां वे BST properties को बनाए रखते हैं। 

प्रत्येक नोड में एक कुंजी (Key) और एक संबद्ध मूल्य (associated value) होता है। 

खोज करते समय, वांछित कुंजी की तुलना BST में कुंजियों से की जाती है और यदि पाया जाता है, तो संबंधित मान पुनः प्राप्त होता है।

निम्नलिखित BST का एक चित्रमय प्रतिनिधित्व है -

binary tree in data structure

Basic Operations : 

एक पेड़ के बुनियादी संचालन निम्नलिखित हैं -

•     Search −  एक Tree में एक तत्व खोजता है।

•     Insert −  एक tree में एक तत्व सम्मिलित करता है।

•     Pre-order Traversal - एक ट्री को प्री-ऑर्डर तरीके से ट्रेस करता है।

•    In-order Traversal −  एक ट्री को इन-ऑर्डर तरीके से ट्रेस करता है।

•    Post-order Traversal  - पोस्ट-ऑर्डर तरीके से एक पेड़ का पता लगाता है।

Node For binary search tree in Hindi

कुछ डेटा वाले नोड को परिभाषित करें, इसके बाएं और दाएं बच्चे के नोड्स के संदर्भ।

Node For binary search tree in Hindi

Search Operation

जब भी कोई तत्व खोजना हो, तो रूट नोड से खोजना शुरू करें। फिर यदि डेटा कुंजी मूल्य से कम है, तो बाएं सबट्री में तत्व की खोज करें। अन्यथा, सही उपशीर्षक में तत्व की खोज करें। प्रत्येक नोड के लिए समान एल्गोरिथ्म का पालन करें।

Algorithm for binary search tree

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

Insert Operation

जब भी कोई तत्व सम्मिलित करना हो, तो पहले उसके उचित स्थान का पता लगाएं। रूट नोड से खोजना शुरू करें, फिर यदि डेटा कुंजी मूल्य से कम है, तो बाएं सबट्री में खाली स्थान खोजें और डेटा डालें। अन्यथा, सही सबट्री में खाली स्थान खोजें और डेटा डालें।

Insert Operation Algorithm For binary search tree

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}   

•    binary search tree एक विशेष ट्री डेटा संरचना है।
•     एक binary tree में, प्रत्येक नोड में अधिकतम 2 बच्चे हो सकते हैं।
•     एक binary tree में, नोड्स को किसी भी यादृच्छिक क्रम में व्यवस्थित किया जा सकता है।

binary search tree in Hindi

•     इसके बाएं उप पेड़ में केवल छोटे मूल्य
•     इसके दाहिने उप वृक्ष में केवल बड़े मूल्य हैं

 
Example-

binary search tree

Number of Binary Search Trees

Example binary search tree -

3 अलग-अलग कुंजी के साथ संभव बाइनरी सर्च ट्री की संख्या

= 2 × 3C3 / 3 + 1

= 6C3 / 4

= 5

बाइनरी सर्च ट्री कंस्ट्रक्शन-

Binary Search Tree Construction

Insert 50

 70 डालें-

 

Insert 70-

Insert 60

 20 डालें-

 

Insert 20

    20 <50 के रूप में, इसलिए 50 के बाईं ओर 20 डालें।

90- डालें

 

binary search tree Insert 90

    90> 50 के रूप में, इसलिए 90 को 50 के दाईं ओर डालें।
    90> 70 के रूप में, इसलिए 70 के दाईं ओर 90 डालें।

10 डालें-

 

Insert 10

    10 <50 के रूप में, इसलिए 10 को 50 के बाईं ओर डालें।
    10 <20 के रूप में, इसलिए 10 को 20 के बाईं ओर डालें।

40- डालें

 

Insert 40

    40 <50 के रूप में, इसलिए 40 को 50 के बाईं ओर डालें।
    40> 20 के रूप में, इसलिए 40 को 20 के दाईं ओर डालें।

100 डालें-

 

Insert 100 in binary search tree

    100> 50 के रूप में, इसलिए 50 के दाईं ओर 100 डालें।
    100> 70 के रूप में, इसलिए 70 के दाईं ओर 100 डालें।
    100> 90 के रूप में, इसलिए 90 के दाईं ओर 100 डालें।