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

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

From Vigyanwiki
Revision as of 10:44, 4 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] सबसे शुरुआती और लोकप्रिय चयनित खोज वृक्ष प्रदर्शन हिब्बार्ड का है।[1]

चयनित खोज वृक्ष की जटिलताएं पेड़ की ऊंचाई के साथ असीम रूप से बढ़ जाती हैं यदि नोड्स को एक मनमाने क्रम में डाला जाता है तथा पेंड़ की ऊंचाई को सीमित करने के लिए स्व-संतुलन चयनित खोज वृक्ष पेश किए गए थे [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][14]: 61  जबकि अंतर एक अनुपात से बंधा हुआ है अल्फा की एक मजबूत संतुलन की स्थिति के बाद के साथ नहीं रखा जा सकता पेड़ संतुलन की स्थिति का एक पूरा परिवार देता है जहां प्रत्येक बाएँ और दाएँ उप पेंड़ में कम से कम एक अंश होता है।[14]: 62 

प्रकार

कई स्व-संतुलित बाइनरी खोज पेंड़ हैं जिनमें पेड़[16] तड़प[17] लाल-काले पेड़[18] बी-पेड़[19] दो तीन पेड़ [20] और स्प्ले पेड़ आदि।[21]


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

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

Main article: Tree sort

बाइनरी खोज पेंड़ का उपयोग में पेंड़ का प्रारूप छोटा में किया जाता है जहां सभी तत्वों को एक ही बार में डाला जाता है [22] बीएसटी का उपयोग जल्दी से किया जाता है।[23]


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

Main article: Priority queue

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

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

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.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 14.3 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. ↑ Comer, Douglas (June 1979), "The Ubiquitous B-Tree", Computing Surveys, 11 (2): 123–137, doi:10.1145/356770.356776, ISSN 0360-0300, S2CID 101673
  20. ↑ Knuth, Donald M (1998). "6.2.4". कंप्यूटर प्रोग्रामिंग की कला. Vol. 3 (2 ed.). Addison Wesley. ISBN 9780201896855. The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3.
  21. ↑ Sleator, Daniel D.; Tarjan, Robert E. (1985). "स्व-समायोजन बाइनरी खोज पेड़" (PDF). Journal of the ACM. 32 (3): 652–686. doi:10.1145/3828.3835. S2CID 1165848.
  22. ↑ 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.
  23. ↑ 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.
  24. ↑ 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=144219’