बाइनरी सर्च ट्री: Difference between revisions

Time complexity in big O notation
Algorithm
Algorithm	Average

Latest revision as of 09:43, 1 May 2023

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

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

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

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

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

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

इतिहास

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

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

सिंहावलोकन

बाइनरी सर्च ट्री एक पाठ्यक्रम है जिसमें नोड्स को एक क्रम में व्यवस्थित किया जाता है ये गैर-सख्त क्रम में रखे जाते हैं जिसमें किसी विशेष कुंजियों वाले बाइनरी सर्च ट्री से संग्रहित होते हैं तथा जो बाइनरी सर्च को संतुष्ट करते हैं।^[9]^: 298^[10]^: 287

खोज प्रारूप को छोटा करने में बाइनरी सर्च ट्री प्रभावशाली है जिसमें कार्यान्वित आदेश और पहचान करने की आवश्यकता नहीं होती है जबकि बीएसटी की खोज जटिलता के उस क्रम पर निर्भर करती है जिसमें नोड्स डाले और हटाए जाते हैं जिससे कि खराब स्थिति बाइनरी सर्च ट्री में क्रमिक संचालन अर्धपतन का कारण बन जाता है और संरचना की तरह एक एकल सूची बना सकता है इस प्रकार सूची के रूप में सबसे खराब स्थिति वाली जटिलता में संग्रहित किया जाता है।^[11]^[9]^: 299-302

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

संचालन

खोजना

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

बाइनरी सर्च ट्री की डेटा संरचना में लकड़ी की जांच की खोज शुरू होती है अगर सर्च ट्री नल बिन्दु कुंजी रूट के बराबर है तो खोज सफल होगी और नोड वापस आ जाता है यदि कुंजी रूट से कम है तो खोज बाएँ ट्री की जाँच करके आगे बढ़ती है इसी तरह यदि कुंजी रूट से अधिक है तो खोज हो चुकी होती है यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कुंजी मिल नहीं जाती या शेष सर्च ट्री नहीं मिल जाता यदि खोजी गई कुंजी नहीं मिलती तो कुंजी सर्च ट्री में नहीं होती है।^[10]^{: 290–291}

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

निम्नलिखित स्यूडोकोड पुनरावर्तन कंप्यूटर विज्ञान के माध्यम से बीटीएस खोज प्रक्रिया को लागू करता है।^[10]

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

खोज के पुनरावर्ती संस्करण को कुछ समय में नियंत्रित किया जा सकता है क्योंकि अधिकांश मशीनों पर पुनरावृत्त संस्करण कंप्यूटर प्रदर्शन में पाया जाता है।^[10]^: 291

इसमें खोज के कुछ लसीका नोड होते हैं बीएसटी खोज की दौड़ कठिन होती है जबकि बीएसटी खोज की सबसे खराब स्थिति होती है तथा बीएसटी में नोड्स की कुल संख्या एन है क्योंकि एक असंतुलित बीएसटी एक सूची में खराब हो सकती है जबकि बीटीएस ऊँचाई-संतुलित सर्च ट्री है ।^[10]

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

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

^[12]^[13]^[10]

बीएसटी में एक नोड खोजने के लिए संचालन जिसकी कुंजी सीमा अधिकतम या न्यूनतम है यह कुछ कार्यों में महत्वपूर्ण हैं जैसे कि उत्तराधिकारी और नोड्स के पूर्ववर्ती का निर्धारण करना संचालन के लिए स्यूडोकोड महत्वपूर्ण हैं।^[10]^{: 291–292}

प्रविष्टि

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

हटाना

यह एक नोड का विलोपन है जो एक बाइनरी सर्च ट्री से बीएसटी की तीन स्थितियों का पालन करते हैं।^[10]^: 295

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

निम्नलिखित स्यूडोकोड बाइनरी सर्च ट्री में विलोपन ऑपरेशन को लागू करता है।^[10]^: 296-298 The following pseudocode implements the deletion operation in a binary search tree.^[10]^: 296-298

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

