binary search tree in Hindi with example - Computer in Hindi | Business in Hindi

Sunday, January 10, 2021

binary search tree in Hindi with example

 एक 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 in hindi
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


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


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


बाइनरी सर्च ट्री (BST) में, प्रत्येक नोड में-

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


 
Example-

binary search tree example
binary search tree


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

Number of Binary Search Trees
Number of Binary Search Trees


Example binary search tree -

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

= 2 × 3C3 / 3 + 1

= 6C3 / 4

= 5

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

Binary Search Tree in Hindi
Binary Search Tree Construction

 


आइए निम्नलिखित उदाहरण का उपयोग करके एक बाइनरी खोज ट्री के निर्माण को समझते हैं-

 
उदाहरण-

संख्याओं के निम्नलिखित अनुक्रम के लिए एक बाइनरी सर्च ट्री (BST) का निर्माण करें-

50, 70, 60, 20, 90, 10, 40, 100

जब तत्वों को एक अनुक्रम में दिया जाता है,

    हमेशा पहले तत्व को रूट नोड मानते हैं।
    दिए गए तत्वों पर विचार करें और उन्हें एक-एक करके BST में डालें।

 

नीचे बताए अनुसार बाइनरी सर्च ट्री का निर्माण किया जाएगा।

 
50 डालें-

binary search tree
Insert 50



 70 डालें-

 

Insert 70
Insert 70-


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

60 डालें-

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

Insert 60
Insert 60

 20 डालें-

 
Insert 20
Insert 20



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

90- डालें

 
Insert 90-
binary search tree Insert 90



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

10 डालें-

 
Insert 10
Insert 10



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

40- डालें

 
Insert 40 in binary search tree
Insert 40



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

100 डालें-

 
Insert 100
Insert 100 in binary search tree



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




No comments:

Post a Comment