C Academy · पाठ

BST में जोड़ना

बाइनरी सर्च ट्री बनाएँ।

पाठ 2, कुल 4 में से13 चरण

BST में जोड़ना, CoddyKit पर C Academy का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह C Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। C Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

BST का क्रम नियम

Binary Search Tree (BST) एक बाइनरी ट्री है, जिसमें एक अतिरिक्त नियम होता है: प्रत्येक नोड के लिए, उसके बाएँ उपट्री के सभी मान छोटे और दाएँ उपट्री के सभी मान बड़े होते हैं।

यही क्रम हमें ट्री की ऊँचाई के अनुपात में समय लेकर खोजने, जोड़ने और हटाने देता है।

मान कहाँ रखा जाए

जोड़ने के लिए हम रूट से शुरू करके तुलना करते हैं। नया मान छोटा हो तो बाएँ जाते हैं; बड़ा हो तो दाएँ।

हम तब तक दोहराते हैं, जब तक कोई खाली स्थान (NULL) न मिल जाए—नया नोड ठीक वहीं रखा जाना चाहिए।

/* insert 7 into:
 *        10
 *       /  \
 *      5    15
 * 7 < 10 -> left;  7 > 5 -> right of 5
 */

create_node सहायक

जोड़ने की प्रक्रिया नए लीफ़ नोड बनाती है, इसलिए हम उस कंस्ट्रक्टर का फिर उपयोग करते हैं जो नोड का आवंटन और प्रारंभीकरण करता है।

दोनों बच्चे शुरू में NULL होते हैं, क्योंकि नया जोड़ा गया नोड हमेशा लीफ़ होता है।

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->left = n->right = NULL;
    return n;
}

पुनरावर्ती जोड़

सबसे साफ़ जोड़ने की विधि पुनरावर्ती होती है और संभवतः नए उपट्री रूट को लौटाती है।

यदि उपट्री खाली हो, तो हम नया नोड लौटाते हैं। अन्यथा बाएँ या दाएँ पुनरावृत्ति करते हैं, परिणाम को फिर से जोड़ते हैं और अपरिवर्तित रूट लौटाते हैं।

Node *insert(Node *root, int value) {
    if (root == NULL)
        return create_node(value);
    if (value < root->value)
        root->left = insert(root->left, value);
    else if (value > root->value)
        root->right = insert(root->right, value);
    return root;  /* equal: ignore duplicate */
}

रूट क्यों लौटाएँ

उपट्री रूट लौटाने से पैरेंट एक ही पंक्ति में कड़ी फिर से जोड़ सकता है: root->left = insert(root->left, v)।

जब उपट्री खाली थी, तो लौटाया गया नया नोड बच्चा बन जाता है। जब वह खाली नहीं थी, तो वही रूट लौटता है और कड़ी अपरिवर्तित रहती है।

/* The assignment does double duty:
 * - empty case: stores the new node
 * - non-empty:  stores the same pointer back (no-op)
 */
root->left = insert(root->left, value);

डुप्लिकेट मानों को संभालना

वास्तविक BST को समान मानों के साथ क्या करना है, यह तय करना पड़ता है। एक सामान्य विकल्प डुप्लिकेट को अनदेखा करना है, जैसा हमारा insert करता है—समान स्थिति के लिए कोई शाखा नहीं है।

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

if (value < root->value)
    root->left = insert(root->left, value);
else if (value > root->value)
    root->right = insert(root->right, value);
/* value == root->value -> do nothing */

BST बनाना

मानों का कोई क्रम जोड़ने पर ऐसा ट्री बनता है जिसका आकार जोड़ने के क्रम पर निर्भर करता है।

यहाँ हम कई संख्याएँ जोड़ते हैं और क्रम नियम सही होने की पुष्टि करने के लिए रूट के सीधे बच्चों को प्रदर्शित करते हैं।

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

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return create_node(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}

int main(void){
    Node *root = NULL;
    int data[] = {10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,data[i]);
    printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
    return 0;
}

पुनरावृत्ति के बिना जोड़ना

आप पुनरावृत्ति के बिना भी जोड़ सकते हैं। हम पॉइंटर के साथ नीचे की ओर बढ़ते हैं और पैरेंट को याद रखते हैं, जब तक कोई खाली स्थान न मिल जाए।

फिर नए नोड को उस पैरेंट की सही दिशा में जोड़ देते हैं।

void insert_iter(Node **rootp, int value) {
    Node *cur = *rootp, *parent = NULL;
    while (cur) {
        parent = cur;
        cur = (value < cur->value) ? cur->left : cur->right;
    }
    Node *n = create_node(value);
    if (!parent) *rootp = n;
    else if (value < parent->value) parent->left = n;
    else parent->right = n;
}

जोड़ने का क्रम ट्री का आकार तय करता है

1,2,3,4,5 को क्रमबद्ध क्रम में जोड़ने पर ऐसा विकृत ट्री बनता है जो लिंक्ड लिस्ट जैसा दिखता है और जिसकी ऊँचाई गिनती के बराबर होती है।

संतुलित क्रम में जोड़ने पर ऊँचाई log(n) के आसपास रहती है। संतुलन खोज की गति को सीधे प्रभावित करता है।

/* sorted insert 1..5 ->
 * 1
 *  \
 *   2
 *    \
 *     3   (height = 4, like a list)
 */

जोड़ने की लागत

हर बार जोड़ने पर रूट से लीफ़ तक एक मार्ग पर चला जाता है, इसलिए किया गया कार्य ट्री की ऊँचाई के अनुपात में होता है।

संतुलित ट्री में यह लगभग log(n) तुलनाएँ होती हैं; विकृत ट्री में यह n तक हो सकता है। इसी कारण स्व-संतुलित ट्री मौजूद हैं।

पूर्ण इंसर्ट प्रदर्शन

यह प्रोग्राम मान डालता है, फिर नोड गिनकर पुष्टि करता है कि पाँच अलग-अलग मान संग्रहीत हुए और डुप्लिकेट को नज़रअंदाज़ किया गया।

डुप्लिकेट 10 गिनती नहीं बढ़ाता, क्योंकि insert समान मानों को छोड़ देता है।

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

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,10,20};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("count=%d\n", count(root));
    return 0;
}

त्वरित जाँच

इंसर्शन के व्यवहार के बारे में विचार कीजिए।

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन

BST इंसर्शन में नए मान की तुलना प्रत्येक नोड से की जाती है; छोटा मान मिलने पर बाएँ और बड़ा मान मिलने पर दाएँ जाते हैं, जब तक कोई खाली स्थान न मिल जाए।

पुनरावर्ती रूप सबट्री का मूल लौटाता है, ताकि पैरेंट लिंक को साफ़-सुथरे ढंग से फिर जोड़ सके। इंसर्शन की लागत ट्री की ऊँचाई के साथ बढ़ती है, इसलिए इंसर्शन का क्रम महत्वपूर्ण होता है।

शुरुआत निःशुल्क

एआई शिक्षक के साथ C सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 39
पाठ: 144

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “BST में जोड़ना” पाठ निःशुल्क है?

हाँ—“BST में जोड़ना” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और C Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। C Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“BST में जोड़ना” में मैं क्या सीखूँगा?

बाइनरी सर्च ट्री बनाएँ। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ C Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या C Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर C Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।

“BST में जोड़ना” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस C Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर C Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← C Academy पर वापस जाएँ