The ${\text{Tree-Delete}}$ procedure deals with the 3 special cases mentioned above. Lines 2-3 deal with case 1; lines 4-5 deal with case 2 and lines 6-16 for case 3. The helper function ${\text{Shift-Nodes}}$ is used within the deletion algorithm for the purpose of replacing the node ${\text{u}}$ with ${\text{v}}$ in the binary search tree ${\text{BST}}$ .^[10]^: 298 This procedure handles the deletion (and substitution) of ${\text{u}}$ from ${\text{BST}}$ .

यात्रीगण

एक बीएसटी तीन बुनियादी प्रारूप के माध्यम से यात्रा हो सकती है यात्रा में आदेश उप आदेशिक यात्रा और पोस्ट आदेश यात्रायें भी सम्मिलित हैं।^[10]

बाएं सर्च ट्री से नोड्स पहले देखे जाते हैं उसके बाद रूट देखे जाते हैं।
जड़ को पहले बहाया जाता है उसके बाद बाएँ और दाएँ सर्च ट्री को देखा जाता है।
बाएं सर्च ट्री से नोड्स पहले देखे जाते हैं।

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

पुनर्संतुलन के बिना बाइनरी सर्च ट्री में सम्मिलित या विलोपन अर्धपतन का कारण बन सकता है जिसके परिणामस्वरूप ऊँचाई होती है एक रेखीय खोज की तुलना में सर्च ट्री को संतुलित और ऊँचाई से घेरे रखना होता है बाइनरी प्रारूप जटिलता के लिए बाइनरी सर्च ट्री की ऊंचाई को बनाए रखने के लिए बनावट किए गए ट्री के अद्यतन संचालन के दौरान इसे स्व-संतुलन तंत्र द्वारा प्राप्त किया जा सकता है।^[4]^[14]

ऊंचाई-संतुलित ट्री

एक सर्च ट्री ऊँचाई-संतुलित में होता है यदि बाइनरी सर्च ट्री की ऊँचाइयों को एक स्थिर कारक द्वारा संबंधित होने दिया जाता है। यह संपत्ति एवीएल ट्री द्वारा पेश की गई थी और लाल-काले ट्री द्वारा जारी रखी गई थी।^[14]^: 50–51जड़ से संशोधित पत्ती तक पथ पर सभी की ऊंचाई को देखी जानी चाहिए और संभवतया ट्री में प्रत्येक डाल को हटाने के लिए सही किया जाना चाहिए।^[14]^: 52

वजन-संतुलित ट्री

भार-संतुलित ट्री में संतुलित ट्री की कसौटी की पत्तियों की संख्या है बाएँ और दाएँ सर्च ट्री का वजन सबसे अधिक होता है ^[15]^[14]^: 61 जबकि अंतर अनुपात से बंधा हुआ है अल्फा संतुलन की स्थिति के बाद नहीं रखा जा सकता सर्च ट्री संतुलन की स्थिति का एक पूरा परिवार होता है जहां प्रत्येक सर्च ट्री में कम से कम एक अंश होता है।^[14]^: 62

प्रकार

कई स्व-संतुलित बाइनरी सर्च ट्री हैं जिनमें ^[16] ^[17] रेड-ब्लैक ट्री^[18] भी होते हैं।

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

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

बाइनरी सर्च ट्री का उपयोग में ट्री का प्रारूप छोटा किया जाता है जहां सभी तत्वों को एक ही बार में डाला जाता है।

^[19]^[20]

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

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

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

यह भी देखें

संदर्भ

