बाइनरी सर्च ट्री

Time complexity in big O notation
Algorithm Average Worst case

चित्र 1: आकार 9 और गहराई 3 का एक बाइनरी सर्च ट्री, जिसकी जड़ 8 है। पत्तियाँ नहीं खींची जाती हैं।

कंप्यूटर विज्ञान में एक बाइनरी सर्च ट्री (बीएसटी) जिसे क्रमांक या सॉर्टेड बाइनरी ट्री भी कहा जाता है एक जड़ वाला पेड़ बाइनरी ट्री डेटा संरचना है जिसमें आंतरिक कुंजी बाएं उप पेंड़ की सभी कुंजियों से अधिक नहीं होती हैं तथा कम होती हैं इसके दाहिने उप पेंड़ की तुलना में बाइनरी सर्च ट्री पर संचालन की समय जटिलता सीधे पेड़ की ऊंचाई के समानुपाती होती है।

बाइनरी सर्च ट्री डेटा आइटम्स को तेजी से देखने जोड़ने और हटाने के लिए बाइनरी सर्च एल्गोरिथम की अनुमति देता है क्योंकि बीएसटी में प्रोप इस तरह रखे गए हैं कि प्रत्येक तुलना शेष पेड़ के आधे हिस्से को छोड़ देती है प्रदर्शन खोजना द्विआधारी लघुगणक के समानुपाती होता है। लेबल किए गए डेटा के कुशल भंडारण की समस्या के लिए 1960 के दशक में बीएसटी तैयार किए गए थे और इसका श्रेय कॉनवे बर्नर्स-ली और डेविडव्हीलर कंप्यूटर के वैज्ञानिक को दिया जाता है।

बाइनरी सर्च ट्री का प्रदर्शन पेड़ में नोड्स के सम्मिलन के क्रम पर निर्भर करता है क्योंकि मनमाना सम्मिलन अर्धपतन का कारण बन सकता है बाइनरी सर्च ट्री के कई रूपों को सबसे खराब स्थिति के प्रदर्शन की गारंटी के साथ बनाया जा सकता है क्योंकि इसमें मूल संचालन में सम्मिलित हैं सबसे खराब स्थिति जटिलता वाले बीएसटी एक अवर्गीकृत सरणी से बेहतर प्रदर्शन करते हैं जिनको रैखिक समय की आवश्यकता होती है।

बीएसटी के कम्प्यूटेशनल जटिलता सिद्धांत से पता चलता है कि अच्छा सबसे खराब और औसत स्थित, डालें, हटायें और खोजें भी सम्मिलित हैं। वे एक एकल लिंक की सूची सम्मिलन और विलोपन के साथ पेड़ की ऊंचाई की असीमित वृद्धि को संबोधित करने के लिए बीएसटी के स्व-संतुलन बाइनरी सर्च ट्री संतुलन रूपों को बाइनरी शुरूआत की सबसे खराब जटिलता को बाध्य करने के लिए पेश किया जाता है। एवीएल पेड़ पहला स्व संतुलन बाइनरी सर्च ट्री था जिसका आविष्कार 1962 में एवीएल एड्स वेल्सकी और ईव्जेनी लैन्डिस द्वारा किया गया था।

बाइनरी सर्च ट्री का उपयोग अमूर्त डेटा प्रकारों जैसे सेट और प्राथमिकता पंक्ति को लागू करने के लिए किया जा सकता है और छँटाई एल्गोरिथ्म जैसे पेड़ की छँटाई में उपयोग किया जाता है।

इतिहास

बाइनरी सर्च ट्री एल्गोरिथम स्वतंत्र रूप से कई शोधकर्ताओं द्वारा खोजा गया था जिसमें पी.एफ. विंडले एंड्रयू डोनाल्ड बूथ एंड्रयू कॉलिन थॉमस एन. हिब्बार्ड तथा एल्गोरिथ्म का श्रेय कॉनवे बर्नर्स-ली और डेविड व्हीलर कंप्यूटर वैज्ञानिक को दिया जाता है जिन्होंने 1960 में चुंबकीय टेप में लेबल किए गए डेटा को संग्रहीत करने के लिए इसका उपयोग किया था। सबसे शुरुआती और लोकप्रिय बाइनरी सर्च ट्री एल्गोरिथम हिब्बार्ड का है।

