Data Structures in Hindi : BST Insertion

Binary Search Tree Insertion

  • Introduction to binary search tree insertion in Hindi
  • Function for binary search tree insertion in Hindi 

Introduction to Binary Search Tree Insertion

जब एक binary search tree में कोई नयी node add की जाती है तो वह operation insertion operation कहलाता है। Binary search tree में insertion operation को perform करने के 2 मुख्य steps होते है।

  1. Search for Location - इस step में उस location को search किया जाता है जँहा पर आप नयी node को insert करना चाहते है। 
  2. Insert New Node - इस step में नयी node को उस location पर insert किया जाता है। 

इन दोनों steps के बारे में निचे detail से बताया जा रहा है। 

Search for Location 

इस step में सबसे पूर्व आप यह देखते है की root node available है या नहीं। यदि root node available होती है तो आप नया element add कर सकते है। यदि root node available नहीं है तो सबसे पहले आप root node create करते है। 

यदि root node available है तो सबसे पहले आप नयी node की value को root node की value से compare करते है। यदि नयी node की value root node की value से छोटी होगी तो नयी node के लिए location left sub tree में search की जाएगी। 

यदि left subtree में कोई child नहीं है तो इसका मतलब है की नयी node के लिए जगह मिल गयी है। नयी node को वँही पर insert कर दिया जायेगा। यदि left subtree की का कोई child है तो उस child की value भी नयी node की value से compare की जाएगी और इसी प्रकार उसके भी left या right subtrees को search किया जायेगा। 

यदि नयी node की value root node की value से अधिक है तो right sub tree को search किया जायेगा। यदि right subtree में कोई child नहीं है तो इसका मतलब है की location मिल गयी है और नयी node यँही insert किया जायेगा। 

यदि right subtree में कोई child है तो उसकी value भी नयी node से compare की जाएगी और इसी प्रकार उसके भी left या right sub tree को search किया जायेगा। 

Binary search tree में हमेशा नयी node leaf node के रूप में insert कि जाती है क्योंकि एक binary search tree पहले से ही ordered form में organised होता है। इसलिए binary search tree में नयी node left या right sub tree में आखिर में ही insert होती है।

इसके अलावा binary search tree में insert की जा रही नयी node के कोई childran भी नहीं होते है क्योंकि binary search tree में नयी node हमेशा सभी nodes को compare करके ही insert की जाती है। 

एक बार जँहा आप नयी node insert करना चाहते है वह location मिलने में insertion operation का second step शुरू होता है। 

Insert New Node

एक binary search tree binary tree ही होता है इनमें फर्क सिर्फ इतना होता है की binary search tree में nodes को निश्चित क्रम में organise किया जाता है। 

Binary search tree के लिए भी node उसी प्रकार create की जाती है जिस प्रकार binary tree के लिए create की जाती है। इसका उदाहरण निचे दिया जा रहा है। 

struct Bi_Tree
{
    int Data;
    struct Node *LChild;
    struct Node *RChild;
}

root = (struct Bi_Tree*) malloc(sizeof(struct Bi_Tree));

जैसा की आप देख सकते है ऊपर दिए गए code में root node create की गयी है। इसी प्रकार आप Bi_Tree struct के दूसरे variables create करके और भी nodes create कर सकते है।

जब नयी node के लिए जगह मिल जाती है उस node को इस प्रकार dynamically memory assign करके उसके parent के left या right child pointer को assign कर दिया जाता है।

उदाहरण के लिए यदि location left में है तो आप इस प्रकार उसे assign करेंगे।

parentN->left = (struct Bi_Tree*) malloc(sizeof(struct Bi_Tree));

ऊपर दिया गया code सिर्फ आसानी से समझने के लिए दिया गया है। असल में parent-node को root के रूप में use करते हुए और नयी key value के साथ Insert() function को वापस call किया जाता है, क्योंकि binary search tree में insertion recursion द्वारा perform किया जाता है।

उदाहरण के लिए निचे दिया गया code को देखिये। 

parentN->left = Insert(parentN->left,Num);

Function for Binary Search Tree Insertion

Binary search tree में नयी node insert करने के लिए simple recursive function निचे दिया गया है। 

struct Bi_Tree *Insert (struct Bi_Tree* Root, int Num)
{
    if(Root == NULL)
    {
        Root = (struct Bi_Tree*) malloc(sizeof(struct Bi_Tree));
        Root -> Data = Num;
        Root -> LChild = NULL;
        Root -> RChild = NULL;
    }
    else
    {
        if(Num < Root -> Data)
        {
             Root -> Left = Insert (Root->Left, Num);
        }
        else
        {
             Root -> Right = Insert(Root->Right, Num);
        }
    }
    return(Root);
}


जब आप इस function को call करते है तो उसमे सबसे पूर्व binary search tree का root और नयी node की value pass की जाती है।

यदि root node available नहीं होती है तो root node create की जाती है। यदि root node available होती है तो उसकी value को नयी node की value से compare किया जाता है।

यदि नयी node की value छोटी होती है तो root के left child को नयी value assign किया जाता है ऐसा वापस Insert() function को call करके किया जाता है। लेकिन इस time root के रूप में मुख्य root node का left child होता है।

उसी प्रकार यदि नयी node की value root node से अधिक होती है तो root node के right child को नयी node assign कि जाती है और Insert function को call किया जाता है।  

      DMCA.com Protection Status

 Leave a comment