↑ Culberson, J.; Munro, J. I. (1 January 1989). "लंबे समय तक अपडेट के तहत बाइनरी सर्च ट्री के व्यवहार की व्याख्या: एक मॉडल और सिमुलेशन". The Computer Journal. 32 (1): 68–69. doi:10.1093/comjnl/32.1.68.
↑ Culberson, J.; Munro, J. I. (28 July 1986). "सटीक फिट डोमेन बाइनरी सर्च ट्री में मानक विलोपन एल्गोरिदम का विश्लेषण". Algorithmica. Springer Publishing, University of Waterloo. 5 (1–4): 297. doi:10.1007/BF01840390. S2CID 971813.
↑ P. F. Windley (1 January 1960). "पेड़, वन और पुनर्व्यवस्था". The Computer Journal. 3 (2): 84. doi:10.1093/comjnl/3.2.84.
↑ ^4.0 ^4.1 Knuth, Donald (1998). "Section 6.2.3: Balanced Trees". कंप्यूटर प्रोग्रामिंग की कला (PDF). Vol. 3 (2 ed.). Addison-Wesley. pp. 458–481. ISBN 978-0201896855. Archived (PDF) from the original on 2022-10-09.
↑ Paul E. Black, "red-black tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 November 2019. (accessed May 19 2022) from: https://www.nist.gov/dads/HTML/redblack.html
↑ Myers, Andrew. "CS 312 Lecture: AVL Trees". Cornell University, Department of Computer Science. Archived from the original on 27 April 2021. Retrieved 19 May 2022.
↑ Adelson-Velsky, Georgy; Landis, Evgenii (1962). "सूचना के संगठन के लिए एक एल्गोरिथ्म". Proceedings of the USSR Academy of Sciences (in русский). 146: 263–266. English translation by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962.
↑ Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" (PDF). University of Toronto, Department of Computer Science. p. 6. Archived (PDF) from the original on 14 February 2019. Retrieved 19 May 2022.
↑ ^9.0 ^9.1 Thareja, Reema (13 October 2018). "Hashing and Collision". सी का उपयोग कर डेटा संरचनाएं (2 ed.). Oxford University Press. ISBN 9780198099307.
↑ ^10.00 ^10.01 ^10.02 ^10.03 ^10.04 ^10.05 ^10.06 ^10.07 ^10.08 ^10.09 ^10.10 ^10.11 ^10.12 ^10.13 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). एल्गोरिदम का परिचय (2nd ed.). MIT Press. ISBN 0-262-03293-7.
↑ R. A. Frost; M. M. Peterson (1 February 1982). "A Short Note on Binary Search Trees". The Computer Journal. Oxford University Press. 25 (1): 158. doi:10.1093/comjnl/25.1.158.
↑ Junzhou Huang. "एल्गोरिदम का डिजाइन और विश्लेषण" (PDF). University of Texas at Arlington. p. 12. Archived (PDF) from the original on 13 April 2021. Retrieved 17 May 2021.
↑ Ray, Ray. "बाइनरी सर्च ट्री". Loyola Marymount University, Department of Computer Science. Retrieved 17 May 2022.
↑ ^14.0 ^14.1 ^14.2 ^14.3 ^14.4 Brass, Peter (January 2011). उन्नत डेटा संरचना. Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 9780511800191.
↑ Blum, Norbert; Mehlhorn, Kurt (1978). "वजन-संतुलित पेड़ों में पुनर्संतुलन संचालन की औसत संख्या पर" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3. Archived (PDF) from the original on 2022-10-09.
↑ Lehman, Tobin J.; Carey, Michael J. (25–28 August 1986). मेन मेमोरी डेटाबेस मैनेजमेंट सिस्टम्स के लिए इंडेक्स स्ट्रक्चर्स का अध्ययन. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. ISBN 0-934613-18-4.
↑ Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees" (PDF), Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1, archived (PDF) from the original on 2022-10-09
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (second ed.). MIT Press. pp. 273–301. ISBN 978-0-262-03293-3.
↑ Narayanan, Arvind (2019). "COS226: Binary search trees". Princeton University School of Engineering and Applied Science. Archived from the original on 22 March 2021. Retrieved 21 October 2021 – via cs.princeton.edu.
↑ Xiong, Li. "बाइनरी सर्च ट्री और क्विकसॉर्ट के बीच एक कनेक्शन". Oxford College of Emory University, The Department of Mathematics and Computer Science. Archived from the original on 26 February 2021. Retrieved 4 June 2022.
↑ Myers, Andrew. "CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps". Cornell University, Department of Computer Science. Archived from the original on 21 October 2021. Retrieved 21 October 2021.

