PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases (BST में इंसर्शन और डिलीशन: इनऑर्डर सक्सेसर/प्रेडिसेसर नियम) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: BST Insertion places every new key strictly as a leaf node by following search comparisons to an empty child pointer in O(h) time. BST Deletion handles three distinct cases—0 children (simple removal), 1 child (bypass/promotion), and 2 children (replacing the node with its Inorder Successor or Predecessor before removing that single/zero-child substitute).
अध्याय सार: BST इंसर्शन में प्रत्येक नया मान तुलनाओं के आधार पर हमेशा एक लीफ नोड (Leaf) के रूप में जोड़ा जाता है। BST डिलीशन में तीन स्थितियां होती हैं: 0 चाइल्ड (सीधे हटाना), 1 चाइल्ड (चाइल्ड को ऊपर जोड़ना), तथा 2 चाइल्ड (नोड को उसके इनऑर्डर सक्सेसर या प्रीडीसेसर से बदलकर डिलीट करना)।
BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases: Detailed Notes & Architecture (BST में इंसर्शन और डिलीशन: इनऑर्डर सक्सेसर/प्रेडिसेसर नियम)
1. BST Insertion: Always Attached as a Leaf Node (BST इंसर्शन: सदैव लीफ नोड के रूप में जोड़ना)
[EN] Inserting a key k into a standard BST begins identically to an unsuccessful search: compare k against `curr->key` from the root downward (`k < curr->key` goes left, `k > curr->key` goes right) until hitting a NULL pointer, where a newly allocated leaf node is attached. Because existing internal nodes never shift during standard insertion, the operation takes O(h) time (O(log n) balanced, O(n) skewed). Duplicate keys are typically ignored, counted via a `freq` field, or routed consistently right.
[HI] सामान्य BST में नया मान डालने के लिए रूट से तुलना करते हुए नीचे जाते हैं जब तक NULL पॉइंटर न मिल जाए, और वहीं नया नोड (Leaf) जोड़ दिया जाता है। पुराने नोड्स के स्थान न बदलने से समय जटिलता O(h) होती है। डुप्लीकेट मान या तो अनदेखे किए जाते हैं, काउंट किए जाते हैं, या एक निश्चित तरफ भेजे जाते हैं।
2. Deletion Case 1 (0 Children) & Case 2 (1 Child) (डिलीशन केस 1 (0 चाइल्ड) एवं केस 2 (1 चाइल्ड))
[EN] When deleting a node with 0 children (a Leaf node), no subtrees depend on it: simply set its parent's pointer to NULL and `free()` the node. When deleting a node with exactly 1 child (either left-only or right-only), bypass the deleted node by pointing its parent directly to its single non-NULL child—promoting that entire child subtree upward seamlessly without violating any BST ordering invariant.
[HI] केस 1 (0 चाइल्ड / लीफ नोड) में नोड के नीचे कोई सबट्री नहीं होता, इसलिए पेरेंट के पॉइंटर को NULL करके नोड को `free()` कर देते हैं। केस 2 (1 चाइल्ड) में डिलीट किए जाने वाले नोड को बाईपास कर उसके पेरेंट को सीधे उसके इकलौते चाइल्ड से जोड़ देते हैं, जिससे पूरा सबट्री बिना क्रम टूटे ऊपर आ जाता है।
3. Deletion Case 3 (2 Children): Inorder Successor / Predecessor (डिलीशन केस 3 (2 चाइल्ड): इनऑर्डर सक्सेसर या प्रीडीसेसर नियम)
[EN] When deleting a node `x` that has 2 non-NULL children, we cannot directly bypass it because two subtrees remain. Instead, we copy the key of EITHER (a) `x`'s Inorder Successor—the minimum (leftmost) node in `x->right`—OR (b) `x`'s Inorder Predecessor—the maximum (rightmost) node in `x->left`—into `x`, and then delete that substitute node. Crucially, the Inorder Successor can NEVER have a left child (so it has at most 1 right child), and the Predecessor can NEVER have a right child—reducing deletion cleanly to Case 1 or Case 2!
[HI] केस 3 (2 चाइल्ड) में सीधे हटाने से दोनों सबट्री अनाथ हो जाएंगे। अतः नोड x के स्थान पर या तो उसका इनऑर्डर सक्सेसर (राइट सबट्री का सबसे छोटा/बायां नोड) या उसका इनऑर्डर प्रीडीसेसर (लेफ्ट सबट्री का सबसे बड़ा/दायां नोड) कॉपी कर दिया जाता है। सक्सेसर का लेफ्ट चाइल्ड कभी नहीं होता, इसलिए अब वह केस 1 या केस 2 की तरह आसानी से डिलीट हो जाता है।
4. Time Complexity & Hibbard Deletion Asymmetry (समय जटिलता एवं हिबार्ड डिलीशन विषमता)
[EN] Insertion and all three Deletion cases run in O(h) worst-case time (O(log n) in balanced BSTs, O(n) in skewed BSTs), because finding the target and descending into its subtree for the Inorder Successor follows a single downward path of length <= h. Note an important theoretical subtlety (Hibbard's result): always choosing the Inorder Successor (never alternating with Predecessor) over many random delete+insert pairs gradually skews an unbalanced BST toward Theta(sqrt(n)) average height instead of O(log n).
[HI] इंसर्शन और डिलीशन के तीनों केस O(h) समय में चलते हैं (संतुलित में O(log n), स्क्यूड में O(n))। एक महत्वपूर्ण तथ्य (Hibbard Deletion): यदि लाखों इंसर्शन-डिलीशन में हमेशा केवल इनऑर्डर सक्सेसर ही चुना जाए (प्रीडीसेसर के साथ बारी-बारी न बदलें), तो रैंडम BST धीरे-धीरे तिरछा होकर उसकी औसत ऊंचाई O(sqrt(n)) तक बढ़ सकती है।
Syntax, Formula & Technical Example (BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases)
// BST Deletion handling 0, 1, and 2 Children Cases (Inorder Successor)
Node* deleteBST(Node* root, int key) {
if (!root) return NULL;
if (key < root->data) root->left = deleteBST(root->left, key);
else if (key > root->data) root->right = deleteBST(root->right, key);
else {
if (!root->left) { Node* t = root->right; free(root); return t; } // 0 or 1 child
if (!root->right) { Node* t = root->left; free(root); return t; } // 1 child
Node* succ = findMin(root->right); // 2 children: Inorder Successor
root->data = succ->data;
root->right = deleteBST(root->right, succ->data);
}
return root;
}
BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases Quick Reference & Comparison Table
| BST Operation / Case | Mechanism Applied | Key Exam Fact |
|---|---|---|
| BST Insertion | Follow search path to NULL and attach new leaf | Always inserts at a leaf in O(h) time |
| Delete: 0 Children (Leaf) | Set parent link to NULL and free node | Simplest case; zero subtree adjustment needed |
| Delete: 1 Child | Bypass node; link parent directly to single child | Promotes entire child subtree upward intact |
| Delete: 2 Children | Copy Inorder Successor or Predecessor, then delete it | Substitute node always has <= 1 child |
BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases Top 20 Bilingual MCQs with Answers
Q1. In a standard (non-self-balancing) BST, where is a newly inserted unique key ALWAYS placed?
(एक मानक (गैर-संतुलित) BST में डाली गई नई अद्वितीय कुंजी सदैव कहाँ रखी जाती है?)
(A) Always replacing an internal node
(B) As a new Leaf node at a previously NULL child position
(C) At the global root of the tree
(D) At the middle depth of the tree
Correct Answer: (B)
[EN] Standard BST insertion descends down search comparisons until reaching NULL and attaches the node as a leaf.
[HI] सामान्य BST में नया मान हमेशा खोज मार्ग के अंत में NULL स्थान पर एक नई पत्ती (Leaf) के रूप में जुड़ता है।
Q2. When deleting a node with 2 children from a BST, which two valid candidates can replace its key while preserving BST order?
(BST से 2 चाइल्ड वाले नोड को डिलीट करते समय क्रम बनाए रखने के लिए किन दो विकल्पों में से किसी एक से उसे बदला जा सकता है?)
(A) Either its Inorder Successor or its Inorder Predecessor
(B) Either its immediate left or right child always
(C) Its parent node or sibling node
(D) Always the global minimum or maximum
Correct Answer: (A)
[EN] Inorder Successor (min of right subtree) and Inorder Predecessor (max of left subtree) sit immediately adjacent in sorted order.
[HI] केवल इनऑर्डर सक्सेसर (राइट सबट्री का न्यूनतम) या इनऑर्डर प्रीडीसेसर (लेफ्ट सबट्री का अधिकतम) ही BST क्रम को सुरक्षित रख सकते हैं।
Q3. How is the Inorder Successor of a node `x` with 2 children located inside a BST?
(2 चाइल्ड वाले नोड `x` का इनऑर्डर सक्सेसर BST में कैसे खोजा जाता है?)
(A) Follow `right` pointers from `x->right` to the maximum
(B) Move once to `x->right`, then follow `left` pointers all the way to the leftmost node
(C) Check `x->parent` only
(D) Move once to `x->left`, then follow `right` pointers
Correct Answer: (B)
[EN] The smallest key in `x`'s right subtree sits at the leftmost node of `x->right`.
[HI] इनऑर्डर सक्सेसर `x->right` में जाकर सबसे बाएं (न्यूनतम) नोड तक जाने पर प्राप्त होता है।
Q4. Why does deleting the Inorder Successor node after copying its value ALWAYS reduce to Case 1 (0 children) or Case 2 (1 child)?
(मान कॉपी करने के बाद इनऑर्डर सक्सेसर को डिलीट करना सदैव केस 1 (0 चाइल्ड) या केस 2 (1 चाइल्ड) में ही क्यों बदल जाता है?)
(A) Because it has 2 right children
(B) Because the Inorder Successor is always a leaf
(C) Because the root has only 1 child
(D) Because the leftmost node of the right subtree can NEVER have a left child
Correct Answer: (D)
[EN] If the successor had a left child, that left child would be smaller—meaning the node wasn't the leftmost (minimum)!
[HI] सबसे बायां नोड होने के कारण इनऑर्डर सक्सेसर का लेफ्ट चाइल्ड हो ही नहीं सकता, अतः उसके अधिकतम 1 (राइट) चाइल्ड ही हो सकता है।
Q5. In BST deletion of a node having ONLY 1 child (say a left subtree and no right child), how is the deletion performed?
(केवल 1 चाइल्ड (जैसे केवल लेफ्ट चाइल्ड) वाले नोड को BST से डिलीट कैसे किया जाता है?)
(A) Replace it with the root of the tree
(B) Link the deleted node's parent directly to its single left child, bypassing and freeing the deleted node
(C) Swap it with the global minimum node
(D) Delete its entire left subtree too
Correct Answer: (B)
[EN] Because all keys in that single child subtree already satisfy the parent's BST bound, bypassing preserves full ordering.
[HI] डिलीट होने वाले नोड के पेरेंट को सीधे उसके इकलौते चाइल्ड से जोड़कर नोड को मुक्त कर देते हैं।
Q6. In BST deletion, suppose we delete node 50 (root) from a BST having Inorder [10, 20, 30, 50, 60, 70, 80] using Inorder Successor. Which key replaces 50?
(मान लें किसी BST का इनऑर्डर [10, 20, 30, 50, 60, 70, 80] है और हम रूट 50 को इनऑर्डर सक्सेसर विधि से डिलीट करते हैं। 50 की जगह क्या आएगा?)
(A) 70
(B) 10
(C) 30
(D) 60
Correct Answer: (D)
[EN] 60 immediately follows 50 in Inorder (minimum of right subtree), so 60 replaces 50; note 30 would be Inorder Predecessor.
[HI] इनऑर्डर में 50 के ठीक बाद 60 (सक्सेसर) आता है; प्रीडीसेसर चुनने पर 30 आता।
Q7. What is the worst-case time complexity of inserting a single key into an unbalanced BST currently holding n keys?
(n कुंजियों वाले असंतुलित BST में एक नई कुंजी डालने (Insert) की सबसे खराब स्थिति में समय जटिलता क्या है?)
(A) O(1)
(B) O(n)
(C) O(log n)
(D) O(n^2)
Correct Answer: (B)
[EN] If the existing BST is skewed (height n - 1), walking down to the bottom NULL pointer takes Theta(n) comparisons.
[HI] यदि मौजूदा ट्री स्क्यूड है तो सबसे नीचे NULL स्थान तक पहुंचने में O(n) समय लग सकता है।
Q8. What is the time complexity of constructing a Binary Search Tree from scratch by inserting n arbitrary unsorted keys one by one in the worst case?
(n अनसॉर्टेड कुंजियों को एक-एक कर डालते हुए शुरू से BST बनाने की सबसे खराब स्थिति (Worst-case) में समय जटिलता कितनी है?)
(A) O(n log n)
(B) O(log n)
(C) O(n^2)
(D) O(n)
Correct Answer: (C)
[EN] If keys happen to be already sorted, insertion i takes i steps: 1 + 2 + ... + n = O(n^2) total time!
[HI] यदि कुंजियां संयोग से सॉर्टेड निकलीं तो i-वां तत्व डालने में i कदम लगेंगे, जिससे कुल समय 1+2+...+n = O(n^2) हो जाएगा।
Q9. In a BST, if you delete a key `k` and immediately re-insert the exact same key `k`, is the resulting tree ALWAYS structurally identical to the original?
(यदि किसी BST से कुंजी `k` को डिलीट करके तुरंत दोबारा `k` को इंसर्ट करें, तो क्या नया ट्री हमेशा पहले जैसा होगा?)
(A) Yes — for all balanced BSTs without rotations
(B) Only if `k` was the global root
(C) Yes — insertion and deletion are exact inverses
(D) No — if `k` was an internal node (1 or 2 children), re-inserting puts `k` back as a leaf, altering tree shape
Correct Answer: (D)
[EN] Deleting root 50 and re-inserting 50 promotes its successor/predecessor to root while placing 50 down at a leaf!
[HI] यदि `k` आंतरिक नोड था तो डिलीट करने पर उसकी जगह कोई और आ जाएगा और पुनः डालने पर `k` पत्ती बन जाएगा—अतः आकार बदल सकता है।
Q10. What happens in Hibbard's deletion analysis when thousands of random insertions and deletions ALWAYS replace 2-child nodes with the Inorder Successor?
(हज़ारों रैंडम इंसर्शन व डिलीशन में 2-चाइल्ड नोड को हमेशा केवल इनऑर्डर सक्सेसर से बदलने (Hibbard Deletion) से ट्री पर क्या प्रभाव पड़ता है?)
(A) Height shrinks to O(1)
(B) All duplicate keys disappear
(C) The tree automatically becomes a Perfect Binary Tree
(D) The BST gradually loses balance and its expected height degrades from O(log n) to Theta(sqrt(n))
Correct Answer: (D)
[EN] Asymmetric successor-only deletion biases the tree leftward over time; alternating successor and predecessor mitigates this drift.
[HI] केवल एक तरफ (सक्सेसर) से डिलीट करते रहने पर ट्री असंतुलित होकर उसकी ऊंचाई Theta(sqrt(n)) तक बढ़ जाती है।
Q11. Can the Inorder Predecessor of a 2-child node `x` EVER have a non-NULL right child?
(क्या 2 चाइल्ड वाले नोड `x` के इनऑर्डर प्रीडीसेसर का कोई नॉन-NULL राइट चाइल्ड हो सकता है?)
(A) No — because a right child would be larger, contradicting that the Predecessor is the maximum of `x`'s left subtree
(B) Yes — whenever the tree height exceeds 4
(C) Yes — if it has no left child
(D) Yes — if `x` is the root
Correct Answer: (A)
[EN] Maximum of `x->left` is the rightmost node in `x->left`, so its right pointer is guaranteed NULL.
[HI] लेफ्ट सबट्री का सबसे बड़ा (अधिकतम) नोड सबसे दाहिने छोर पर होता है, इसलिए उसका राइट पॉइंटर सदैव NULL होता है।
Q12. Suppose a BST contains keys [40, 20, 60, 10, 30, 50, 70] (40 root). After deleting 20 (using Inorder Successor) and then deleting 40 (using Inorder Successor), what is the new root?
([40, 20, 60, 10, 30, 50, 70] वाले BST (रूट 40) में पहले 20 और फिर 40 को इनऑर्डर सक्सेसर से डिलीट करने पर नया रूट क्या होगा?)
(A) 10
(B) 50
(C) 60
(D) 30
Correct Answer: (B)
[EN] Deleting 20 replaces it with 30 (leaving 40's right subtree untouched: 60 with 50, 70). Then deleting 40 picks min of right subtree = 50 as the new root!
[HI] 20 की जगह 30 आ जाएगा; फिर 40 डिलीट करने पर उसके राइट सबट्री [50, 60, 70] का न्यूनतम अर्थात 50 नया रूट बनेगा।
Q13. When deleting a leaf node (0 children) from a BST of n nodes, how many pointer assignments in the parent node are needed?
(n नोड्स वाले BST से 0 चाइल्ड वाले लीफ नोड को डिलीट करने के लिए पेरेंट नोड में कितने पॉइंटर बदलने पड़ते हैं?)
(A) log n pointers
(B) 2 pointers
(C) n pointers
(D) 1 pointer (setting parent->left or parent->right to NULL)
Correct Answer: (D)
[EN] Only the single child pointer from the parent pointing to that leaf is set to NULL.
[HI] पेरेंट का केवल वही एक पॉइंटर (left या right) NULL करना होता है जो उस पत्ती की ओर इशारा कर रहा था।
Q14. Which statement is NOT true about BST Insertion and Deletion?
(BST में इंसर्शन और डिलीशन के बारे में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Deleting a node with 1 child promotes that single child upward
(B) Every standard BST insertion adds a new leaf node
(C) In a balanced BST, both insertion and deletion run in O(log n) time
(D) Deleting a node with 2 children requires picking the minimum node of the left subtree as replacement
Correct Answer: (D)
[EN] Replacement from the left subtree must be the MAXIMUM node of the left subtree (Inorder Predecessor), NOT the minimum!
[HI] लेफ्ट सबट्री से विकल्प चुनना हो तो सबसे बड़ा (अधिकतम / Predecessor) नोड चुना जाता है, सबसे छोटा नहीं!
Q15. In the recursive `Node* insertBST(Node* root, int key)` implementation, what does the base case `if (root == NULL)` return?
(रिकर्सिव `insertBST(root, key)` फ़ंक्शन में बेस केस `if (root == NULL)` क्या लौटाता है?)
(A) NULL always
(B) A pointer to a newly allocated leaf node containing `key` with left = right = NULL
(C) The root of the entire tree
(D) An integer error code -1
Correct Answer: (B)
[EN] Returning the newly created node allows the parent's recursive call `root->left = insertBST(...)` to link it cleanly.
[HI] नया बनाया गया नोड लौटाने से पेरेंट का `root->left = insertBST(...)` लिंक अपने आप जुड़ जाता है।
Q16. If you insert keys 25, 15, 35, 10, 20, 30, 40 into an empty BST and delete leaf 10, which traversal of the tree gives [15, 20, 25, 30, 35, 40]?
(खाली BST में 25, 15, 35, 10, 20, 30, 40 डालकर पत्ती 10 को डिलीट करने पर कौन सा ट्रैवर्सल [15, 20, 25, 30, 35, 40] देगा?)
(A) Level Order Traversal
(B) Postorder Traversal
(C) Preorder Traversal
(D) Inorder Traversal
Correct Answer: (D)
[EN] BST deletion always preserves the BST ordering property, so Inorder Traversal continues to yield remaining keys sorted ascending.
[HI] डिलीशन के बाद भी ट्री एक वैध BST बना रहता है, अतः इसका इनऑर्डर ट्रैवर्सल शेष कुंजियों को सॉर्टेड क्रम में ही देगा।
Q17. Within BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases, which bst operation / case directly maps to: "Follow search path to NULL and attach new leaf"?
(BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases में कौन सा BST Operation / Case सीधे "Follow search path to NULL and attach new leaf" से संबंधित है?)
(A) Delete: 0 Children (Leaf)
(B) Delete: 1 Child
(C) BST Insertion
(D) Delete: 2 Children
Correct Answer: (C)
[EN] In BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases, 'BST Insertion' handles 'Follow search path to NULL and attach new leaf' (Always inserts at a leaf in O(h) time).
[HI] BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases में 'BST Insertion' का कार्य/विवरण 'Follow search path to NULL and attach new leaf' (Always inserts at a leaf in O(h) time) है।
Q18. Which option accurately describes 'Delete: 0 Children (Leaf)' in BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases?
(BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases के संदर्भ में 'Delete: 0 Children (Leaf)' की सही विशेषता कौन सी है?)
(A) Set parent link to NULL and free node
(B) Follow search path to NULL and attach new leaf
(C) Bypass node; link parent directly to single child
(D) Copy Inorder Successor or Predecessor, then delete it
Correct Answer: (A)
[EN] 'Delete: 0 Children (Leaf)' provides 'Set parent link to NULL and free node' — key point: Simplest case; zero subtree adjustment needed.
[HI] 'Delete: 0 Children (Leaf)' का मुख्य विवरण 'Set parent link to NULL and free node' है (Simplest case; zero subtree adjustment needed)।
Q19. In BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases, identify the correct parameter for the specification: "Bypass node; link parent directly to single child".
(BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases में "Bypass node; link parent directly to single child" विवरण किस विकल्प के लिए सही है?)
(A) Delete: 2 Children
(B) BST Insertion
(C) Delete: 0 Children (Leaf)
(D) Delete: 1 Child
Correct Answer: (D)
[EN] 'Delete: 1 Child' corresponds to 'Bypass node; link parent directly to single child' (Promotes entire child subtree upward intact).
[HI] 'Delete: 1 Child' का संबंध 'Bypass node; link parent directly to single child' (Promotes entire child subtree upward intact) से है।
Q20. Considering BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases, what key behavior defines 'Delete: 2 Children'?
(BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases में 'Delete: 2 Children' की मुख्य भूमिका या मान क्या है?)
(A) Follow search path to NULL and attach new leaf
(B) Bypass node; link parent directly to single child
(C) Copy Inorder Successor or Predecessor, then delete it
(D) Set parent link to NULL and free node
Correct Answer: (C)
[EN] 'Delete: 2 Children' represents 'Copy Inorder Successor or Predecessor, then delete it' (Substitute node always has <= 1 child).
[HI] 'Delete: 2 Children' का अर्थ/मान 'Copy Inorder Successor or Predecessor, then delete it' है (Substitute node always has <= 1 child)।
BST Insertion and Deletion: 0 Child, 1 Child, 2 Children Cases — Exam FAQs
Q1: Between Inorder Successor and Inorder Predecessor, which one should I use in exams when deleting a 2-child node?
2 चाइल्ड वाले नोड को डिलीट करते समय परीक्षा में इनऑर्डर सक्सेसर और प्रीडीसेसर में से किसे चुनें?
[EN] Both are mathematically valid and preserve BST order! If the exam question does not specify which convention to follow, check whether the answer options match the Inorder Successor (standard in CLRS and most competitive exams) or Inorder Predecessor.
[HI] दोनों ही पूर्णतः सही हैं और BST नियम बनाए रखते हैं। यदि प्रश्न में कुछ न लिखा हो, तो पहले मानक CLRS नियम (इनऑर्डर सक्सेसर) जांचें या विकल्पों के अनुसार मिलान करें।
Q2: Why doesn't standard BST insertion insert new keys in the middle of the tree?
मानक BST में नया मान कभी बीच के स्तरों में क्यों नहीं जोड़ा जाता?
[EN] Because inserting at a leaf requires changing only one NULL pointer in O(h) time without restructuring existing parent-child subtrees. (Only self-balancing or randomized trees rebalance internal links afterward.)
[HI] पत्ती पर जोड़ने से केवल एक NULL पॉइंटर बदलना पड़ता है और पूरा ट्री पुनः व्यवस्थित नहीं करना पड़ता (यह केवल AVL/रेड-ब्लैक में रोटेशन से होता है)।
Q3: What if a BST deletion receives a key that does NOT exist in the tree?
यदि BST डिलीशन को ऐसी कुंजी दी जाए जो ट्री में मौजूद ही न हो तो क्या होता है?
[EN] The recursive or iterative search reaches a NULL child pointer without finding a match, performs no deallocation, and safely returns the tree unmodified in O(h) time.
[HI] सर्च NULL पॉइंटर तक पहुंचकर बिना किसी बदलाव के सुरक्षित रूप से लौट आती है और ट्री वैसा ही बना रहता है।
Post a Comment
Post a Comment