बाइनरी सर्च ट्री की समय जटिलताएं पेड़ की ऊंचाई के साथ असीम रूप से बढ़ जाती हैं यदि नोड्स को एक मनमाने क्रम में डाला जाता है तो पेंड़ की ऊंचाई को सीमित करने के लिए स्व-संतुलन बाइनरी सर्च पेंड़ पेश किए गए थे पेड़ की ऊंचाई को सीमित करने के लिए विभिन्न ऊंचाई-संतुलित द्विआधारी खोज पेड़ पेश किए गए जैसे एवीएल पेड़ ट्रीप और लाल-काले पेड़ एवीएल पेड़ का आविष्कार जॉर्जी एडेल्सन वेलेस्की और ईव्जेनी लैन्ड्स द्वारा 1962 में सूचना के कुशल संगठन के लिए किया गया था। यह आविष्कार किया जाने वाला पहला स्व-संतुलन बाइनरी खोजक पेड़ था।

सिंहावलोकन

एक द्विआधारी खोज ट्री एक रूटेड बाइनरी ट्री है जिसमें नोड्स को कुल क्रम में व्यवस्थित किया जाता है#सख्त और गैर-सख्त कुल ऑर्डर जिसमें किसी विशेष नोड से अधिक कुंजियों वाले नोड्स को सही ट्री (डेटा संरचना)#शब्दावली| उप-वृक्ष और बराबर या उससे कम वाले बायीं उप-वृक्ष पर संग्रहीत होते हैं जो बाइनरी खोज संपत्ति को संतुष्ट करते हैं।

एल्गोरिदम और खोज एल्गोरिदम को सॉर्ट करने में बाइनरी सर्च ट्री भी प्रभावशाली हैं। (इस प्रकार, कार्यान्वित आदेश संबंध को सख्त और पहचान करने की आवश्यकता नहीं है ताकि डुप्लिकेट पेड़ में हो सकता है, यानी एक ही कुंजी के साथ एक से अधिक आइटम।) हालांकि, बीएसटी की खोज जटिलता उस क्रम पर निर्भर करती है जिसमें नोड्स डाले और हटाए जाते हैं; चूंकि सबसे खराब स्थिति में, बाइनरी सर्च ट्री में क्रमिक संचालन अध: पतन का कारण बन सकता है और संरचना की तरह एक एकल लिंक्ड सूची (या असंतुलित पेड़) बना सकता है, इस प्रकार एक लिंक की गई सूची के रूप में सबसे खराब स्थिति वाली जटिलता है।

बाइनरी सर्च ट्री भी एक मूलभूत डेटा संरचना है जिसका उपयोग अमूर्त डेटा संरचनाओं जैसे सेट, सेट (कंप्यूटर साइंस) #Multiset, और साहचर्य सरणियों के निर्माण में किया जाता है।

संचालन

खोजना

एक विशिष्ट कुंजी के लिए बाइनरी सर्च ट्री में खोज को क्रमादेशित पुनरावर्तन (कंप्यूटर विज्ञान) या पुनरावृत्ति#कंप्यूटिंग किया जा सकता है।

वृक्ष (डेटा संरचना)#रूट नोड्स की जांच से खोज शुरू होती है। अगर पेड़ नल पॉइंटर है |nil, खोजी जा रही कुंजी ट्री में मौजूद नहीं है। अन्यथा, यदि कुंजी रूट के बराबर है, तो खोज सफल होती है और नोड वापस आ जाता है। यदि कुंजी रूट से कम है, तो खोज बाएँ सबट्री की जाँच करके आगे बढ़ती है। इसी तरह, यदि कुंजी रूट से अधिक है, तो खोज सही सबट्री की जांच करके आगे बढ़ती है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कुंजी नहीं मिल जाती या शेष सबट्री नहीं मिल जाती ${\text{nil}}$. यदि खोजी गई कुंजी a के बाद नहीं मिलती है ${\text{nil}}$ सबट्री तक पहुँच जाता है, तो कुंजी ट्री में मौजूद नहीं है।