अग्रिम पठन

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)

[computer_journal89-1] Culberson, J.; Munro, J. I. (1 January 1989). "लंबे समय तक अपडेट के तहत बाइनरी सर्च ट्री के व्यवहार की व्याख्या: एक मॉडल और सिमुलेशन". The Computer Journal. 32 (1): 68–69. doi:10.1093/comjnl/32.1.68.

[2] Culberson, J.; Munro, J. I. (28 July 1986). "सटीक फिट डोमेन बाइनरी सर्च ट्री में मानक विलोपन एल्गोरिदम का विश्लेषण". Algorithmica. Springer Publishing, University of Waterloo. 5 (1–4): 297. doi:10.1007/BF01840390. S2CID 971813.

[windley60-3] P. F. Windley (1 January 1960). "पेड़, वन और पुनर्व्यवस्था". The Computer Journal. 3 (2): 84. doi:10.1093/comjnl/3.2.84.

[Knuth98-4] 4.0 ^4.1 Knuth, Donald (1998). "Section 6.2.3: Balanced Trees". कंप्यूटर प्रोग्रामिंग की कला (PDF). Vol. 3 (2 ed.). Addison-Wesley. pp. 458–481. ISBN 978-0201896855. Archived (PDF) from the original on 2022-10-09.

[5] Paul E. Black, "red-black tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 November 2019. (accessed May 19 2022) from: https://www.nist.gov/dads/HTML/redblack.html

[6] Myers, Andrew. "CS 312 Lecture: AVL Trees". Cornell University, Department of Computer Science. Archived from the original on 27 April 2021. Retrieved 19 May 2022.

[7] Adelson-Velsky, Georgy; Landis, Evgenii (1962). "सूचना के संगठन के लिए एक एल्गोरिथ्म". Proceedings of the USSR Academy of Sciences (in русский). 146: 263–266. English translation by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962.

[8] Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" (PDF). University of Toronto, Department of Computer Science. p. 6. Archived (PDF) from the original on 14 February 2019. Retrieved 19 May 2022.

[reema18-9] 9.0 ^9.1 Thareja, Reema (13 October 2018). "Hashing and Collision". सी का उपयोग कर डेटा संरचनाएं (2 ed.). Oxford University Press. ISBN 9780198099307.

[algo_cormen-10] 10.00 ^10.01 ^10.02 ^10.03 ^10.04 ^10.05 ^10.06 ^10.07 ^10.08 ^10.09 ^10.10 ^10.11 ^10.12 ^10.13 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). एल्गोरिदम का परिचय (2nd ed.). MIT Press. ISBN 0-262-03293-7.

[11] R. A. Frost; M. M. Peterson (1 February 1982). "A Short Note on Binary Search Trees". The Computer Journal. Oxford University Press. 25 (1): 158. doi:10.1093/comjnl/25.1.158.

[12] Junzhou Huang. "एल्गोरिदम का डिजाइन और विश्लेषण" (PDF). University of Texas at Arlington. p. 12. Archived (PDF) from the original on 13 April 2021. Retrieved 17 May 2021.

[13] Ray, Ray. "बाइनरी सर्च ट्री". Loyola Marymount University, Department of Computer Science. Retrieved 17 May 2022.

[peter11-14] 14.0 ^14.1 ^14.2 ^14.3 ^14.4 Brass, Peter (January 2011). उन्नत डेटा संरचना. Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 9780511800191.

[15] Blum, Norbert; Mehlhorn, Kurt (1978). "वजन-संतुलित पेड़ों में पुनर्संतुलन संचालन की औसत संख्या पर" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3. Archived (PDF) from the original on 2022-10-09.

