बाइनरी सर्च ट्री: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
}} | }} | ||
[[File:Binary search tree.svg|right|upright=0.8|thumb|चित्र 1: आकार 9 और गहराई 3 का एक बाइनरी सर्च ट्री, जिसकी जड़ 8 है। पत्तियाँ नहीं खींची जाती हैं।]]कम्प्यूटर [[कंप्यूटर विज्ञान|विज्ञान एक]] | [[File:Binary search tree.svg|right|upright=0.8|thumb|चित्र 1: आकार 9 और गहराई 3 का एक बाइनरी सर्च ट्री, जिसकी जड़ 8 है। पत्तियाँ नहीं खींची जाती हैं।]]कम्प्यूटर [[कंप्यूटर विज्ञान|विज्ञान एक]] बाइनरी सर्च ट्री है बीएसटी जिसे क्रमांक या [[बाइनरी ट्री|चयनित]] ट्री भी कहा जाता है एक [[ जड़ वाला पेड़ |जड़ वाला]] चयनित ट्री [[डेटा संरचना]] है जिसमें आंतरिक कुंजी बाएं सर्च ट्री की सभी कुंजियों से अधिक नहीं होती हैं तथा कम होती हैं यह दाहिने सर्च ट्री की तुलना में चयनित सर्च ट्री पर संचालन की [[समय जटिलता]] सीधे ट्री की ऊंचाई के समानुपाती होती है। | ||
चयनित सर्च ट्री डेटा कार्यक्रम को तेजी से देखने जोड़ने और हटाने के लिए चयनित खोज [[बाइनरी सर्च एल्गोरिथम|कलनविधि]] की अनुमति देता है क्योंकि बीएसटी में प्रोप इस तरह रखे गए हैं कि प्रत्येक तुलना शेष सर्च ट्री के आधे हिस्से को छोड़ देती है प्रदर्शन खोजना [[द्विआधारी लघुगणक]] के समानुपाती होता है विवरण किए गए डेटा के कुशल भंडारण की समस्या के लिए 1960 के दशक में बीएसटी तैयार किए गए थे और इसका श्रेय [[कॉनवे बर्नर्स-ली]] और डेविडव्हीलर कंप्यूटर के वैज्ञानिक को दिया जाता है। | चयनित सर्च ट्री डेटा कार्यक्रम को तेजी से देखने जोड़ने और हटाने के लिए चयनित खोज [[बाइनरी सर्च एल्गोरिथम|कलनविधि]] की अनुमति देता है क्योंकि बीएसटी में प्रोप इस तरह रखे गए हैं कि प्रत्येक तुलना शेष सर्च ट्री के आधे हिस्से को छोड़ देती है प्रदर्शन खोजना [[द्विआधारी लघुगणक]] के समानुपाती होता है विवरण किए गए डेटा के कुशल भंडारण की समस्या के लिए 1960 के दशक में बीएसटी तैयार किए गए थे और इसका श्रेय [[कॉनवे बर्नर्स-ली]] और डेविडव्हीलर कंप्यूटर के वैज्ञानिक को दिया जाता है। | ||
| Line 15: | Line 15: | ||
== इतिहास == | == इतिहास == | ||
बाइनरी सर्च ट्री प्रदर्शन स्वतंत्र रूप से कई शोधकर्ताओं द्वारा खोजा गया था जिसमें पी.एफ. विंडले [[एंड्रयू डोनाल्ड बूथ]] [[एंड्रयू कॉलिन]] थॉमस एन. हिब्बार्ड तथा <ref name="computer_journal89">{{cite journal|journal=[[The Computer Journal]]|date=1 January 1989|doi=10.1093/comjnl/32.1.68|volume=32|issue=1|pages=68–69|first1=J.|last1=Culberson|first2=J. I.|last2=Munro|url=https://academic.oup.com/comjnl/article/32/1/68/341965?login=true|doi-access=free|title=लंबे समय तक अपडेट के तहत बाइनरी सर्च ट्री के व्यवहार की व्याख्या: एक मॉडल और सिमुलेशन}}</ref><ref>{{cite journal|journal=[[Algorithmica]]|publisher=[[Springer Publishing]], [[University of Waterloo]]|title= सटीक फिट डोमेन बाइनरी सर्च ट्री में मानक विलोपन एल्गोरिदम का विश्लेषण|date=28 July 1986|doi=10.1007/BF01840390|url=https://link.springer.com/article/10.1007%2FBF01840390|first1=J.|last1=Culberson|first2=J. I.|last2=Munro|volume=5 |issue=1–4 |page=297|s2cid=971813 }}</ref> प्रदर्शन का श्रेय कॉनवे बर्नर्स-ली और [[डेविड व्हीलर (कंप्यूटर वैज्ञानिक)|डेविड व्हीलर कंप्यूटर वैज्ञानिक]] को दिया जाता है जिन्होंने 1960 में [[चुंबकीय टेप]] में [[लेबल किए गए डेटा|विवरण किए गए डेटा]] को संग्रहीत करने के लिए किया गया था।<ref name="windley60">{{cite journal|journal=[[The Computer Journal]]|date=1 January 1960|doi=10.1093/comjnl/3.2.84|url=https://academic.oup.com/comjnl/article/3/2/84/504799|author=P. F. Windley|volume=3|issue=2|page=84|title= पेड़, वन और पुनर्व्यवस्था|doi-access=free}}</ref | बाइनरी सर्च ट्री प्रदर्शन स्वतंत्र रूप से कई शोधकर्ताओं द्वारा खोजा गया था जिसमें पी.एफ. विंडले [[एंड्रयू डोनाल्ड बूथ]] [[एंड्रयू कॉलिन]] थॉमस एन. हिब्बार्ड तथा <ref name="computer_journal89">{{cite journal|journal=[[The Computer Journal]]|date=1 January 1989|doi=10.1093/comjnl/32.1.68|volume=32|issue=1|pages=68–69|first1=J.|last1=Culberson|first2=J. I.|last2=Munro|url=https://academic.oup.com/comjnl/article/32/1/68/341965?login=true|doi-access=free|title=लंबे समय तक अपडेट के तहत बाइनरी सर्च ट्री के व्यवहार की व्याख्या: एक मॉडल और सिमुलेशन}}</ref><ref>{{cite journal|journal=[[Algorithmica]]|publisher=[[Springer Publishing]], [[University of Waterloo]]|title= सटीक फिट डोमेन बाइनरी सर्च ट्री में मानक विलोपन एल्गोरिदम का विश्लेषण|date=28 July 1986|doi=10.1007/BF01840390|url=https://link.springer.com/article/10.1007%2FBF01840390|first1=J.|last1=Culberson|first2=J. I.|last2=Munro|volume=5 |issue=1–4 |page=297|s2cid=971813 }}</ref> प्रदर्शन का श्रेय कॉनवे बर्नर्स-ली और [[डेविड व्हीलर (कंप्यूटर वैज्ञानिक)|डेविड व्हीलर कंप्यूटर वैज्ञानिक]] को दिया जाता है जिन्होंने 1960 में [[चुंबकीय टेप]] में [[लेबल किए गए डेटा|विवरण किए गए डेटा]] को संग्रहीत करने के लिए किया गया था।<ref name="windley60">{{cite journal|journal=[[The Computer Journal]]|date=1 January 1960|doi=10.1093/comjnl/3.2.84|url=https://academic.oup.com/comjnl/article/3/2/84/504799|author=P. F. Windley|volume=3|issue=2|page=84|title= पेड़, वन और पुनर्व्यवस्था|doi-access=free}}</ref> | ||
बाइनरी सर्च ट्री की जटिलताएं असीम रूप से बढ़ जाती हैं यदि नोड्स को एक मनमाने क्रम में | बाइनरी सर्च ट्री की जटिलताएं असीम रूप से बढ़ जाती हैं यदि नोड्स को एक मनमाने क्रम में डालते हैं तो बाइनरी सर्च ट्री की ऊंचाई को सीमित करने के लिए [[स्व-संतुलन बाइनरी सर्च ट्री|स्व-संतुलन]] पेश किए गए थे <ref name="Knuth98">{{cite book|title=कंप्यूटर प्रोग्रामिंग की कला|first=Donald|last=Knuth|author-link=Donald_Knuth|publisher=[[Addison-Wesley]]|year=1998|chapter=Section 6.2.3: Balanced Trees|pages=458–481|volume=3|edition=2|url=https://ia801604.us.archive.org/17/items/B-001-001-250/B-001-001-250.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://ia801604.us.archive.org/17/items/B-001-001-250/B-001-001-250.pdf |archive-date=2022-10-09 |url-status=live|isbn=978-0201896855 | ||
}}</ref> बाइनरी सर्च ट्री को सीमित करने के लिए विभिन्न बाइनरी सर्च ट्री पेश किए गए जैसे एवीएल ट्री [[ट्रीप]] और रेड़ ब्लैक ट्री <ref>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</ref> एवीएल का आविष्कार जॉर्जी एडेल्सन वेलेस्की और ईव्जेनी लैन्ड्स द्वारा 1962 में सूचना के कुशल संगठन के लिए किया गया था।<ref>{{cite web|url=https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec_avl.html|publisher=[[Cornell University]], Department of Computer Science|access-date=19 May 2022|title=CS 312 Lecture: AVL Trees|first=Andrew|last=Myers|url-status=live|archive-url=https://web.archive.org/web/20210427195749/http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec_avl.html|archive-date=27 April 2021}}</ref><ref>{{cite journal|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=सूचना के संगठन के लिए एक एल्गोरिथ्म|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263–266|language=ru}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref> यह आविष्कार किया जाने वाला पहला स्व-संतुलन बाइनरी सर्च ट्री था।<ref>{{cite web|url=http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|access-date=19 May 2022|url-status=live|archive-url=https://web.archive.org/web/20190214212633/http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|title=CSC263: Balanced BSTs, AVL tree|first=Toniann|last=Pitassi|year=2015|publisher=[[University of Toronto]], Department of Computer Science|archive-date=14 February 2019|page=6}}</ref> | }}</ref> बाइनरी सर्च ट्री को सीमित करने के लिए विभिन्न बाइनरी सर्च ट्री पेश किए गए जैसे एवीएल ट्री [[ट्रीप]] और रेड़ ब्लैक ट्री <ref>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</ref> एवीएल का आविष्कार जॉर्जी एडेल्सन वेलेस्की और ईव्जेनी लैन्ड्स द्वारा 1962 में सूचना के कुशल संगठन के लिए किया गया था।<ref>{{cite web|url=https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec_avl.html|publisher=[[Cornell University]], Department of Computer Science|access-date=19 May 2022|title=CS 312 Lecture: AVL Trees|first=Andrew|last=Myers|url-status=live|archive-url=https://web.archive.org/web/20210427195749/http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec_avl.html|archive-date=27 April 2021}}</ref><ref>{{cite journal|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=सूचना के संगठन के लिए एक एल्गोरिथ्म|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263–266|language=ru}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref> यह आविष्कार किया जाने वाला पहला स्व-संतुलन बाइनरी सर्च ट्री था।<ref>{{cite web|url=http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|access-date=19 May 2022|url-status=live|archive-url=https://web.archive.org/web/20190214212633/http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|title=CSC263: Balanced BSTs, AVL tree|first=Toniann|last=Pitassi|year=2015|publisher=[[University of Toronto]], Department of Computer Science|archive-date=14 February 2019|page=6}}</ref> | ||
== सिंहावलोकन == | == सिंहावलोकन == | ||
[[ द्विआधारी खोज |बाइनरी सर्च ट्री]] एक कडा़ई है जिसमें नोड्स को एक क्रम में व्यवस्थित किया जाता है ये गैर-सख्त क्रम में रखे जाते हैं जिसमें किसी विशेष कुंजियों वाले बाइनरी सर्च ट्री कम संग्रहीत होते हैं जो बाइनरी सर्च को संतुष्ट करते हैं।<ref name="reema18">{{cite book|title= सी का उपयोग कर डेटा संरचनाएं|date=13 October 2018|edition=2|first=Reema|last=Thareja|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|isbn= 9780198099307|url-access=subscription|chapter=Hashing and Collision}}</ref>{{rp|p=298}}<ref name="algo_cormen">{{cite book|last1=Cormen|first1=Thomas H. |author-link1=Thomas H. Cormen|last2=Leiserson|first2=Charles E. |author-link2=Charles E. Leiserson|last3=Rivest|first3=Ronald L. |author-link3=Ronald L. Rivest|author-link4=Clifford Stein|first4=Clifford |last4=Stein|url=https://mitpress.mit.edu/books/introduction-algorithms-second-edition|title=एल्गोरिदम का परिचय|edition=2nd|year=2001|publisher=[[MIT Press]]|isbn=0-262-03293-7}}</ref>{{rp|287}} | |||
[[खोज एल्गोरिदम|खोज प्रारूप]] को छोटा करने में | [[खोज एल्गोरिदम|खोज प्रारूप]] को छोटा करने में बाइनरी सर्च ट्री भी प्रभावशाली हैं। इस प्रकार कार्यान्वित आदेश और पहचान करने की आवश्यकता नहीं है जबकि बीएसटी की खोज जटिलता के उस क्रम पर निर्भर करती है जिसमें नोड्स डाले और हटाए जाते हैं जिससे कि खराब स्थिति बाइनरी सर्च ट्री में क्रमिक संचालन अर्धपतन का कारण बन सकता है और संरचना की तरह एक एकल [[लिंक्ड सूची]] बना सकता है इस प्रकार सूची के रूप में सबसे खराब स्थिति वाली जटिलता में संग्रहित किया जाता है।<ref>{{cite journal|journal=[[The Computer Journal]]|volume=25|issue=1|date=1 February 1982|doi=10.1093/comjnl/25.1.158|author1=R. A. Frost|author2=M. M. Peterson|page=158|url=https://academic.oup.com/comjnl/article/25/1/158/527326|publisher=[[Oxford University Press]]|title=A Short Note on Binary Search Trees}}</ref>{{r}} | ||
बाइनरी सर्च ट्री भी एक मूलभूत डेटा संरचना है जिसका उपयोग अमूर्त डेटा संरचनाओं जैसे सेट कंप्यूटर विज्ञान और साहचर्य सारणियों के निर्माण में किया जाता है। | |||
== संचालन == | == संचालन == | ||
===खोजना=== | ===खोजना=== | ||
एक विशिष्ट कुंजी के लिए | एक विशिष्ट कुंजी के लिए बाइनरी सर्च ट्री को क्रमादेशित किया जाता है तथा पुनरावर्तन या पुनरावृत्ति की गणना की जाती है। | ||
बाइनरी सर्च ट्री को डेटा संरचना में लकड़ी की जांच से खोज शुरू होती है अगर सर्च ट्री नल बिन्दु कुंजी रूट के बराबर है तो खोज सफल होती है और नोड वापस आ सकता है। यदि कुंजी रूट से कम है तो खोज बाएँ ट्री की जाँच करके आगे बढ़ती है इसी तरह यदि कुंजी रूट से अधिक है तो खोज हो चुकी होती है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कुंजी मिल नहीं जाती या शेष सर्च ट्री नहीं मिल जाते यदि खोजी गई कुंजी नहीं मिलती तो कुंजी सर्च ट्री में नहीं है।{{r}} | |||
==== पुनरावर्ती खोज ==== | ==== पुनरावर्ती खोज ==== | ||
| Line 39: | Line 39: | ||
==== पुनरावृत्त खोज ==== | ==== पुनरावृत्त खोज ==== | ||
खोज के पुनरावर्ती संस्करण को थोड़ी देर में | खोज के पुनरावर्ती संस्करण को थोड़ी देर में नियंत्रित किया जा सकता है अधिकांश मशीनों पर पुनरावृत्त संस्करण कंप्यूटर प्रदर्शन पाया जाता है।<ref name="algo_cormen" />{{rp|291}} | ||
इसमें खोज के कुछ [[ लसीका नोड |लसीका नोड]] होते हैं बीएसटी खोज की दौड़ जटिल है जबकि बीएसटी खोज की सबसे खराब स्थिति है बीएसटी में नोड्स की कुल संख्या एन है क्योंकि एक असंतुलित बीएसटी एक लिंक्ड सूची में खराब हो | इसमें खोज के कुछ [[ लसीका नोड |लसीका नोड]] होते हैं बीएसटी खोज की दौड़ जटिल है जबकि बीएसटी खोज की सबसे खराब स्थिति है बीएसटी में नोड्स की कुल संख्या एन है क्योंकि एक असंतुलित बीएसटी एक लिंक्ड सूची में खराब हो सकती है जबकि बीटीएस [[ऊँचाई-संतुलित वृक्ष|ऊँचाई-संतुलित सर्च ट्री]] है ।<ref name="algo_cormen" />{{rp}} | ||
==== पूर्ववर्ती उत्तराधिकारी ==== | ==== पूर्ववर्ती उत्तराधिकारी ==== | ||
कुछ कार्यों के लिए एक नोड दिया गया जिसके उत्तराधिकारी या पूर्ववर्ती का पता लगाना अत्यंत महत्वपूर्ण है | कुछ कार्यों के लिए एक नोड दिया गया जिसके उत्तराधिकारी या पूर्ववर्ती का पता लगाना अत्यंत महत्वपूर्ण है जबकि बीएसटी की सभी कुंजियाँ अलग-अलग हैं तथा एक नोड के उत्तराधिकारी हैं बीएसटी में सबसे छोटी कुंजी वाला नोड एक्स है दूसरी ओर एक नोड के पूर्ववर्ती बीएसटी में सबसे बड़ी कुंजी से छोटा नोड एक्स है नोड के उत्तराधिकारी और पूर्ववर्ती को खोजने के लिए निम्नलिखित स्यूडोकोड की प्रयोग किया जाता है। | ||
<ref>{{cite web|url=https://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-url=https://web.archive.org/web/20210413045057/http://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-date=13 April 2021|page=12|publisher=[[University of Texas at Arlington]]|access-date=17 May 2021|url-status=live|title=एल्गोरिदम का डिजाइन और विश्लेषण|author=Junzhou Huang}}</ref><ref>{{cite web |author=Ray |first=Ray |title=बाइनरी सर्च ट्री|url=https://cs.lmu.edu/~ray/notes/binarysearchtrees/ |access-date=17 May 2022 |publisher=[[Loyola Marymount University]], Department of Computer Science}}</ref><ref name="algo_cormen" />{{rp}} | <ref>{{cite web|url=https://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-url=https://web.archive.org/web/20210413045057/http://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-date=13 April 2021|page=12|publisher=[[University of Texas at Arlington]]|access-date=17 May 2021|url-status=live|title=एल्गोरिदम का डिजाइन और विश्लेषण|author=Junzhou Huang}}</ref><ref>{{cite web |author=Ray |first=Ray |title=बाइनरी सर्च ट्री|url=https://cs.lmu.edu/~ray/notes/binarysearchtrees/ |access-date=17 May 2022 |publisher=[[Loyola Marymount University]], Department of Computer Science}}</ref><ref name="algo_cormen" />{{rp}} | ||
बीएसटी में एक नोड खोजने | बीएसटी में एक नोड खोजने के लिए संचालन जिसकी कुंजी सीमा अधिकतम या न्यूनतम है यह कुछ कार्यों में महत्वपूर्ण हैं जैसे कि उत्तराधिकारी और नोड्स के पूर्ववर्ती का निर्धारण करना संचालन के लिए स्यूडोकोड महत्वपूर्ण हैं।<ref name="algo_cormen" />{{rp|291–292}} | ||
=== प्रविष्टि === | === प्रविष्टि === | ||
सम्मिलन और विलोपन संचालन बीएसटी प्रतिनिधित्व को गतिशील रूप से बदलने का कारण बनते हैं डेटा संरचना को इस तरह से संशोधित किया जाता है कि बीएसटी के गुण बने रहें | सम्मिलन और विलोपन संचालन बीएसटी प्रतिनिधित्व को गतिशील रूप से बदलने का कारण बनते हैं डेटा संरचना को इस तरह से संशोधित किया जाता है जिससे कि बीएसटी के गुण बने रहें बीएसटी में [[पत्ती के नोड्स]] के रूप में नए नोड डाले जाते हैं।<ref name="algo_cormen" />{{rp}}जो सम्मिलित ऑपरेशन की प्रविष्टि करते हैं।<ref name="algo_cormen" />{{rp}} | ||
=== हटाना === | === हटाना === | ||
यह एक नोड का विलोपन है जो एक | यह एक नोड का विलोपन है जो एक बाइनरी सर्च ट्री से बीएसटी की तीन स्थितियों का पालन करते हैं। {{r}} | ||
# | # माना डी एक पत्ती है जो डी का मूल बिन्दु है डी पेड़ से हटा दिया जाता है। | ||
# अगर डी एक एकल विद्यार्थी है तो बच्चा बाएँ या दाएँ बच्चे के रूप में उन्नत करेगा डी माता-पिता की स्थिति के आधार पर कार्य करता है अंजीर में दिखाया गया है कि भाग ए और भाग बी और डी पेड़ से हटा दिया जाता है। | # अगर डी एक एकल विद्यार्थी है तो बच्चा बाएँ या दाएँ बच्चे के रूप में उन्नत करेगा डी माता-पिता की स्थिति के आधार पर कार्य करता है जैसे अंजीर में दिखाया गया है कि भाग ए और भाग बी और डी पेड़ से हटा दिया जाता है। | ||
# अगर डी का उत्तराधिकारी एक बाएँ और दाएँ दोनों बच्चे हैं ई जिसके पास कोई बच्चा नहीं है तो इस स्थिति में क्या करेगा। | # अगर डी का उत्तराधिकारी एक बाएँ और दाएँ दोनों बच्चे हैं ई जिसके पास कोई बच्चा नहीं है तो इस स्थिति में वह क्या करेगा। | ||
##अगर डी एस का दायां बच्चा ऊंचा हो जाता है तो ई के बॉंये बच्चे किस बिन्दु पर ले जाया | ##अगर डी एस का दायां बच्चा ऊंचा हो जाता है तो ई के बॉंये बच्चे किस बिन्दु पर ले जाया जायेगा। | ||
## | ## | ||
[[File:AVL-tree-delete.svg|600px|नोड <math>\mathsf{D}</math> हटाने के लिए 2 बच्चे हैं]] | [[File:AVL-tree-delete.svg|600px|नोड <math>\mathsf{D}</math> हटाने के लिए 2 बच्चे हैं]] | ||
{{clear}} | {{clear}} | ||
निम्नलिखित स्यूडोकोड | निम्नलिखित स्यूडोकोड बाइनरी सर्च ट्री में विलोपन ऑपरेशन को लागू करता है।{{r}} | ||
| Line 70: | Line 70: | ||
{{Main article}} | {{Main article}} | ||
{{see also|Threaded binary tree}} | {{see also|Threaded binary tree}} | ||
एक बीएसटी तीन बुनियादी प्रारूप के माध्यम से | एक बीएसटी तीन बुनियादी प्रारूप के माध्यम से [[ट्री ट्रैवर्सल|यात्रा]] हो सकती है [[इनऑर्डर ट्रैवर्सल|यात्रा में आदेश]], [[प्री-ऑर्डर ट्रैवर्सल|उप आदेशिक यात्रा]] और [[पोस्ट-ऑर्डर ट्रैवर्सल|पोस्ट आदेश यात्रायें]] भी सम्मिलित हैं।<ref name="algo_cormen" />{{rp}} | ||
* बाएं | * बाएं सर्च ट्री से नोड्स पहले देखे जाते हैं उसके बाद रूट देखे जाते हैं। | ||
*जड़ को पहले बहाया जाता है उसके बाद बाएँ और दाएँ | *जड़ को पहले बहाया जाता है उसके बाद बाएँ और दाएँ सर्च ट्री को देखा जाता है। | ||
* बाएं | * बाएं सर्च ट्री से नोड्स पहले देखे जाते हैं। | ||
== संतुलित | == संतुलित बाइनरी सर्च ट्री == | ||
{{Main|Self-balancing binary search tree}} | {{Main|Self-balancing binary search tree}} | ||
पुनर्संतुलन के बिना | पुनर्संतुलन के बिना बाइनरी सर्च ट्री में सम्मिलित या विलोपन अर्धपतन का कारण बन सकता है जिसके परिणामस्वरूप ऊँचाई होती है एक रेखीय खोज की तुलना में सर्च ट्री को संतुलित और ऊँचाई से घेरे रखना होता है चयनित प्रारूप जटिलता के लिए बाइनरी सर्च ट्री की ऊंचाई को बनाए रखने के लिए बनावट किए गए ट्री के अद्यतन संचालन के दौरान इसे स्व-संतुलन तंत्र द्वारा प्राप्त किया जा सकता है।<ref name="Knuth98" /><ref name="peter11">{{cite book|publisher=[[Cambridge University Press]]|url=https://www.cambridge.org/core/books/advanced-data-structures/D56E2269D7CEE969A3B8105AD5B9254C|title=उन्नत डेटा संरचना|date=January 2011|isbn=9780511800191|doi=10.1017/CBO9780511800191|first=Peter|last=Brass}}</ref>{{rp}} | ||
=== ऊंचाई-संतुलित | === ऊंचाई-संतुलित ट्री === | ||
एक | एक सर्च ट्री ऊँचाई-संतुलित में होता है यदि बाइनरी सर्च ट्री की ऊँचाइयों को एक स्थिर कारक द्वारा संबंधित होने दिया जाता है। यह संपत्ति एवीएल ट्री द्वारा पेश की गई थी और लाल-काले ट्री द्वारा जारी रखी गई थी।{{r}} जड़ से संशोधित पत्ती तक पथ पर सभी की ऊंचाई को देखी जानी चाहिए और संभवतया ट्री में प्रत्येक डाल को हटाने के लिए सही किया जाना चाहिए।{{r|peter11|pp=52}} | ||
=== वजन-संतुलित | === वजन-संतुलित ट्री === | ||
{{main|Weight-balanced tree}} | {{main|Weight-balanced tree}} | ||
भार-संतुलित | भार-संतुलित ट्री में संतुलित ट्री की कसौटी की पत्तियों की संख्या है बाएँ और दाएँ सर्च ट्री का वजन सबसे अधिक होता है <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 conference|url=https://archive.org/details/verylargedatabas0000inte|first1=Tobin J.|last1=Lehman|first2=Michael J.|last2=Carey|title=मेन मेमोरी डेटाबेस मैनेजमेंट सिस्टम्स के लिए इंडेक्स स्ट्रक्चर्स का अध्ययन|location=Kyoto|date=25–28 August 1986|conference=Twelfth International Conference on Very Large Databases (VLDB 1986)|isbn=0-934613-18-4|url-access=registration}}</ref> <ref>{{Citation | contribution=Randomized Search Trees | first1=Cecilia R. | last1=Aragon | first2=Raimund | last2=Seidel | contribution-url=http://faculty.washington.edu/aragon/pubs/rst89.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://faculty.washington.edu/aragon/pubs/rst89.pdf |archive-date=2022-10-09 |url-status=live | title=Proc. 30th Symp. Foundations of Computer Science (FOCS 1989) | pages=540–545 | year=1989 | doi=10.1109/SFCS.1989.63531 | isbn=0-8186-1982-1 | publisher=IEEE Computer Society Press | location=Washington, D.C.| title-link=Symposium on Foundations of Computer Science }}</ref> रेड-ब्लैक ट्री<ref name="Cormen2001">{{Anchor|Cormen}}{{Cite book |title=Introduction to Algorithms |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |edition=second |publisher=MIT Press |year=2001 |isbn=978-0-262-03293-3 |chapter=Red–Black Trees |pages=[https://archive.org/details/introductiontoal00corm_691/page/n735 273]–301 |title-link=Introduction to Algorithms }}</ref> भी होते हैं। | ||
| Line 97: | Line 97: | ||
=== क्रमबद्ध करें === | === क्रमबद्ध करें === | ||
{{Main article|Tree sort}} | {{Main article|Tree sort}} | ||
बाइनरी सर्च ट्री का उपयोग में ट्री का प्रारूप छोटा किया जाता है जहां सभी तत्वों को एक ही बार में डाला जाता है। | |||
| Line 107: | Line 107: | ||
=== प्राथमिकता पंक्ति संचालन === | === प्राथमिकता पंक्ति संचालन === | ||
{{main|Priority queue}} | {{main|Priority queue}} | ||
बाइनरी सर्च ट्री का उपयोग [[प्राथमिकता कतार|प्राथमिक पंक्ति]] को लागू करने में किया जाता है कुंजी को प्राथमिकताओं के रूप में उपयोग करते हुए पंक्ति में नए तत्व में जोड़ना नियमित बीएसटी सम्मिलन ऑपरेशन का अनुसरण करता है लेकिन निष्कासन ऑपरेशन प्राथमिकता पंक्ति के प्रकार पर निर्भर करता है।<ref>{{cite web|publisher=[[Cornell University]], [[Cornell University College of Engineering|Department of Computer Science]]|first=Andrew|last=Myers|title=CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps|url=https://www.cs.cornell.edu/courses/cs4120/2016sp/lectures/lec_heaps/|archive-date=21 October 2021|url-status=live|archive-url=https://web.archive.org/web/20211021202727/https://www.cs.cornell.edu/courses/cs4120/2016sp/lectures/lec_heaps/|access-date=21 October 2021}} | |||
</ref> | </ref> | ||
* यदि यह एक आरोही क्रम प्राथमिक पंक्ति है तो सबसे कम प्राथमिकता वाले तत्व को बीएसटी के बाईं ओर यात्रियों के माध्यम से हटाया जाता है। | * यदि यह एक आरोही क्रम की प्राथमिक पंक्ति है तो सबसे कम प्राथमिकता वाले तत्व को बीएसटी के बाईं ओर यात्रियों के माध्यम से हटाया जाता है। | ||
* यदि यह अवरोही क्रम की प्राथमिक पंक्ति है तो उच्चतम प्राथमिकता वाले तत्व को बीएसटी के दाईं ओर यात्रियों के माध्यम से हटाया जाता है। | * यदि यह अवरोही क्रम की प्राथमिक पंक्ति है तो उच्चतम प्राथमिकता वाले तत्व को बीएसटी के दाईं ओर यात्रियों के माध्यम से हटाया जाता है। | ||
Revision as of 08:13, 14 March 2023
| Time complexity in big O notation | ||||
|---|---|---|---|---|
| ||||
कम्प्यूटर विज्ञान एक बाइनरी सर्च ट्री है बीएसटी जिसे क्रमांक या चयनित ट्री भी कहा जाता है एक जड़ वाला चयनित ट्री डेटा संरचना है जिसमें आंतरिक कुंजी बाएं सर्च ट्री की सभी कुंजियों से अधिक नहीं होती हैं तथा कम होती हैं यह दाहिने सर्च ट्री की तुलना में चयनित सर्च ट्री पर संचालन की समय जटिलता सीधे ट्री की ऊंचाई के समानुपाती होती है।
चयनित सर्च ट्री डेटा कार्यक्रम को तेजी से देखने जोड़ने और हटाने के लिए चयनित खोज कलनविधि की अनुमति देता है क्योंकि बीएसटी में प्रोप इस तरह रखे गए हैं कि प्रत्येक तुलना शेष सर्च ट्री के आधे हिस्से को छोड़ देती है प्रदर्शन खोजना द्विआधारी लघुगणक के समानुपाती होता है विवरण किए गए डेटा के कुशल भंडारण की समस्या के लिए 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]
पूर्ववर्ती उत्तराधिकारी
कुछ कार्यों के लिए एक नोड दिया गया जिसके उत्तराधिकारी या पूर्ववर्ती का पता लगाना अत्यंत महत्वपूर्ण है जबकि बीएसटी की सभी कुंजियाँ अलग-अलग हैं तथा एक नोड के उत्तराधिकारी हैं बीएसटी में सबसे छोटी कुंजी वाला नोड एक्स है दूसरी ओर एक नोड के पूर्ववर्ती बीएसटी में सबसे बड़ी कुंजी से छोटा नोड एक्स है नोड के उत्तराधिकारी और पूर्ववर्ती को खोजने के लिए निम्नलिखित स्यूडोकोड की प्रयोग किया जाता है।
बीएसटी में एक नोड खोजने के लिए संचालन जिसकी कुंजी सीमा अधिकतम या न्यूनतम है यह कुछ कार्यों में महत्वपूर्ण हैं जैसे कि उत्तराधिकारी और नोड्स के पूर्ववर्ती का निर्धारण करना संचालन के लिए स्यूडोकोड महत्वपूर्ण हैं।[10]: 291–292
प्रविष्टि
सम्मिलन और विलोपन संचालन बीएसटी प्रतिनिधित्व को गतिशील रूप से बदलने का कारण बनते हैं डेटा संरचना को इस तरह से संशोधित किया जाता है जिससे कि बीएसटी के गुण बने रहें बीएसटी में पत्ती के नोड्स के रूप में नए नोड डाले जाते हैं।[10]जो सम्मिलित ऑपरेशन की प्रविष्टि करते हैं।[10]
हटाना
यह एक नोड का विलोपन है जो एक बाइनरी सर्च ट्री से बीएसटी की तीन स्थितियों का पालन करते हैं। Cite error: Invalid <ref> tag; refs with no name must have content
- माना डी एक पत्ती है जो डी का मूल बिन्दु है डी पेड़ से हटा दिया जाता है।
- अगर डी एक एकल विद्यार्थी है तो बच्चा बाएँ या दाएँ बच्चे के रूप में उन्नत करेगा डी माता-पिता की स्थिति के आधार पर कार्य करता है जैसे अंजीर में दिखाया गया है कि भाग ए और भाग बी और डी पेड़ से हटा दिया जाता है।
- अगर डी का उत्तराधिकारी एक बाएँ और दाएँ दोनों बच्चे हैं ई जिसके पास कोई बच्चा नहीं है तो इस स्थिति में वह क्या करेगा।
- अगर डी एस का दायां बच्चा ऊंचा हो जाता है तो ई के बॉंये बच्चे किस बिन्दु पर ले जाया जायेगा।
निम्नलिखित स्यूडोकोड बाइनरी सर्च ट्री में विलोपन ऑपरेशन को लागू करता है।Cite error: Invalid <ref> tag; refs with no name must have content
यात्रीगण
Error: no page names specified (help).
एक बीएसटी तीन बुनियादी प्रारूप के माध्यम से यात्रा हो सकती है यात्रा में आदेश, उप आदेशिक यात्रा और पोस्ट आदेश यात्रायें भी सम्मिलित हैं।[10]
- बाएं सर्च ट्री से नोड्स पहले देखे जाते हैं उसके बाद रूट देखे जाते हैं।
- जड़ को पहले बहाया जाता है उसके बाद बाएँ और दाएँ सर्च ट्री को देखा जाता है।
- बाएं सर्च ट्री से नोड्स पहले देखे जाते हैं।
संतुलित बाइनरी सर्च ट्री
पुनर्संतुलन के बिना बाइनरी सर्च ट्री में सम्मिलित या विलोपन अर्धपतन का कारण बन सकता है जिसके परिणामस्वरूप ऊँचाई होती है एक रेखीय खोज की तुलना में सर्च ट्री को संतुलित और ऊँचाई से घेरे रखना होता है चयनित प्रारूप जटिलता के लिए बाइनरी सर्च ट्री की ऊंचाई को बनाए रखने के लिए बनावट किए गए ट्री के अद्यतन संचालन के दौरान इसे स्व-संतुलन तंत्र द्वारा प्राप्त किया जा सकता है।[4][14]
ऊंचाई-संतुलित ट्री
एक सर्च ट्री ऊँचाई-संतुलित में होता है यदि बाइनरी सर्च ट्री की ऊँचाइयों को एक स्थिर कारक द्वारा संबंधित होने दिया जाता है। यह संपत्ति एवीएल ट्री द्वारा पेश की गई थी और लाल-काले ट्री द्वारा जारी रखी गई थी।Cite error: Invalid <ref> tag; refs with no name must have content जड़ से संशोधित पत्ती तक पथ पर सभी की ऊंचाई को देखी जानी चाहिए और संभवतया ट्री में प्रत्येक डाल को हटाने के लिए सही किया जाना चाहिए।[14]: 52
वजन-संतुलित ट्री
भार-संतुलित ट्री में संतुलित ट्री की कसौटी की पत्तियों की संख्या है बाएँ और दाएँ सर्च ट्री का वजन सबसे अधिक होता है [15]Cite error: Invalid <ref> tag; refs with no name must have content जबकि अंतर अनुपात से बंधा हुआ है अल्फा संतुलन की स्थिति के बाद नहीं रखा जा सकता सर्च ट्री संतुलन की स्थिति का एक पूरा परिवार होता है जहां प्रत्येक सर्च ट्री में कम से कम एक अंश होता है।[14]: 62
प्रकार
कई स्व-संतुलित बाइनरी सर्च ट्री हैं जिनमें [16] [17] रेड-ब्लैक ट्री[18] भी होते हैं।
अनुप्रयोगों के उदाहरण
क्रमबद्ध करें
बाइनरी सर्च ट्री का उपयोग में ट्री का प्रारूप छोटा किया जाता है जहां सभी तत्वों को एक ही बार में डाला जाता है।
प्राथमिकता पंक्ति संचालन
बाइनरी सर्च ट्री का उपयोग प्राथमिक पंक्ति को लागू करने में किया जाता है कुंजी को प्राथमिकताओं के रूप में उपयोग करते हुए पंक्ति में नए तत्व में जोड़ना नियमित बीएसटी सम्मिलन ऑपरेशन का अनुसरण करता है लेकिन निष्कासन ऑपरेशन प्राथमिकता पंक्ति के प्रकार पर निर्भर करता है।[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.
- ↑ Thareja, Reema (13 October 2018). "Hashing and Collision". सी का उपयोग कर डेटा संरचनाएं (2 ed.). Oxford University Press. ISBN 9780198099307.
- ↑ 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.
- ↑ 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 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.
बाहरी संबंध
Wikimedia Commons has media related to Binary search trees.
- 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)
