Binary Search Tree क्या हैं?
Binary search tree क्या हैं?
Binary Search Tree एक महत्वपूर्ण एवं उपयोगी data structure होता है। इसकी सबसे बड़ी विशेषता यह होती है कि इसमें किसी element को बहुत ही कम समय में efficient तरीके से search किया जा सकता है। साथ ही इसमें elements का insertion और deletion भी बहुत efficient तरीके से होता है।
हम जानते है कि array में किसी element को binary search के प्रयोग से प्रभावशाली तरीके से search किया जा सकता है लेकिन इसमें element का insertion एवं deletion बहुत expensive होता है । इसी प्रकार linked list में element का insertion और deletion तो बहुत efficient तरीके से किया जा सकता है लेकिन इसमें element को search करना बहुत expensive होता है क्योंकि इसमें केवल linear search का ही प्रयोग किया जा सकता है binary search का नहीं। Binary search tree array और linked list में आने वाली इन दोनों समस्याओं को हल करता है।
- Node N का मान इसके left subtree में स्थित सभी nodes के मान से बड़ा होता है।
- Node N का मान इसके right subtree में स्थित सभी nodes के मान से छोटा होता है।
- T में inorder traversal करने पर इसके सभी nodes sorted order में प्राप्त होते हैं।
Searching in Binary Search Tree
- KEY को T के root node N से compare करते है।
- यदि KEY < N होता है N के left child को ओर आगे बढ़ते है।
- यदि KEY > N होता है N के right child को ओर आगे बढ़ते है।
- Step 1 को तब तक करते है जब तक कि निम्नलिखित में कोई एक न मिल जाए-
- यदि हमें ऐसा node N मिलता है जो KEY के बराबर है तो search successful हो जाता है।
- यदि हमें empty subtree मिलता है तो search unsuccessful हो जाता है।
Insertion in Binay Search Tree
- ITEM को T के root node N से compare करते है।
- यदि ITEM < N होता है N के left child की और आगे बढ़ते है।
- यदि ITEM > N होता है N के right child की ओर आगे बढ़ते है।
- Step 1 को तब तक करते है जब तक कि हमें कोई empty subree नहीं मिल जाता है। फिर हम empty subtree के स्थान पर ITEM को insert करते है।
Thank you sir ????
Internet me Aap jaiso ki kami thi sir hamari madad karne ke liye dil se dhanyawad. 🙏