पुनरावर्ती खोज

निम्नलिखित स्यूडोकोड पुनरावर्तन (कंप्यूटर विज्ञान) के माध्यम से BST खोज प्रक्रिया को लागू करता है।

Recursive-Tree-Search(x, key) if x = NIL or key = x.key then return x if key < x.key then return Recursive-Tree-Search(x.left, key) else return Recursive-Tree-Search(x.right, key) end if

पुनरावर्ती प्रक्रिया एक तक जारी रहती है ${\text{nil}}$ या ${\text{key}}$ तलाश की जा रही है।

पुनरावृत्त खोज

खोज के पुनरावर्ती संस्करण को थोड़ी देर के लूप में अनियंत्रित किया जा सकता है। अधिकांश मशीनों पर, पुनरावृत्त संस्करण अधिक कंप्यूटर प्रदर्शन वाला पाया जाता है।

Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key then if key < x.key then x := x.left else x := x.right end if repeat return x

चूँकि खोज कुछ लसीका नोड तक आगे बढ़ सकती है, BST खोज की रनिंग टाइम जटिलता है $O(h)$ कहाँ $h$ वृक्ष है (डेटा संरचना)#शब्दावली। हालाँकि, BST खोज के लिए सबसे खराब स्थिति है $O(n)$ कहाँ $n$ बीएसटी में नोड्स की कुल संख्या है, क्योंकि एक असंतुलित बीएसटी एक लिंक्ड सूची में खराब हो सकता है। हालाँकि, यदि BST ऊँचाई-संतुलित वृक्ष है | ऊँचाई-संतुलित ऊँचाई है $O(\log n)$.

उत्तराधिकारी और पूर्ववर्ती

कुछ कार्यों के लिए, एक नोड दिया गया ${\text{x}}$, के उत्तराधिकारी या पूर्ववर्ती का पता लगाना ${\text{x}}$ अत्यंत महत्वपूर्ण है। यह मानते हुए कि BST की सभी कुंजियाँ अलग-अलग हैं, एक नोड की उत्तराधिकारी हैं ${\text{x}}$ बीएसटी में सबसे छोटी कुंजी वाला नोड है ${\text{x}}$की चाबी। दूसरी ओर, एक नोड के पूर्ववर्ती ${\text{x}}$ BST में सबसे बड़ी कुंजी से छोटा नोड है ${\text{x}}$की चाबी। नोड के उत्तराधिकारी और पूर्ववर्ती को खोजने के लिए निम्नलिखित स्यूडोकोड है ${\text{x}}$ बीएसटी में।

BST-Successor(x) if x.right ≠ NIL then return BST-Minimum(x.right) end if y := x.parent while y ≠ NIL and x = y.right then x := y y := y.parent repeat return y

BST-Predecessor(x) if x.left ≠ NIL then return BST-Maximum(x.left) end if y := x.parent while y ≠ NIL and x = y.left then x := y y := y.parent repeat return y

बीएसटी में एक नोड खोजने जैसे संचालन, जिसकी कुंजी अधिकतम या न्यूनतम है, कुछ कार्यों में महत्वपूर्ण हैं, जैसे कि उत्तराधिकारी और नोड्स के पूर्ववर्ती का निर्धारण करना। संचालन के लिए स्यूडोकोड निम्नलिखित है।

BST-Maximum(x) while x.right ≠ NIL then x := x.right repeat return x

BST-Minimum(x) while x.left ≠ NIL then x := x.left repeat return x

प्रविष्टि

सम्मिलन और विलोपन जैसे संचालन BST प्रतिनिधित्व को गतिशील रूप से बदलने का कारण बनते हैं। डेटा संरचना को इस तरह से संशोधित किया जाना चाहिए कि BST के गुण बने रहें। बीएसटी में पत्ती के नोड्स के रूप में नए नोड डाले गए हैं। सम्मिलन ऑपरेशन का पुनरावृत्त कार्यान्वयन निम्नलिखित है।

1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 while x ≠ NIL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NIL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if