[16] Lehman, Tobin J.; Carey, Michael J. (25–28 August 1986). मेन मेमोरी डेटाबेस मैनेजमेंट सिस्टम्स के लिए इंडेक्स स्ट्रक्चर्स का अध्ययन. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. ISBN 0-934613-18-4.

[17] Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees" (PDF), Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1, archived (PDF) from the original on 2022-10-09

[Cormen2001-18] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (second ed.). MIT Press. pp. 273–301. ISBN 978-0-262-03293-3.

[19] Narayanan, Arvind (2019). "COS226: Binary search trees". Princeton University School of Engineering and Applied Science. Archived from the original on 22 March 2021. Retrieved 21 October 2021 – via cs.princeton.edu.

[20] Xiong, Li. "बाइनरी सर्च ट्री और क्विकसॉर्ट के बीच एक कनेक्शन". Oxford College of Emory University, The Department of Mathematics and Computer Science. Archived from the original on 26 February 2021. Retrieved 4 June 2022.

[21] Myers, Andrew. "CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps". Cornell University, Department of Computer Science. Archived from the original on 21 October 2021. Retrieved 21 October 2021.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

@@ Line 28: / Line 28: @@
 बाइनरी सर्च ट्री भी एक मूलभूत डेटा संरचना है जिसका उपयोग अमूर्त डेटा संरचनाओं जैसे सेट कंप्यूटर विज्ञान और साहचर्य सारणियों के निर्माण में किया जाता है।
-[[Category:Articles with hatnote templates targeting a nonexistent page|Binary search tree]]
-[[Category:C++ कोड उदाहरण के साथ लेख|Binary search tree]]
-[[Category:CS1|Binary search tree]]
-[[Category:CS1 русский-language sources (ru)|Binary search tree]]
-[[Category:Created On 24/02/2023|Binary search tree]]
-[[Category:Good articles|Binary search tree]]
-[[Category:Machine Translated Page|Binary search tree]]
-[[Category:Pages with reference errors|Binary search tree]]
-[[Category:Pages with script errors|Binary search tree]]
 == संचालन ==
@@ Line 60: / Line 60: @@
 बीएसटी में एक नोड खोजने के लिए संचालन जिसकी कुंजी सीमा अधिकतम या न्यूनतम है यह कुछ कार्यों में महत्वपूर्ण हैं जैसे कि उत्तराधिकारी और नोड्स के पूर्ववर्ती का निर्धारण करना संचालन के लिए स्यूडोकोड महत्वपूर्ण हैं।<ref name="algo_cormen" />{{rp|291–292}}
-[[Category:Articles with hatnote templates targeting a nonexistent page|Binary search tree]]
-[[Category:C++ कोड उदाहरण के साथ लेख|Binary search tree]]
-[[Category:CS1|Binary search tree]]
-[[Category:CS1 русский-language sources (ru)|Binary search tree]]
-[[Category:Created On 24/02/2023|Binary search tree]]
-[[Category:Good articles|Binary search tree]]
-[[Category:Machine Translated Page|Binary search tree]]
-[[Category:Pages with reference errors|Binary search tree]]
-[[Category:Pages with script errors|Binary search tree]]
 === प्रविष्टि ===
@@ Line 74: / Line 74: @@
 === हटाना ===
-यह एक नोड का विलोपन है जो एक बाइनरी सर्च ट्री से बीएसटी की तीन स्थितियों का पालन करते हैं। {{r}}
+यह एक नोड का विलोपन है जो एक बाइनरी सर्च ट्री से बीएसटी की तीन स्थितियों का पालन करते हैं।{{r|algo_cormen|p=295}}
 # माना डी एक पत्ती है जो डी का मूल बिन्दु है डी सर्च ट्री से हटा दिया जाता है।
 # अगर डी एक एकल विद्यार्थी है तो बच्चा बाएँ या दाएँ बच्चे के रूप में उन्नत करेगा डी माता-पिता की स्थिति के आधार पर कार्य करता है जैसे अंजीर में दिखाया गया है कि भाग ए और भाग बी और डी पेड़ से हटा दिया जाता है।
