Hello दोस्तों! आज मैं आपको इस पोस्ट में Basic Operations on Binary Search Tree क्या है? के बारें में बताऊंगा, और Binary search tree मे operations को perform करना पढेंगे…
तो चलिए शुरू करते हैं:-
Binary Search Tree
- Binary search tree एक विशेष प्रकार का binary tree है जो Class के रूप में परिभाषित किया जा सकता है. जिसमें Nodes को एक विशिष्ट क्रम में व्यवस्थित किया जाता है.
- left sub tree की सारी information root से छोटी है और right sub tree की सारी information root से बड़ी है.
- right sub – tree में सभी नोड्स की value, root की value से अधिक या बराबर है।
- left और right दोनों ही sub binary search tree है.
Binary search tree मे निम्न operation को perform करना होता है ।
(1) Insertion
(2) Deletion
(3) Traversal
Link list द्वारा जब representation किया जाता है तो node के तीन भाग होते है
(1) Left (2) Info (3) Right
इसके लिए निम्न structure को बनाया जाएगा ।
{
struct node * left;
int info;
struct node * right;
};
-
Binary search tree मे node को जोड़ना ( Insertion )
इसके लिए सबसे पहले एक Temprary variable T को root पर और एक variable Prev को NULL पर भेज देते है ।
Prev Variable T से पहले वाली node को प्रदर्शित करेगा अब एक नये node को memory allocate करेंगे।
उसके information part मे data तथा left और right मे NULL value insert करेंगे।
इसके बाद loop के द्वारा Prev को T पर भेजा जाएगा और यह check किया जाएगा की क्या data की value T की value से छोटी है ।
यदि data की value T से छोटी है तो उसे T के left मे insert कर दिया जाएगा
यदि data की value T से बड़ी है तो उसे T के right मे insert किया जाएगा ।
अब यह check करेंगे की previous variable जो T के पिछली node को प्रदर्शित कर रहा है ।
NULL तो नहीं है । यदि NULL है अतः tree खाली है । तो नये node को root बना देंगे।
Step1:- एक temporary pointer लेंगे जिसमे root का address डालेंगे।
struct node * t = root Step 2: - struct node * prev = NULL Step 3: - struct node * n = malloc (sizeof (struct node)) Step 4: - n -> info = data n ->left = NULL n -> right = NULL Step 5: - while (t != NULL and data != t -> info) set prev = t check whether (data < t -> info) if yes then t = t ->left else t = t -> right Step 6: - check whether (data = t -> info) if yes then return Step 7: - check whether (prev = NULL) if yes then root = n return Step 8: - check whether (data < prev -> info) if yes then prev ->left = n else prev-> right = n Step 9: - Exit
निम्न number को यदि binary tree मे insert करना हो तो उसके लिए निम्न steps follow करेंगे।
Example:-
12, 15, 18 10, 11, 14, 22
i. सबसे पहले 12 को add करना है । चूंकि अभी तक कोई node add नहीं हुई है
इसीलिए यह साधारण रूप से add हो जाएगी।
ii. इसके बाद 15 को add कराना है । चूंकि 15, 12 से बड़ा है
इसलिए 15,12 के दाई ओर add होगा ।
iii. 18 को add करते हुए हमने पाया कि 18, 12 से बड़ा है परन्तु चूंकि 12 के दाईं ओर 15 पहले से ही है
इसीलिए हम इसकी 15 से भी तुलना करेंगे। तुलना करने पर हमने पाया कि 18, 15 से भी बड़ा है।
इसीलिए 18, 12 के भी दाईं ओर Add होगा।
iv. 10 को add करते हुए हमने पाया कि 10, 12 से छोटा है,
इसीलिए 10, 12 के बाईं ओर add होगा।
v. 11 को add करते हुए हमने पाया कि 11, 12 से तो छोटा है,
इसीलिए 12 के बाईं ओर add होगा परन्तु 12 के बाईं ओर पहले से सुरक्षित सूचना 10 से बड़ा है,
इसीलिए 11, 12 के बाईं ओर परन्तु 10 के दाईं ओर add होगा।
vi. 14 को add करते हुए हमने पाया कि 14, 12 से बड़ा है इसिलये यह 12 के दाईं ओर add होगा। परन्तु यहां पर पहले से ही 18 सुरक्षित है। इसलिये हमने 14 की तुलना 15 से की और पाया कि 14, 15 से छोटा है इसीलिये 14, 12 के दाईं ओर परन्तु 15 के बाईं ओर add होगा।
vii. अब हमें अन्तिम सूचना अर्थात् 22 को add करना है। 22 को add करते हुए हमने देखा कि 22,12 से बड़ा है,
इसलिये 22, 12 के दाईं ओर add होगा।
परन्तु 12 के दाईं ओर पहले से 15 सरुक्षित है,
इसलिये हमने इसकी तुलना 15 से की और पाया 22, 15 से भी बड़ा है।
इसलिये 22,15 के भी दाईं ओर जाएगा,
परन्तु 15 के दाईं ओर 18 सुरक्षित है,
अतः 22 की तुलना 18 से भी की और पाया कि 2, 18 से भी बड़ा है,
इसलिये 22, 18 के दाईं ओर add होगा। अतः हम कह सकते हैं
कि 22, 15 के दाईं ओर सुरक्षित 18 के दाईं ओर add होगा।
2. ( Deletion )
Delete a Node from Binary Tree (Binary search tree मे node को delete करना )
i. 15 को Delete करते हुए हमने पाया कि 15 के left और right child दोनों भरे हुए हैं,
इसलिये हमने अपनी Algorithm के अनुसार इसका Inorder (14, 15, 18) निकाला और पाया कि 18 इसका Inorder successor हैं
इसलिये 15 को delete करके 18 को Promote कर दिया। अतः अब Tree निम्नानुसार रह जाता है
ii. 10 को Delete करते हुए हमने पाया कि 10 का केवल right child ही है,
इसलिये हमने इसके child को promote करके 10 को delete कर दिया।
अतः अब tree निम्नानुसार रह जाता है –
3. Traversal of Binary Tree
Binary Tree को Traverse करना सबसे Important Operation हैं।
Binary Tree पर बहुत सारे Operations Perform किये जाते हैं।
Traversing करना tree के हर Node पर होता हैं। Traversing एक Process हैं।
जिसमें Tree के हर Nodes से गुजरना होता हैं। किसी भी Tree को Traverse करने के लिए सबसे पहले उसके root को check किया जाता हैं।
इसके बाद left Sub Tree को Traverse करते हैं तथा अन्त में Right sub tree को traverse करते हैं।
Normally Binary Tree के Traversal 3 प्रकार के होते हैं।
i.) In order Traversal: – (Left, Root, Right)
- सबसे पहले Left Sub Tree को Traverse करो.
- Root को traverse करो
- Left मे right sub tree को traverse करो ।
ii.) Pre Order Traversal: – (Root, Left, Right)
- Root को traverse करो
- Left sub tree को traverse करो।
- Left मे right sub tree को traverse करो ।
iii.) Post Order Traversal: – (Left, Right, Root)
- Left sub tree को traverse करो।
- Right sub tree को traverse करो
- Root को traversal करो
उपरोक्त Tree में यदि तीनों प्रकार कर Traversal करना हो तो इसके लिए Tree को Root से Access किया जाएगा।
i.) In Order Traversal of Tree: – (Left, Root, Right)
सबसे पहले Root Node A पर जाऐंगे। अब देखेंगे कि root का Left Full है
अतः A के left में B हैं।
अब B के left को check करेंगे B का left भी full हैं।
इसके left में D हैं। पर D का left खाली हैं
अतः यहां से Left Root और right को traverse करेंगे। D का Left खाली हैं
अतः D और G(Root, Right) को Traverse करेंगे।
1 इस Tree का In order Traversal D और G होगा।
2 D खुद B का left हैं अतः अब Root को लिखेंगे
D G B
3 B का right E हैं तथा E का left हैं अतः EH वाले tree के अन्र्तगत Traversal HE होग अतः Tree
D G B H E
4 Left sub Tree complete हो चुका हैं अब root को लिखेंगे
D G B H E A
5 अब Right Sub Tree को Access करेंगे। F का Left NULL है तथा Right में I हैं। L, Root, R के आधार पर Traversal FI होगी।
D G B H E A F I
6 F का root C में और C का Right NULL हैं। अतः Traversal होगी
D G B H E A F I C
ii.) Pre Order Traversal: – (Root, Left, Right)
सबसे पहले root node A पर जाएंगे । अब देखेंगे की root का left full है
अतः A के left मे B है अब B के left को check करेंगे B का left भी full है ।
इसके left मे D है पर D का left खाली है अतः यहाँ से root, left और right को traverse करेंगे ।
- सबसे पहले root को देंगे tree का root A है अतः tree traversal मे first element A है
A
- A के left sub tree को check करेंगे A के left मे B अतःtree traversal
A, B
- B का left D है और G का root D है अतः tree traversal
A B D
- D का left NULL है और right मे G है अतः root left-right के आधार पर tree traversal
A B D G
- B के right मे E है और E H का root है अतः root left-right के आधार पर tree traversal
A B D G E H
- अब right sub tree को traverse करेंगे A का right C है अतः tree traversal
A B D G E H C F I
- C के left मे F है तथा FI का root है अतः traversal
A B D G E H C F I
iii.) Post Order Traversal: – (Left, Right और Root)
सबसे पहले root node A पर जाएंगे । अब देखेंगे की root का left full है
अतः A के left मे B है अब B के left को check करेंगे B का left भी full है इसके left मे D है
पर D का left खाली है ।अतः यहां से left , right, root को traverse करेंगे ।
- A का left B है B का left D है और D का left NULL है पर D का right G है अतः left right root के आधार पर traversal
G D
- B का left sub tree complete है और B के right sub tree पर जयेंगे। B के right पर E है और E के left मे H traversal
G D H E B
- A का left sub tree traverse हो चुका है अब A के right sub tree को traverse करेंगे ।
- A के right मे C है C केआर left मे F है तथा F का right I है अतः पहले IF को लेंगे
G D H E B F I
- C का left sub tree complete traverse हो चुका है अतः अब right sub tree NULL है
G D H E B F I C
- सबसे अंत मे root node को लिखा जायेगा।
G D H E B F I C
निवेदन:-
अगर आपके लिए यह आर्टिकल useful रहा हो तो इसे अपने दोस्तों और classmates के साथ अवश्य share कीजिये,
और या अन्य विषयों से related कोई question हो तो नीचे कमेंट के द्वारा बताइए. thanks.
इसे भी देखे:
Hello दोस्तों! नीचे दिए गए links पर click करके आपको हम इस पोस्ट में (Computer Online Test) की Practice कराएंगे जिससे आप अपने CCC, O level , कम्प्युटर GK की practice कर सकते है.
इस post के द्वारा आप अपनी कम्प्युटर की नॉलेज बड़ सकते है.
उसके साथ ही साथ आप अपने कई प्रकार के पेपरो की भी तैयरी भी कर सकते है.
जैसे की CCC, O level , कम्प्युटर GK की practice कर सकते है,