प्रक्रिया अनुगामी सूचक को बनाए रखती है ${\text{y}}$ के माता पिता के रूप में ${\text{x}}$. लाइन 2 पर इनिशियलाइज़ेशन के बाद, जबकि लूप 4-11 लाइनों के साथ पॉइंटर्स को अपडेट करने का कारण बनता है। अगर ${\text{y}}$ है ${\text{nil}}$, बीएसटी खाली है, इस प्रकार ${\text{z}}$ बाइनरी सर्च ट्री के रूट नोड के रूप में डाला गया है ${\text{T}}$, यदि यह नहीं है ${\text{nil}}$, प्रविष्टि कुंजियों की तुलना करके आगे बढ़ती है ${\text{y}}$ 15-19 की तर्ज पर और उसके अनुसार नोड डाला जाता है।

हटाना

एक नोड का विलोपन, कहते हैं ${\mathsf {D}}$, एक बाइनरी सर्च ट्री से ${\mathsf {BST}}$ तीन मामलों का पालन करना चाहिए:

1. अगर ${\mathsf {D}}$ एक लीफ नोड है, जो पैरेंट नोड का पॉइंटर है ${\mathsf {D}}$ से प्रतिस्थापित हो जाता है ${\mathsf {NIL}}$ और इसके परिणामस्वरूप ${\mathsf {D}}$ पेड़ से हटा दिया जाता है।
2. अगर ${\mathsf {D}}$ एक एकल चाइल्ड नोड है, तो बच्चा या तो बाएँ या दाएँ बच्चे के रूप में उन्नत हो जाता है ${\mathsf {D}}$′s माता-पिता की स्थिति के आधार पर ${\mathsf {D}}$ बीएसटी के भीतर, जैसा कि अंजीर में दिखाया गया है। 2 भाग (ए) और भाग (बी), और परिणामस्वरूप, ${\mathsf {D}}$ पेड़ से हटा दिया जाता है।
3. अगर ${\mathsf {D}}$ का उत्तराधिकारी एक बाएँ और दाएँ दोनों बच्चे हैं ${\mathsf {D}}$ (जाने भी दो ${\mathsf {E}}$ जिसके पास कोई बच्चा नहीं है)) की स्थिति लेता है ${\mathsf {D}}$ वृक्ष में। यह की स्थिति पर निर्भर करता है ${\mathsf {E}}$ अंदर ${\mathsf {BST}}$:
   1. अगर ${\mathsf {E}}$ है ${\mathsf {D}}$′s तत्काल दायां बच्चा, ${\mathsf {E}}$ ऊंचा हो जाता है और ${\mathsf {E}}$के लेफ्ट चाइल्ड पॉइंटर को पॉइंट किया जाता है ${\mathsf {D}}$′s प्रारंभिक बाएँ उप-वृक्ष, जैसा कि चित्र में दिखाया गया है। 2 भाग (सी)।
   2. अगर ${\mathsf {E}}$ की तत्काल सही संतान नहीं है ${\mathsf {D}}$, विलोपन की स्थिति को बदलकर आगे बढ़ता है ${\mathsf {E}}$ द्वारा ${\mathsf {E}}$′s सही बच्चा (यहाँ ${\mathsf {F}}$), और ${\mathsf {E}}$ का स्थान लेता है ${\mathsf {D}}$ में ${\mathsf {BST}}$, जैसा कि यहां दिखाया गया है।

निम्नलिखित स्यूडोकोड बाइनरी सर्च ट्री में विलोपन ऑपरेशन को लागू करता है।

1 BST_Delete(BST, D) 2 if D.left = NIL then 3 Shift_Nodes(BST, D, D.right) 4 else if D.right = NIL then 5 Shift_Nodes(BST, D, D.left) 6 else 7 E := Tree_Successor(D) 8 if E.parent ≠ D then 9 Shift_Nodes(BST, E, E.right) 10 E.right := D.right 11 E.right.parent := E 12 end if 13 Shift_Nodes(BST, D, E) 14 E.left := D.left 15 E.left.parent := E 16 end if

1 Shift_Nodes(BST, u, v) 2 if u.parent = NIL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 5 else 6 u.parent.right := v 7 end if 8 if v ≠ NIL then 9 v.parent := u.parent 10 end if