@@ Line 82: / Line 82: @@
   &nbsp; &nbsp; &nbsp; [[File:AVL-tree-delete.svg|600px|नोड <math>\mathsf{D}</math> हटाने के लिए 2 बच्चे हैं]]
 {{clear}}
-निम्नलिखित स्यूडोकोड बाइनरी सर्च ट्री में विलोपन ऑपरेशन को लागू करता है।{{r}}
+निम्नलिखित स्यूडोकोड बाइनरी सर्च ट्री में विलोपन ऑपरेशन को लागू करता है।{{r|algo_cormen|p=296-298}}
+The following pseudocode implements the deletion operation in a binary search tree.{{r|algo_cormen|p=296-298}}
+{|
+|- style="vertical-align:top"
+|
+    BST-Delete(BST, D)
+      '''if''' D.left = NIL '''then'''
+        Shift-Nodes(BST, D, D.right)
+      '''else if''' D.right = NIL '''then'''
+        Shift-Nodes(BST, D, D.left)
+      '''else'''
+        E := Tree-Successor(D)
+        '''if''' E.parent &ne; D '''then'''
+          Shift-Nodes(BST, E, E.right)
+         E.right := D.right
+         E.right.parent := E
+       '''end if'''
+       Shift-Nodes(BST, D, E)
+       E.left := D.left
+       E.left.parent := E
+     '''end if'''
+|
+    Shift-Nodes(BST, u, v)
+      '''if''' u.parent = NIL '''then'''
+        BST.root := v
+      '''else if''' u = u.parent.left '''then'''
+        u.parent.left := v
+      '''else'''
+        u.parent.right := v
+      '''end if'''
+      '''if''' v &ne; NIL '''then'''
+        v.parent := u.parent
+     '''end if'''
+|}
+The <math>\text{Tree-Delete}</math> procedure deals with the 3 special cases mentioned above. Lines 2-3 deal with case 1; lines 4-5 deal with case 2 and lines 6-16 for case 3. The [[helper function]] <math>\text{Shift-Nodes}</math> is used within the deletion algorithm for the purpose of replacing the node <math>\text{u}</math> with <math>\text{v}</math> in the binary search tree <math>\text{BST}</math>.{{r|algo_cormen|p=298}} This procedure handles the deletion (and substitution) of <math>\text{u}</math> from <math>\text{BST}</math>.
 == यात्रीगण ==
@@ Line 99: / Line 142: @@
 === ऊंचाई-संतुलित ट्री ===
-एक सर्च ट्री ऊँचाई-संतुलित में होता है यदि बाइनरी सर्च ट्री की ऊँचाइयों को एक स्थिर कारक द्वारा संबंधित होने दिया जाता है। यह संपत्ति एवीएल ट्री द्वारा पेश की गई थी और लाल-काले ट्री द्वारा जारी रखी गई थी।{{r}} जड़ से संशोधित पत्ती तक पथ पर सभी की ऊंचाई को देखी जानी चाहिए और संभवतया ट्री में प्रत्येक डाल को हटाने के लिए सही किया जाना चाहिए।{{r|peter11|pp=52}}
+एक सर्च ट्री ऊँचाई-संतुलित में होता है यदि बाइनरी सर्च ट्री की ऊँचाइयों को एक स्थिर कारक द्वारा संबंधित होने दिया जाता है। यह संपत्ति एवीएल ट्री द्वारा पेश की गई थी और लाल-काले ट्री द्वारा जारी रखी गई थी।{{r|peter11|pp=50-51}}जड़ से संशोधित पत्ती तक पथ पर सभी की ऊंचाई को देखी जानी चाहिए और संभवतया ट्री में प्रत्येक डाल को हटाने के लिए सही किया जाना चाहिए।{{r|peter11|pp=52}}
 === वजन-संतुलित ट्री ===
 {{main|वजन संतुलित ट्री}}
