This is a good article. Click here for more information.

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

From Vigyanwiki
Revision as of 08:13, 14 March 2023 by alpha>Ayushidixit

Time complexity in big O notation
Algorithm Average Worst case
चित्र 1: आकार 9 और गहराई 3 का एक बाइनरी सर्च ट्री, जिसकी जड़ 8 है। पत्तियाँ नहीं खींची जाती हैं।

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

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

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

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

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

इतिहास

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

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


सिंहावलोकन

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

खोज प्रारूप को छोटा करने में बाइनरी सर्च ट्री भी प्रभावशाली हैं। इस प्रकार कार्यान्वित आदेश और पहचान करने की आवश्यकता नहीं है जबकि बीएसटी की खोज जटिलता के उस क्रम पर निर्भर करती है जिसमें नोड्स डाले और हटाए जाते हैं जिससे कि खराब स्थिति बाइनरी सर्च ट्री में क्रमिक संचालन अर्धपतन का कारण बन सकता है और संरचना की तरह एक एकल लिंक्ड सूची बना सकता है इस प्रकार सूची के रूप में सबसे खराब स्थिति वाली जटिलता में संग्रहित किया जाता है।[11]Cite error: Invalid <ref> tag; refs with no name must have content

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

संचालन

खोजना

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

बाइनरी सर्च ट्री को डेटा संरचना में लकड़ी की जांच से खोज शुरू होती है अगर सर्च ट्री नल बिन्दु कुंजी रूट के बराबर है तो खोज सफल होती है और नोड वापस आ सकता है। यदि कुंजी रूट से कम है तो खोज बाएँ ट्री की जाँच करके आगे बढ़ती है इसी तरह यदि कुंजी रूट से अधिक है तो खोज हो चुकी होती है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कुंजी मिल नहीं जाती या शेष सर्च ट्री नहीं मिल जाते यदि खोजी गई कुंजी नहीं मिलती तो कुंजी सर्च ट्री में नहीं है।Cite error: Invalid <ref> tag; refs with no name must have content

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

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

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

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

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

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

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

[12][13][10]

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


प्रविष्टि

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

हटाना

यह एक नोड का विलोपन है जो एक बाइनरी सर्च ट्री से बीएसटी की तीन स्थितियों का पालन करते हैं। Cite error: Invalid <ref> tag; refs with no name must have content

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

निम्नलिखित स्यूडोकोड बाइनरी सर्च ट्री में विलोपन ऑपरेशन को लागू करता है।Cite error: Invalid <ref> tag; refs with no name must have content


यात्रीगण

Error: no page names specified (help).

See also: Threaded binary tree

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

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


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

Main article: Self-balancing binary search tree

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

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

एक सर्च ट्री ऊँचाई-संतुलित में होता है यदि बाइनरी सर्च ट्री की ऊँचाइयों को एक स्थिर कारक द्वारा संबंधित होने दिया जाता है। यह संपत्ति एवीएल ट्री द्वारा पेश की गई थी और लाल-काले ट्री द्वारा जारी रखी गई थी।Cite error: Invalid <ref> tag; refs with no name must have content जड़ से संशोधित पत्ती तक पथ पर सभी की ऊंचाई को देखी जानी चाहिए और संभवतया ट्री में प्रत्येक डाल को हटाने के लिए सही किया जाना चाहिए।[14]: 52 

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

Main article: Weight-balanced tree

भार-संतुलित ट्री में संतुलित ट्री की कसौटी की पत्तियों की संख्या है बाएँ और दाएँ सर्च ट्री का वजन सबसे अधिक होता है [15]Cite error: Invalid <ref> tag; refs with no name must have content जबकि अंतर अनुपात से बंधा हुआ है अल्फा संतुलन की स्थिति के बाद नहीं रखा जा सकता सर्च ट्री संतुलन की स्थिति का एक पूरा परिवार होता है जहां प्रत्येक सर्च ट्री में कम से कम एक अंश होता है।[14]: 62 

प्रकार

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


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

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

Main article: Tree sort

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


[19][20]


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

Main article: Priority queue

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

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

यह भी देखें

संदर्भ

  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.
  3. ↑ P. F. Windley (1 January 1960). "पेड़, वन और पुनर्व्यवस्था". The Computer Journal. 3 (2): 84. doi:10.1093/comjnl/3.2.84.
  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.
  9. ↑ Thareja, Reema (13 October 2018). "Hashing and Collision". सी का उपयोग कर डेटा संरचनाएं (2 ed.). Oxford University Press. ISBN 9780198099307.
  10. ↑ 10.0 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 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.
  14. ↑ 14.0 14.1 14.2 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
  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.


अग्रिम पठन


बाहरी संबंध

Wikimedia Commons has media related to Binary search trees.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बाइनरी_सर्च_ट्री&oldid=144224’