${\mathsf {Tree\_Delete}}$ h> प्रक्रिया ऊपर उल्लिखित 3 विशेष मामलों से संबंधित है। पंक्तियाँ 2-3 केस 1 से संबंधित हैं; पंक्ति 4-5 स्थिति 2 से संबंधित है और पंक्ति 6-16 स्थिति 3 के लिए है। सहायक कार्य ${\mathsf {Shift\_Nodes}}$ नोड को बदलने के उद्देश्य से विलोपन एल्गोरिथ्म के भीतर उपयोग किया जाता है ${\mathsf {u}}$ साथ ${\mathsf {v}}$ बाइनरी सर्च ट्री में ${\mathsf {BST}}$. यह प्रक्रिया हटाने (और प्रतिस्थापन) को संभालती है ${\mathsf {u}}$ से ${\mathsf {BST}}$.

ट्रैवर्सल

Main article: Tree traversal

See also: Threaded binary tree

एक BST तीन बुनियादी एल्गोरिदम के माध्यम से ट्री ट्रैवर्सल हो सकता है: इनऑर्डर ट्रैवर्सल, प्री-ऑर्डर ट्रैवर्सल और पोस्ट-ऑर्डर ट्रैवर्सल ट्री वॉक।

• इनऑर्डर ट्री वॉक: बाएं सबट्री से नोड्स पहले देखे जाते हैं, उसके बाद रूट नोड और राइट सबट्री।
• प्रीऑर्डर ट्री वॉक: रूट नोड को पहले विज़िट किया जाता है, उसके बाद बाएँ और दाएँ सबट्री को देखा जाता है।
• पोस्टऑर्डर ट्री वॉक: बाएं सबट्री से नोड्स पहले देखे जाते हैं, उसके बाद राइट सबट्री और अंत में रूट।

ट्री वॉक का पुनरावर्ती कार्यान्वयन निम्नलिखित है।

Inorder-Tree-Walk(x) if x ≠ NIL then Inorder-Tree-Walk(x.left) visit node Inorder-Tree-Walk(x.right) end if

Preorder-Tree-Walk(x) if x ≠ NIL then visit node Preorder-Tree-Walk(x.left) Preorder-Tree-Walk(x.right) end if

Postorder-Tree-Walk(x) if x ≠ NIL then Postorder-Tree-Walk(x.left) Postorder-Tree-Walk(x.right) visit node end if

संतुलित बाइनरी सर्च ट्री

Main article: Self-balancing binary search tree

पुनर्संतुलन के बिना, बाइनरी सर्च ट्री में सम्मिलन या विलोपन अध: पतन का कारण बन सकता है, जिसके परिणामस्वरूप ऊँचाई होती है $n$ पेड़ की (जहां $n$ एक पेड़ में वस्तुओं की संख्या है), ताकि लुकअप प्रदर्शन एक रेखीय खोज की तुलना में खराब हो जाए। खोज वृक्ष को संतुलित और ऊँचाई से घिरा रखना $O(\log n)$ बाइनरी सर्च ट्री की उपयोगिता की कुंजी है। बाइनरी लॉगरिदमिक जटिलता के लिए पेड़ की ऊंचाई को बनाए रखने के लिए डिज़ाइन किए गए पेड़ के अद्यतन संचालन के दौरान इसे स्व-संतुलन तंत्र द्वारा प्राप्त किया जा सकता है।

ऊंचाई-संतुलित पेड़

एक पेड़ ऊँचाई-संतुलित होता है यदि बाएँ उप-वृक्ष और दाएँ उप-वृक्ष की ऊँचाइयों को एक स्थिर कारक द्वारा संबंधित होने की गारंटी दी जाती है। यह संपत्ति एवीएल पेड़ द्वारा पेश की गई थी और लाल-काले पेड़ द्वारा जारी रखी गई थी। रूट से संशोधित लीफ नोड तक पथ पर सभी नोड्स की ऊंचाई को देखा जाना चाहिए और संभवतया पेड़ में प्रत्येक डालने और हटाने के ऑपरेशन पर सही किया जाना चाहिए।