-भार-संतुलित ट्री में संतुलित ट्री की कसौटी की पत्तियों की संख्या है बाएँ और दाएँ सर्च ट्री का वजन सबसे अधिक होता है <ref>{{Cite journal|doi=10.1016/0304-3975(80)90018-3|title=वजन-संतुलित पेड़ों में पुनर्संतुलन संचालन की औसत संख्या पर|journal=Theoretical Computer Science|volume=11|issue=3|pages=303–320|year=1978|last1=Blum|first1=Norbert|last2=Mehlhorn|first2=Kurt|url=http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-date=2022-10-09 |url-status=live}}</ref>{{r}} जबकि अंतर अनुपात से बंधा हुआ है अल्फा संतुलन की स्थिति के बाद नहीं रखा जा सकता सर्च ट्री संतुलन की स्थिति का एक पूरा परिवार होता है जहां प्रत्येक सर्च ट्री में कम से कम एक अंश होता है।{{r|peter11|pp=62}}
+भार-संतुलित ट्री में संतुलित ट्री की कसौटी की पत्तियों की संख्या है बाएँ और दाएँ सर्च ट्री का वजन सबसे अधिक होता है <ref>{{Cite journal|doi=10.1016/0304-3975(80)90018-3|title=वजन-संतुलित पेड़ों में पुनर्संतुलन संचालन की औसत संख्या पर|journal=Theoretical Computer Science|volume=11|issue=3|pages=303–320|year=1978|last1=Blum|first1=Norbert|last2=Mehlhorn|first2=Kurt|url=http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf |archive-date=2022-10-09 |url-status=live}}</ref>{{r|peter11|pp=61}} जबकि अंतर अनुपात से बंधा हुआ है अल्फा संतुलन की स्थिति के बाद नहीं रखा जा सकता सर्च ट्री संतुलन की स्थिति का एक पूरा परिवार होता है जहां प्रत्येक सर्च ट्री में कम से कम एक अंश होता है।{{r|peter11|pp=62}}
 === प्रकार ===
@@ Line 149: / Line 212: @@
 * [http://btv.melezinek.cz Binary Tree Visualizer] (JavaScript animation of various BT-based data structures)
-{{DEFAULTSORT:Binary search tree}}[[Category: C++ कोड उदाहरण के साथ लेख]] [[Category: लेख उदाहरण के साथ पायथन (प्रोग्रामिंग भाषा) कोड]] [[Category: बाइनरी पेड़]] [[Category: पेड़ खोजें]]
+{{DEFAULTSORT:Binary search tree}}
+[[Category:Articles with hatnote templates targeting a nonexistent page|Binary search tree]]
+[[Category:C++ कोड उदाहरण के साथ लेख|Binary search tree]]
-[[Category: Machine Translated Page]]
+[[Category:CS1|Binary search tree]]
-[[Category:Created On 24/02/2023]]
+[[Category:CS1 русский-language sources (ru)|Binary search tree]]
+[[Category:Created On 24/02/2023|Binary search tree]]
+[[Category:Good articles|Binary search tree]]
+[[Category:Lua-based templates|Binary search tree]]
+[[Category:Machine Translated Page|Binary search tree]]
+[[Category:Pages with reference errors|Binary search tree]]
+[[Category:Pages with script errors|Binary search tree]]
+[[Category:Templates Vigyan Ready|Binary search tree]]
+[[Category:Templates that add a tracking category|Binary search tree]]
+[[Category:Templates that generate short descriptions|Binary search tree]]
+[[Category:Templates using TemplateData|Binary search tree]]
+[[Category:पेड़ खोजें|Binary search tree]]
+[[Category:बाइनरी पेड़|Binary search tree]]
+[[Category:लेख उदाहरण के साथ पायथन (प्रोग्रामिंग भाषा) कोड|Binary search tree]]

Anonymous

Search

बाइनरी सर्च ट्री: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:43, 1 May 2023

Contents

इतिहास

सिंहावलोकन