Textual description of firstImageUrl

Data Structures in Hindi : BST Deletion

Binary Search Tree - Deletion Operation

  • Introduction to BST deletion operation in Hindi
  • Example of BST deletion operation in Hindi

Introduction to BST Deletion Operation

Binary search tree में deletion सभी operations में सबसे complex operation है। Binary search tree में deletion operation की worst time complexity O(h) होती है।

जब आप deletion operation perform करते है तो उसमे first step लगभग search operation की तरह ही perform किया जाता है। लेकिन इसके बाद 3 possible situations आती है।

  1. जो node आप delete करना चाहते है वह एक leaf node है। 
  2. जो node आप delete करना चाहते है उसके सिर्फ एक ही child node है। 
  3. जो node आप delete करना चाहते है उसके दो child nodes है। 

Insertion operation perform करते समय आप सिर्फ नयी node insert करते है जो हमेशा एक leaf node होती है। Search operation perform करते समय आप आसानी से दूसरी nodes से compare करके एक node को ढूंढते है। लेकिन deletion perform करते समय इन 3 situations को अलग अलग handle करने की आवश्यकता होती है। 

आइये अब देखते है की इन तीनों situations में आप कैसे एक node को delete कर सकते है। 

Deleting a Leaf Node

Binary search tree में एक leaf node को delete करना बहुत आसान होता है। सबसे पहले आप उस सभी node की values से compare करते हुए उस node को find करते है जिसे आप delete करना चाहते है।

इसके बाद जिस भी leaf node को आप delete करना चाहते है simply उसके parent के left या right pointer को NULL assign कर देते है।

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

Binary-search-tree-in-Hindi


ऊपर दिए गए binary search tree में यदि आप node 50 को delete करना चाहते है तो इसके लिए simply आप node 40 के right pointer को NULL assign करते है और node 50 की memory को free कर देते है।

bst-leaf-node-deletion-in-Hindi


Deleting a Node with One Child

इस तरह के deletion में सबसे पहले node को tree से पूरी तरह remove कर दिया जाता है। इसके बाद remove की गयी node के child को और remove की गयी node के parent को आपस में connect कर दिया जाता है। 

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

Binary-search-tree-in-Hindi

इस tree में यदि आप node 23 को delete करना चाहते है तो इसके लिए सबसे पहले आप node 23 की memory free करते है और इसके बाद node 40 के left pointer को node 35 assign कर देते है।

bst-one-child-node-deletion-in-Hindi


Deleting a Node with Two Childs

दो child nodes वाली node को delete करना सबसे complex होता है। जब भी किसी binary search tree में किसी दो child वाली node को delete किया जाता है तो उसके लिए निचे दिए गए steps perform किये जाते है।

  1. जिस node को आप delete करना चाहते है उसके right subtree में सबसे minimum value ढूँढ़िये। 
  2. Delete की जाने वाली node की value को search की गयी minimum value से replace कर दीजिये। 
  3. इसके बाद right subtree में available duplicate node को remove कर दीजिये। 

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

Binary-search-tree-in-Hindi

ऊपर दिए गए binary search tree में यदि आप node 82 को delete करना चाहते है तो इसके लिए सबसे पहले आप उसके right subtree में minimum value वाली node को ढूंढेंगे जो की node 90 है।

इसके बाद आप node 90 की value से node 82 की value को replace कर देंगे और node 90 को remove कर देंगे।

bst-two-child-node-deletion-in-Hindi





      DMCA.com Protection Status

 Leave a comment