वजन-संतुलित पेड़

Main article: Weight-balanced tree

भार-संतुलित वृक्ष में, संतुलित वृक्ष की कसौटी उपवृक्षों की पत्तियों की संख्या है। बाएँ और दाएँ सबट्री का वज़न सबसे अधिक भिन्न होता है $1$. हालांकि, अंतर एक अनुपात से बंधा हुआ है $\alpha$ वजन की, एक मजबूत संतुलन की स्थिति के बाद से $1$ के साथ नहीं रखा जा सकता $O(\log n)$ डालने और हटाने के संचालन के दौरान पुनर्संतुलन कार्य। $\alpha$वें>-वजन-संतुलित पेड़ संतुलन की स्थिति का एक पूरा परिवार देता है, जहां प्रत्येक बाएँ और दाएँ सबट्री में कम से कम एक अंश होता है $\alpha$ सबट्री के कुल वजन का।

प्रकार

कई स्व-संतुलित बाइनरी सर्च ट्री हैं, जिनमें टी पेड़, ट्रीप, लाल-काले पेड़, बी-पेड़, 2-3 पेड़, और स्प्ले पेड़ ।

अनुप्रयोगों के उदाहरण

क्रमबद्ध करें

Main article: Tree sort

बाइनरी सर्च ट्री का उपयोग सॉर्टिंग एल्गोरिदम जैसे ट्री सॉर्ट में किया जाता है, जहां सभी तत्वों को एक ही बार में डाला जाता है और ट्री को इन-ऑर्डर फैशन में ट्रैवर्स किया जाता है। BST का उपयोग जल्दी से सुलझाएं में भी किया जाता है।

प्राथमिकता कतार संचालन

Main article: Priority queue

बाइनरी सर्च ट्री का उपयोग प्राथमिकता कतारों को लागू करने में किया जाता है, नोड की कुंजी को प्राथमिकताओं के रूप में उपयोग करते हुए। कतार में नए तत्व जोड़ना नियमित BST सम्मिलन ऑपरेशन का अनुसरण करता है लेकिन निष्कासन ऑपरेशन प्राथमिकता कतार के प्रकार पर निर्भर करता है:

• यदि यह एक आरोही क्रम प्राथमिकता कतार है, तो सबसे कम प्राथमिकता वाले तत्व को BST के बाईं ओर ट्रैवर्सल के माध्यम से हटाया जाता है।
• यदि यह अवरोही क्रम की प्राथमिकता कतार है, तो उच्चतम प्राथमिकता वाले तत्व को BST के दाईं ओर ट्रैवर्सल के माध्यम से हटाया जाता है।

यह भी देखें

• खोज पेड़
• ज्वाइन-आधारित ट्री एल्गोरिदम
• इष्टतम बाइनरी सर्च ट्री
• बाइनरी सर्च ट्री की ज्यामिति
• त्रिगुट खोज वृक्ष

अग्रिम पठन

•  This article incorporates public domain material from Black, Paul E. "Binary Search Tree". Dictionary of Algorithms and Data Structures.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "12: Binary search trees, 15.5: Optimal binary search trees". Introduction to Algorithms (2nd ed.). MIT Press. pp. 253–272, 356–363. ISBN 0-262-03293-7.
• Jarc, Duane J. (3 December 2005). "Binary Tree Traversals". Interactive Data Structure Visualizations. University of Maryland. Archived from the original on 27 February 2014. Retrieved 30 April 2006.
• Knuth, Donald (1997). "6.2.2: Binary Tree Searching". The Art of Computer Programming. Vol. 3: "Sorting and Searching" (3rd ed.). Addison-Wesley. pp. 426–458. ISBN 0-201-89685-0.
• Long, Sean. "Binary Search Tree" (PPT). Data Structures and Algorithms Visualization-A PowerPoint Slides Based Approach. SUNY Oneonta.
• Parlante, Nick (2001). "Binary Trees". CS Education Library. Stanford University. Archived from the original on 2022-01-30.

बाहरी संबंध

• Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675 kB) 2004.
• Binary Tree Visualizer (JavaScript animation of various BT-based data structures)