BST insertion, deletion और height costs
उद्देश्य और tree contract
BST search से आगे insertion, deletion, successor replacement तथा height-dependent cost सीखें। यह ordinary unbalanced BST है, keys distinct हैं। Duplicate insertion reject होगी और tree unchanged रहेगा; duplicate को चुपचाप left/right नहीं भेजते। हर node की पूरी left subtree में छोटे और पूरी right subtree में बड़े keys हैं। Comparison total order है। Nodes में key तथा child links हैं; record payload हो तो key copy के साथ उसका associated data भी consistent रखना होगा।
Height h, longest root-to-leaf path के edges हैं। Empty tree h=−1, leaf h=0। Balancing rotations नहीं। हर structural change के बाद subtree root return/update करें ताकि overall root भी सामान्य logic से संभले। Allocation failure में insertion का पुराना tree unchanged है।
1. Search path से insertion
Root से key compare करें। Equality पर duplicate reject; छोटा हो तो left, बड़ा हो तो right। पहला absent child नया leaf लेने का स्थान है। Empty tree में leaf ही root। Recursive insert नया subtree root return करता है; caller root=insert(root,key) या parent.child=insert(parent.child,key) assign करे। Returned root ignore करने पर empty-tree insertion और कुछ deletions टूटते हैं।
Sequence 40,20,60,10,30,50,70,25 डालें। Root 40; बच्चे 20,60। 20 के बच्चे 10,30; 30 का left 25। 60 के बच्चे 50,70। Path 40→20→30→25 से height 3। फिर 30 डालने पर existing 30 पर equality होगी: count 8 और shape unchanged। 55 डालें तो 40→60→50 path से 50.right नया leaf; count 9, height अभी 3।
Insertion “sorted append” नहीं; input order shape तय करता है। 1,2,3,4,5 क्रम में डालने पर केवल right-child chain और height 4। इसी key set के छोटे-height BST का inorder भी वही sorted sequence होगा।
2. Zero/one-child deletion
पहले key खोजें। Absent हो तो subtree unchanged return करें। Leaf को absent link से replace कर release करें। One-child node को उसके child से replace करें: parent link या overall root अब child बताता है। Release से पहले replacement link बचाएँ। पूरा child subtree जोड़ना है, केवल उसका key नहीं।
Root 8 के केवल left subtree का root 3 हो तो 8 delete करने पर 3 नया root बनेगा और उसके सभी descendants बचेंगे। Singleton 8 delete करने पर empty tree। इसलिए deletion को replacement subtree root बताना जरूरी है। Parent pointer अनिवार्य नहीं: recursive return या incoming root/child link का pointer भी update कर सकता है।
3. Two children: successor key, फिर successor node
दो children वाले target का inorder successor उसकी right subtree का minimum है। Right child से शुरू करके जितना संभव left जाएँ। Successor का left child नहीं होता, लेकिन right child हो सकता है। Target में successor key तथा आवश्यक associated payload copy करें। फिर right subtree में successor को zero/one-child case से हटाएँ। केवल एक physical node release और count एक कम होगा।
Order क्यों बचता है? पुरानी left subtree का हर key old target से छोटा, इसलिए successor से भी छोटा। Successor पुरानी right subtree का minimum था; उसका unique occurrence हटने पर शेष सभी right keys उससे बड़े हैं। Distinct keys और एक successor removal से strict inequalities फिर मिलती हैं। Copy करके पुराना occurrence छोड़ने से duplicate बनता है। Immediate right child को हमेशा successor मानना गलत है।
Fresh tree में 40,20,60,10,30,50,70,45,55 insert करें और root 40 हटाएँ। Successor 45 है, path 60→50→45। Root key 45 करें और पुराना leaf 45, 50.left से हटाएँ। Root physical object वही, key नया। Left 20 के बच्चे 10,30; right 60 के बच्चे 50,70; 50.right=55। Inorder 10,20,30,45,50,55,60,70। नौ के बजाय आठ nodes।
Successor के child का उदाहरण: root 20,left=10,right=40; 40.left=30 और 30.right=35। 20 हटाएँ: root key 30 करें, पुराने successor 30 की जगह उसका right child लगाएँ, इसलिए 40.left=35। 35 छोड़ देना subtree loss है। Successor immediate right child हो तो copy के बाद उसका right child target का नया right child बनता है।
4. Identity, cost और shape bounds
Copy-key deletion में target physical node का logical key बदलता है। उसके external pointers live object बताते हैं, लेकिन नया key देखते हैं। Removed successor के pointers invalid हैं। Transplant-based implementation में identity contract अलग है। Final key set समान होने पर भी दोनों के pointer निष्कर्ष न मिलाएँ।
Current height h वाले tree में search/insert/delete का worst-case समय O(h+1) है। Successor खोज root-to-leaf स्तर के path में है; deletion O(nh) नहीं बनता। बिना explicit path stack वाले iterative variants का auxiliary space O(1); recursive versions का call stack O(h+1)। Allocator cost अलग है। n-node BST की height n−1 तक हो सकती है, इसलिए operations worst-case O(n)। n≥1 के लिए minimum possible height ceil(log2(n+1))−1 है। O(log n) के लिए height guarantee चाहिए, केवल BST नाम पर्याप्त नहीं।
गलतियाँ और अंतिम जाँच
Duplicate तथा height policies पहले लिखें। Root सहित हर removal की incoming link trace करें। Actual right-subtree minimum खोजें, उसका संभव right child reconnect करें और केवल एक node release करें। Count तथा sorted inorder जाँचें, लेकिन structure/identity भी देखें: sorted inorder अकेला intended reachability और pointer ownership की सुरक्षा सिद्ध नहीं करता।
मौलिक अभ्यास: छह single-correct MCQs
ये मौलिक शिक्षण प्रश्न हैं, previous-year questions नहीं। एक विकल्प चुनें।
P01. इस पाठ की reject-duplicates policy में existing 30 फिर insert करने पर:
A. Left duplicate जोड़ता है B. Right duplicate जोड़ता है C. पूरा tree बदलता है D. Tree unchanged
उत्तर: D
A: यह अलग duplicate policy है।
B: यह भी अलग policy है।
C: Duplicate detection tree replacement नहीं।
D: Equality पर नया node बिना insertion रुकता है।
P02. Empty ordinary BST में 1,2,3,4,5 डालें। Edge-height?
A. 2 B. 4 C. 5 D. 0
उत्तर: B
A: बेहतर shape में संभव है, इस order में नहीं।
B: पाँच nodes की chain में चार edges हैं।
C: पाँच path nodes हैं, edges नहीं।
D: केवल leaf tree की height zero है।
P03. Two-child target का inorder successor?
A. Right subtree maximum B. Left subtree root C. Right subtree minimum D. हमेशा immediate right child
उत्तर: C
A: Replacement के बाद छोटे keys right में रह सकते हैं।
B: यह next larger key नहीं।
C: Target से बड़ा सबसे छोटा key है।
D: Right child का छोटा left descendant हो सकता है।
P04. Root 20,left 10,right 40; 40.left=30,30.right=35। 20 की successor-copy deletion के बाद 40.left?
A. 35 B. NULL C. 20 D. 10
उत्तर: A
A: Removed successor का right child उसकी जगह आता है।
B: इससे 35 खो जाएगा।
C: 20 deleted key है।
D: 10 root की left subtree में रहता है।
P05. Ordinary n-node unbalanced BST में operation की worst-case time?
A. हमेशा O(log n) B. O(n) C. हर deletion O(n²) D. हर search O(1)
उत्तर: B
A: Balance guarantee नहीं।
B: Height n−1 chain में linear paths हैं।
C: Path और successor handling quadratic नहीं।
D: Search पूरी chain जा सकता है।
P06. Two-child node की copy-key deletion में सामान्यतः कौन physical node release होता है?
A. Target और successor दोनों B. Target का left child C. कोई नहीं D. Original successor node
उत्तर: D
A: केवल एक key/node हटता है।
B: Left child deletion replacement नहीं।
C: सभी nodes छोड़ने से successor duplicate होगा।
D: Target copied key के साथ बचता है; successor unlink होता है।
स्रोत और दायरा
GATE CS 2026 के मौजूदा आधार-पाठों का सीमित विस्तार। पूरे विषय की पूर्णता का दावा नहीं। उदाहरण और प्रश्न मौलिक हैं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन