ट्री (डेटा संरचना): Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Abstract data type simulating a hierarchical tree structure and represented as a set of linked nodes}} {{Distinguish|text=Trie, a specific type of tree...")
 
No edit summary
Line 1: Line 1:
{{Short description|Abstract data type simulating a hierarchical tree structure and represented as a set of linked nodes}}
{{Short description|Abstract data type simulating a hierarchical tree structure and represented as a set of linked nodes}}
{{Distinguish|text=[[Trie]], a specific type of tree data structure}}
{{Distinguish|text=[[Trie]], a specific type of tree data structure}}
[[File:Tree (computer science).svg|right|thumb|इस अवर्गीकृत पेड़ के गैर-अद्वितीय मान हैं और यह गैर-द्विआधारी है, क्योंकि बच्चों की संख्या एक (जैसे नोड 9) से तीन (नोड 7) तक भिन्न होती है। रूट नोड, शीर्ष पर, कोई पैरेंट नहीं है।]][[कंप्यूटर विज्ञान]] में, एक पेड़ एक व्यापक रूप से इस्तेमाल किया जाने वाला अमूर्त डेटा प्रकार है जो जुड़े हुए [[नोड (कंप्यूटर विज्ञान)]] के एक सेट के साथ एक पदानुक्रमित पेड़ संरचना का प्रतिनिधित्व करता है। पेड़ में प्रत्येक नोड को कई बच्चों (पेड़ के प्रकार के आधार पर) से जोड़ा जा सकता है, लेकिन 'रूट' नोड को छोड़कर, जिसका कोई माता-पिता नहीं है, को ठीक से एक माता-पिता से जोड़ा जाना चाहिए। इन बाधाओं का मतलब है कि कोई चक्र या लूप नहीं है (कोई भी नोड उसका स्वयं का पूर्वज नहीं हो सकता है), और यह भी कि प्रत्येक बच्चे को अपने स्वयं के सबट्री के रूट नोड की तरह माना जा सकता है, जिससे पुनरावृत्ति [[ट्री ट्रैवर्सल]] के लिए एक उपयोगी तकनीक बन जाती है। [[रैखिक डेटा संरचना]]ओं के विपरीत, कई पेड़ों को एक सीधी रेखा में पड़ोसी नोड्स के बीच संबंधों द्वारा प्रदर्शित नहीं किया जा सकता है।
[[File:Tree (computer science).svg|right|thumb|इस अवर्गीकृत वृक्ष के गैर-अद्वितीय मान हैं और यह गैर-द्विआधारी है, क्योंकि बच्चों की संख्या एक (जैसे नोड 9) से तीन (नोड 7) तक भिन्न होती है। मूल नोड, शीर्ष पर, कोई पैरेंट नहीं है।]][[कंप्यूटर विज्ञान]] में, एक वृक्ष एक व्यापक रूप से उपयोग  किया जाने वाला संक्षेप डेटा प्रकार है जो जुड़े हुए [[नोड (कंप्यूटर विज्ञान)]] के एक समूह के साथ एक पदानुक्रमित वृक्ष संरचना का प्रतिनिधित्व करता है। वृक्ष में प्रत्येक नोड को कई बच्चों (वृक्ष के प्रकार के आधार पर) से जोड़ा जा सकता है, परन्तु 'मूल' नोड को छोड़कर, जिसका कोई माता-पिता नहीं है, को ठीक से एक माता-पिता से जोड़ा जाना चाहिए। इन बाधाओं का तात्पर्य है कि कोई चक्र या लूप नहीं है (कोई भी नोड उसका स्वयं का पूर्वज नहीं हो सकता है), और यह भी कि प्रत्येक बच्चे को अपने स्वयं के उपवृक्ष के मूल नोड के जैसे माना जा सकता है, जिससे पुनरावृत्ति [[ट्री ट्रैवर्सल|वृक्ष  पथक्रमण]] के लिए एक उपयोगी तकनीक बन जाती है। [[रैखिक डेटा संरचना|रैखिक डेटा संरचनाओं]] के विपरीत, कई वृक्षों को एक सीधी रेखा में निकटतम  नोड्स के बीच संबंधों द्वारा प्रदर्शित नहीं किया जा सकता है।


[[बाइनरी ट्री]] आमतौर पर इस्तेमाल किया जाने वाला प्रकार है, जो प्रत्येक माता-पिता के लिए अधिकतम दो बच्चों की संख्या को सीमित करता है। जब बच्चों का क्रम निर्दिष्ट किया जाता है, तो यह डेटा संरचना [[ग्राफ सिद्धांत]] में एक आदेशित पेड़ से मेल खाती है। अन्य डेटा के लिए एक मूल्य या सूचक पेड़ में प्रत्येक नोड के साथ जुड़ा हो सकता है, या कभी-कभी केवल 'पत्ती नोड्स' के साथ जुड़ा हो सकता है, जिसमें कोई संतान नहीं है।
[[बाइनरी ट्री|द्विआधारी वृक्ष]] सामान्यतः  उपयोग  किया जाने वाला प्रकार है, जो प्रत्येक माता-पिता के लिए अधिकतम दो बच्चों की संख्या को सीमित करता है। जब बच्चों का क्रम निर्दिष्ट किया जाता है, तो यह डेटा संरचना [[ग्राफ सिद्धांत]] में एक क्रमिक वृक्ष से मेल खाती है। अन्य डेटा के लिए एक मूल्य या सूचक वृक्ष में प्रत्येक नोड के साथ जुड़ा हो सकता है, या कभी-कभी मात्र  'पत्ती नोड्स' के साथ जुड़ा हो सकता है, जिसमें कोई संतान नहीं है।


[[सार डेटा प्रकार]] को कई तरीकों से प्रदर्शित किया जा सकता है, जिसमें माता-पिता की सूची बच्चों के लिए पॉइंटर्स, माता-पिता के पॉइंटर्स वाले बच्चों की सूची, या नोड्स की सूची और माता-पिता-बाल संबंधों की एक अलग सूची (एक विशिष्ट प्रकार) शामिल है। [[निकटता सूची]] की)। प्रतिनिधित्व भी अधिक जटिल हो सकते हैं, उदाहरण के लिए प्रदर्शन के लिए [[डाटाबेस इंडेक्स]] या पूर्वजों की सूची का उपयोग करना।
[[सार डेटा प्रकार|संक्षेप डेटा प्रकार]] को कई विधियों से प्रदर्शित किया जा सकता है, जिसमें माता-पिता की सूची बच्चों के लिए संकेत, माता-पिता के संकेत वाले बच्चों की सूची, या नोड्स की सूची और माता-पिता-बाल संबंधों की एक अलग सूची (एक विशिष्ट प्रकार [[निकटता सूची]] )सम्मिलित है। अभ्यावेदन भी अधिक जटिल हो सकते हैं, उदाहरण के लिए निष्पादन के लिए [[डाटाबेस इंडेक्स|डाटाबेस अनुक्रमणिका]] या पूर्वजों की सूची का उपयोग करना।


कंप्यूटिंग में उपयोग किए जाने वाले पेड़ समान हैं लेकिन पेड़ (ग्राफ सिद्धांत), [[पेड़ (सेट सिद्धांत)]], और पेड़ (वर्णनात्मक सेट सिद्धांत) के गणितीय निर्माणों से भिन्न हो सकते हैं।
कंप्यूटिंग में उपयोग किए जाने वाले वृक्ष समान हैं परन्तु वृक्ष (ग्राफ सिद्धांत), [[पेड़ (सेट सिद्धांत)|वृक्ष (समूह सिद्धांत)]], और वृक्ष (वर्णनात्मक समूह सिद्धांत) के गणितीय निर्माणों से भिन्न हो सकते हैं।


== अनुप्रयोग ==
== अनुप्रयोग ==
पेड़ों का उपयोग आमतौर पर अनुप्रयोगों में पदानुक्रमित डेटा का प्रतिनिधित्व या हेरफेर करने के लिए किया जाता है जैसे:
वृक्षों का उपयोग सामान्यतः  अनुप्रयोगों में पदानुक्रमित डेटा का प्रतिनिधित्व या क्रमभंग करने के लिए किया जाता है जैसे:
* [[फाइल सिस्टम]] के लिए:
* [[फाइल सिस्टम|फाइल पद्धति]] के लिए:
** [[निर्देशिका संरचना]] का उपयोग उपनिर्देशिकाओं और फ़ाइलों को व्यवस्थित करने के लिए किया जाता है ([[प्रतीकात्मक लिंक]] गैर-ट्री ग्राफ़ बनाते हैं, जैसा कि एक ही फ़ाइल या निर्देशिका के लिए कई [[कड़ी कड़ी]] करते हैं)
** [[निर्देशिका संरचना]] का उपयोग उपनिर्देशिकाओं और फ़ाइलों को व्यवस्थित करने के लिए किया जाता है ([[प्रतीकात्मक लिंक]] गैर-वृक्ष ग्राफ़ बनाते हैं, जैसा कि एक ही फ़ाइल या निर्देशिका के लिए कई [[कड़ी कड़ी|दृढ़ लिंक]] करते हैं)
** स्टोरेज डिवाइस पर डेटा के ब्लॉक आवंटित करने और लिंक करने के लिए प्रयुक्त तंत्र
** स्टोरेज डिवाइस पर डेटा के खंड आवंटित करने और लिंक करने के लिए प्रयुक्त तंत्र
* क्लास पदानुक्रम या इनहेरिटेंस ट्री [[ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग]] में [[वर्ग (कंप्यूटर प्रोग्रामिंग)]] के बीच संबंधों को दर्शाता है; [[एकाधिक वंशानुक्रम]] गैर-वृक्ष रेखांकन उत्पन्न करता है
* वर्ग पदानुक्रम या वंशानुक्रम वृक्ष [[ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग]] में [[वर्ग (कंप्यूटर प्रोग्रामिंग)]] के बीच संबंधों को दर्शाता है; [[एकाधिक वंशानुक्रम]] गैर-वृक्ष रेखांकन उत्पन्न करता है
* कंप्यूटर भाषाओं के लिए [[सार वाक्य रचना का पेड़]]
* कंप्यूटर भाषाओं के लिए [[सार वाक्य रचना का पेड़|संक्षेप वाक्य रचना का वृक्ष]]
* [[प्राकृतिक भाषा प्रसंस्करण]]:
* [[प्राकृतिक भाषा प्रसंस्करण]]:
** [[पार्स पेड़]]
** [[पार्स पेड़|पदव्‍याख्‍या  वृक्ष]]
** एक [[उत्पादक व्याकरण]] में मॉडलिंग उच्चारण
** एक [[उत्पादक व्याकरण]] में मॉडलिंग उच्चारण
** वार्तालाप उत्पन्न करने के लिए [[संवाद वृक्ष]]
** वार्तालाप उत्पन्न करने के लिए [[संवाद वृक्ष]]
* [[XML]] और [[HTML]] दस्तावेज़ों के दस्तावेज़ ऑब्जेक्ट मॉडल (DOM ट्री)।
* [[XML|एक्सएमएल]] और [[HTML|एचटीएमएल]] दस्तावेज़ों के दस्तावेज़ ऑब्जेक्ट मॉडल (डीओएम वृक्ष)।
* [[खोज पेड़]] डेटा को एक तरह से स्टोर करता है जो ट्री ट्रैवर्सल के माध्यम से एक कुशल [[खोज एल्गोरिदम]] को संभव बनाता है
* [[खोज पेड़|खोज]] वृक्ष डेटा को एक वृक्ष से स्टोर करता है जो वृक्ष  पथक्रमण के माध्यम से एक कुशल [[खोज एल्गोरिदम]] को संभव बनाता है
** [[बाइनरी सर्च ट्री]] एक प्रकार का बाइनरी ट्री है
** [[बाइनरी सर्च ट्री|द्विआधारी सर्च वृक्ष]] एक प्रकार का द्विआधारी वृक्ष है
* डेटा के [[छँटाई एल्गोरिथ्म]] का प्रतिनिधित्व करना
* डेटा के [[छँटाई एल्गोरिथ्म]] का प्रतिनिधित्व करना
* [[कंप्यूटर जनित कल्पना]]:
* [[कंप्यूटर जनित कल्पना]]:
** स्पेस पार्टीशनिंग # डेटा स्ट्रक्चर्स, जिसमें [[बाइनरी स्पेस विभाजन]] शामिल है
** स्पेस पार्टीशनिंग # डेटा स्ट्रक्चर्स, जिसमें [[बाइनरी स्पेस विभाजन|द्विआधारी स्पेस विभाजन]] सम्मिलित है
** [[डिजिटल रचना]]
** [[डिजिटल रचना]]
* बार्न्स-हट सिमुलेशन का भंडारण | बार्न्स-हट के पेड़ आकाशगंगाओं का अनुकरण करते थे
* बार्न्स-हट सिमुलेशन का भंडारण | बार्न्स-हट के वृक्ष आकाशगंगाओं का अनुकरण करते थे
* कार्यान्वयन हीप (डेटा संरचना)
* कार्यान्वयन हीप (डेटा संरचना)
* [[नेस्टेड सेट]]
* [[नेस्टेड सेट|नेस्टेड समूह]]
* टैक्सोनॉमी (सामान्य)#एप्लिकेशन जैसे [[डेवी दशमलव वर्गीकरण]] जिसमें बढ़ते स्पेसिफिकेशंस के सेक्शन हों।
* टैक्सोनॉमी (सामान्य)#एप्लिकेशन जैसे [[डेवी दशमलव वर्गीकरण]] जिसमें बढ़ते स्पेसिफिकेशंस के सेक्शन हों।
* पदानुक्रमित लौकिक स्मृति
* पदानुक्रमित लौकिक स्मृति
Line 35: Line 35:
* [[पदानुक्रमित क्लस्टरिंग]]
* [[पदानुक्रमित क्लस्टरिंग]]


पेड़ों का उपयोग विभिन्न गणितीय संरचनाओं का प्रतिनिधित्व और हेरफेर करने के लिए किया जा सकता है, जैसे:
वृक्षों का उपयोग विभिन्न गणितीय संरचनाओं का प्रतिनिधित्व और क्रमभंग करने के लिए किया जा सकता है, जैसे:
* एक मनमाना [[ग्राफ (असतत गणित)]] के माध्यम से पथ | नोड-एंड-एज ग्राफ ([[मल्टीग्राफ]] सहित), कई रास्तों में उपयोग किए जाने वाले प्रत्येक ग्राफ नोड के लिए पेड़ में कई नोड बनाकर
* एक मनमाना [[ग्राफ (असतत गणित)]] के माध्यम से पथ | नोड-एंड-एज ग्राफ ([[मल्टीग्राफ]] सहित), कई रास्तों में उपयोग किए जाने वाले प्रत्येक ग्राफ नोड के लिए वृक्ष में कई नोड बनाकर
* कोई [[पदानुक्रम (गणित)]]
* कोई [[पदानुक्रम (गणित)]]


वृक्ष संरचनाओं का उपयोग अक्सर चीजों के बीच संबंधों को मैप करने के लिए किया जाता है, जैसे कि:
वृक्ष संरचनाओं का उपयोग अक्सर चीजों के बीच संबंधों को मैप करने के लिए किया जाता है, जैसे कि:
* अवयव और उप-घटक जिन्हें [[विस्फोट-दृश्य आरेखण]] में देखा जा सकता है
* अवयव और उप-घटक जिन्हें [[विस्फोट-दृश्य आरेखण]] में देखा जा सकता है
* [[सबरूटीन कॉल]] का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से सबरूटीन्स अन्य सबरूटीन्स को गैर-पुनरावर्ती रूप से कॉल करते हैं
* [[सबरूटीन कॉल|सबमूलीन कॉल]] का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से सबमूलीन्स अन्य सबमूलीन्स को गैर-पुनरावर्ती रूप से कॉल करते हैं
* [[विकास]] द्वारा प्रजातियों के बीच डीएनए की विरासत, of source code by software projects (e.g. [[:File:Linux_Distribution_Timeline_Dec._2020.svg|लिनक्स वितरण समयरेखा), विभिन्न प्रकार की कारों में डिज़ाइन आदि।
* [[विकास]] द्वारा प्रजातियों के बीच डीएनए की विरासत, of source code by software projects (e.g. [[:File:Linux_Distribution_Timeline_Dec._2020.svg|लिनक्स वितरण समयरेखा), विभिन्न प्रकार की कारों में डिज़ाइन आदि।
* पदानुक्रमित नामस्थानों की सामग्री
* पदानुक्रमित नामस्थानों की सामग्री


[[JSON]] और [[YAML]] दस्तावेज़ों को पेड़ों के रूप में माना जा सकता है, लेकिन आमतौर पर नेस्टेड [[सूची (सार डेटा प्रकार)]] और [[साहचर्य सरणी]] द्वारा प्रतिनिधित्व किया जाता है।
[[JSON]] और [[YAML]] दस्तावेज़ों को वृक्षों के रूप में माना जा सकता है, परन्तु सामान्यतः  नेस्टेड [[सूची (सार डेटा प्रकार)|सूची (संक्षेप डेटा प्रकार)]] और [[साहचर्य सरणी]] द्वारा प्रतिनिधित्व किया जाता है।


== शब्दावली ==
== शब्दावली ==
एक नोड (कंप्यूटर विज्ञान) एक संरचना है जिसमें डेटा और अन्य नोड्स के कनेक्शन हो सकते हैं, जिन्हें कभी-कभी किनारे या लिंक कहा जाता है। एक पेड़ में प्रत्येक नोड में शून्य या अधिक बच्चे के नोड होते हैं, जो पेड़ में इसके नीचे होते हैं (परंपरा के अनुसार, पेड़ों को 'वंशज' नीचे की ओर जाते हुए खींचा जाता है)। एक नोड जिसमें एक बच्चा होता है उसे बच्चे का मूल नोड (या [[सुपीरियर (पदानुक्रम)]]) कहा जाता है। शीर्षतम रूट नोड को छोड़कर, जिसमें कोई नहीं है, सभी नोड्स में बिल्कुल एक पैरेंट है। एक नोड में कई पूर्वज नोड हो सकते हैं, जैसे कि माता-पिता के माता-पिता। एक ही पैरेंट वाले चाइल्ड नोड सिबलिंग नोड होते हैं। आमतौर पर भाई-बहनों का एक क्रम होता है, जिसमें पहला पारंपरिक रूप से बाईं ओर खींचा जाता है। कुछ परिभाषाएँ एक पेड़ को कोई नोड नहीं होने देती हैं, जिस स्थिति में इसे ''खाली'' कहा जाता है।
एक नोड (कंप्यूटर विज्ञान) एक संरचना है जिसमें डेटा और अन्य नोड्स के कनेक्शन हो सकते हैं, जिन्हें कभी-कभी किनारे या लिंक कहा जाता है। एक वृक्ष में प्रत्येक नोड में शून्य या अधिक बच्चे के नोड होते हैं, जो वृक्ष में इसके नीचे होते हैं (परंपरा के अनुसार, वृक्षों को 'वंशज' नीचे की ओर जाते हुए खींचा जाता है)। एक नोड जिसमें एक बच्चा होता है उसे बच्चे का मूल नोड (या [[सुपीरियर (पदानुक्रम)]]) कहा जाता है। शीर्षतम मूल नोड को छोड़कर, जिसमें कोई नहीं है, सभी नोड्स में बिल्कुल एक पैरेंट है। एक नोड में कई पूर्वज नोड हो सकते हैं, जैसे कि माता-पिता के माता-पिता। एक ही पैरेंट वाले चाइल्ड नोड सिबलिंग नोड होते हैं। सामान्यतः  भाई-बहनों का एक क्रम होता है, जिसमें पहला पारंपरिक रूप से बाईं ओर खींचा जाता है। कुछ परिभाषाएँ एक वृक्ष को कोई नोड नहीं होने देती हैं, जिस स्थिति में इसे ''खाली'' कहा जाता है।


एक आंतरिक नोड (जिसे एक आंतरिक नोड के रूप में भी जाना जाता है, लघु या शाखा नोड के लिए इनोड) एक पेड़ का कोई भी नोड होता है जिसमें बच्चे के नोड होते हैं। इसी तरह, एक बाहरी नोड (जिसे बाहरी नोड, लीफ नोड या टर्मिनल नोड के रूप में भी जाना जाता है) कोई भी नोड होता है जिसमें चाइल्ड नोड नहीं होता है।
एक आंतरिक नोड (जिसे एक आंतरिक नोड के रूप में भी जाना जाता है, लघु या शाखा नोड के लिए इनोड) एक वृक्ष का कोई भी नोड होता है जिसमें बच्चे के नोड होते हैं। इसी वृक्ष, एक बाहरी नोड (जिसे बाहरी नोड, लीफ नोड या टर्मिनल नोड के रूप में भी जाना जाता है) कोई भी नोड होता है जिसमें चाइल्ड नोड नहीं होता है।


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


प्रत्येक गैर-रूट नोड को अपने स्वयं के सबट्री के रूट नोड के रूप में माना जा सकता है, जिसमें वह नोड और उसके सभी वंशज शामिल हैं।{{efn|This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no descendants).}}<ref>{{MathWorld|id=Subtree|title=Subtree}}</ref>
प्रत्येक गैर-मूल नोड को अपने स्वयं के उपवृक्ष के मूल नोड के रूप में माना जा सकता है, जिसमें वह नोड और उसके सभी वंशज सम्मिलित हैं।{{efn|This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no descendants).}}<ref>{{MathWorld|id=Subtree|title=Subtree}}</ref>
पेड़ों के साथ प्रयुक्त अन्य शब्द:
वृक्षों के साथ प्रयुक्त अन्य शब्द:
{{glossary}}
{{glossary}}
{{term|Neighbor}} {{defn|Parent or child.}}
{{term|Neighbor}} {{defn|Parent or child.}}
Line 73: Line 73:




== पेड़ों और गैर-वृक्षों के उदाहरण ==
== वृक्षों और गैर-वृक्षों के उदाहरण ==


{{multiple image
{{multiple image
Line 98: Line 98:
{{graph search algorithm}}
{{graph search algorithm}}
* सभी वस्तुओं की गणना करना
* सभी वस्तुओं की गणना करना
* एक पेड़ के एक खंड की गणना
* एक वृक्ष के एक खंड की गणना
* किसी वस्तु की खोज करना
* किसी वस्तु की खोज करना
* पेड़ पर एक निश्चित स्थान पर एक नया आइटम जोड़ना
* वृक्ष पर एक निश्चित स्थान पर एक नया आइटम जोड़ना
* किसी वस्तु को हटाना
* किसी वस्तु को हटाना
* [[प्रूनिंग (एल्गोरिदम)]]: एक पेड़ के पूरे खंड को हटाना
* [[प्रूनिंग (एल्गोरिदम)]]: एक वृक्ष के पूरे खंड को हटाना
* [[ग्राफ्टिंग (एल्गोरिदम)]]: एक पेड़ में एक पूरा खंड जोड़ना
* [[ग्राफ्टिंग (एल्गोरिदम)]]: एक वृक्ष में एक पूरा खंड जोड़ना
* किसी भी नोड के लिए रूट ढूँढना
* किसी भी नोड के लिए मूल ढूँढना
* दो नोड्स के [[सबसे कम सामान्य पूर्वज]] का पता लगाना
* दो नोड्स के [[सबसे कम सामान्य पूर्वज]] का पता लगाना


=== ट्रैवर्सल और खोज के तरीके ===
=== पथक्रमण और खोज के तरीके ===
{{Main article|Tree traversal}}
{{Main article|Tree traversal}}
माता-पिता और बच्चों के बीच संबंधों के माध्यम से एक पेड़ की वस्तुओं के माध्यम से कदम रखना, पेड़ पर चलना कहलाता है, और क्रिया पेड़ का '' चलना '' है। जब कोई पॉइंटर किसी विशेष नोड पर आता है, तो अक्सर एक ऑपरेशन किया जा सकता है। एक वॉक जिसमें प्रत्येक पैरेंट नोड को उसके बच्चों से पहले पार किया जाता है, उसे प्री-ऑर्डर वॉक कहा जाता है; एक वॉक जिसमें बच्चों को उनके संबंधित माता-पिता से पहले ट्रैवर्स किया जाता है, पोस्ट-ऑर्डर वॉक कहा जाता है; एक चाल जिसमें एक नोड का बायाँ सबट्री, फिर नोड स्वयं, और अंत में इसका दाहिना सबट्री ट्रैवर्स किया जाता है, इन-ऑर्डर ट्रैवर्सल कहलाता है। (यह अंतिम परिदृश्य, ठीक दो सबट्री, एक लेफ्ट सबट्री और एक राइट सबट्री का जिक्र करते हुए, विशेष रूप से एक बाइनरी ट्री मानता है।) एक लेवल-ऑर्डर वॉक प्रभावी रूप से एक पेड़ की संपूर्णता पर चौड़ाई-पहली खोज करता है; नोड्स को स्तर से पार किया जाता है, जहां पहले रूट नोड का दौरा किया जाता है, उसके बाद उसके प्रत्यक्ष बच्चे नोड्स और उनके भाई बहनों के बाद, उसके पोते नोड्स और उनके भाई बहनों आदि के बाद, जब तक पेड़ में सभी नोड्स का पता नहीं लगाया जाता है।
माता-पिता और बच्चों के बीच संबंधों के माध्यम से एक वृक्ष की वस्तुओं के माध्यम से कदम रखना, वृक्ष पर चलना कहलाता है, और क्रिया वृक्ष का '' चलना '' है। जब कोई पॉइंटर किसी विशेष नोड पर आता है, तो अक्सर एक ऑपरेशन किया जा सकता है। एक वॉक जिसमें प्रत्येक पैरेंट नोड को उसके बच्चों से पहले पार किया जाता है, उसे प्री-ऑर्डर वॉक कहा जाता है; एक वॉक जिसमें बच्चों को उनके संबंधित माता-पिता से पहले ट्रैवर्स किया जाता है, पोस्ट-ऑर्डर वॉक कहा जाता है; एक चाल जिसमें एक नोड का बायाँ उपवृक्ष, फिर नोड स्वयं, और अंत में इसका दाहिना उपवृक्ष ट्रैवर्स किया जाता है, इन-ऑर्डर पथक्रमण कहलाता है। (यह अंतिम परिदृश्य, ठीक दो उपवृक्ष, एक लेफ्ट उपवृक्ष और एक राइट उपवृक्ष का जिक्र करते हुए, विशेष रूप से एक द्विआधारी वृक्ष मानता है।) एक लेवल-ऑर्डर वॉक प्रभावी रूप से एक वृक्ष की संपूर्णता पर चौड़ाई-पहली खोज करता है; नोड्स को स्तर से पार किया जाता है, जहां पहले मूल नोड का दौरा किया जाता है, उसके बाद उसके प्रत्यक्ष बच्चे नोड्स और उनके भाई बहनों के बाद, उसके पोते नोड्स और उनके भाई बहनों आदि के बाद, जब तक वृक्ष में सभी नोड्स का पता नहीं लगाया जाता है।


== प्रतिनिधित्व ==
== प्रतिनिधित्व ==


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


नोड्स को एक [[सरणी डेटा संरचना]] में आइटम के रूप में भी संग्रहीत किया जा सकता है, उनके बीच संबंधों को सरणी में उनकी स्थिति द्वारा निर्धारित किया जाता है (जैसा कि [[द्विआधारी ढेर]] में)।
नोड्स को एक [[सरणी डेटा संरचना]] में आइटम के रूप में भी संग्रहीत किया जा सकता है, उनके बीच संबंधों को सरणी में उनकी स्थिति द्वारा निर्धारित किया जाता है (जैसा कि [[द्विआधारी ढेर]] में)।


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


आदेशित पेड़ों को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा एन्कोड किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।<ref name="Afanasiev2005">
क्रमिक वृक्षों को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा एन्कोड किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।<ref name="Afanasiev2005">
{{cite journal | title=PDL for ordered trees
{{cite journal | title=PDL for ordered trees
  | author1=L. Afanasiev
  | author1=L. Afanasiev
Line 139: Line 139:
== प्रकार सिद्धांत ==
== प्रकार सिद्धांत ==
{{unreferenced section|date=April 2022}}
{{unreferenced section|date=April 2022}}
सार डेटा प्रकार के रूप में, सार वृक्ष प्रकार {{mvar|T}} किसी प्रकार के मूल्यों के साथ {{mvar|E}} सार वन प्रकार का उपयोग करके परिभाषित किया गया है {{mvar|F}} (पेड़ों की सूची), कार्यों द्वारा:
संक्षेप डेटा प्रकार के रूप में, संक्षेप वृक्ष प्रकार {{mvar|T}} किसी प्रकार के मूल्यों के साथ {{mvar|E}} संक्षेप वन प्रकार का उपयोग करके परिभाषित किया गया है {{mvar|F}} (वृक्षों की सूची), कार्यों द्वारा:
: कीमत: {{mvar|T}} → {{mvar|E}}
: कीमत: {{mvar|T}} → {{mvar|E}}
: बच्चे: {{mvar|T}} → {{mvar|F}}
: बच्चे: {{mvar|T}} → {{mvar|F}}
Line 147: Line 147:
: मान (नोड ({{mvar|e}}, {{mvar|f}})) = {{mvar|e}}
: मान (नोड ({{mvar|e}}, {{mvar|f}})) = {{mvar|e}}
: बच्चे (नोड ({{mvar|e}}, {{mvar|f}})) = {{mvar|f}}
: बच्चे (नोड ({{mvar|e}}, {{mvar|f}})) = {{mvar|f}}
प्रकार के सिद्धांत के संदर्भ में, एक पेड़ एक [[पुनरावर्ती डेटा प्रकार]] है जिसे निर्माणकर्ताओं द्वारा परिभाषित किया गया है {{math|nil}} (खाली जंगल) और {{math|node}} (दिए गए मूल्य और बच्चों के साथ रूट नोड वाला पेड़)।
प्रकार के सिद्धांत के संदर्भ में, एक वृक्ष एक [[पुनरावर्ती डेटा प्रकार]] है जिसे निर्माणकर्ताओं द्वारा परिभाषित किया गया है {{math|nil}} (खाली जंगल) और {{math|node}} (दिए गए मूल्य और बच्चों के साथ मूल नोड वाला वृक्ष)।


== गणितीय शब्दावली ==
== गणितीय शब्दावली ==
{{unreferenced section|date=April 2022}}
{{unreferenced section|date=April 2022}}
एक पूरे के रूप में देखा जाए तो एक ट्री डेटा स्ट्रक्चर एक ऑर्डर किया हुआ ट्री है, आम तौर पर प्रत्येक नोड से जुड़े मूल्यों के साथ। निश्चित रूप से, यह है (यदि गैर-रिक्त होना आवश्यक है):
एक पूरे के रूप में देखा जाए तो एक वृक्ष डेटा स्ट्रक्चर एक ऑर्डर किया हुआ वृक्ष है, आम तौर पर प्रत्येक नोड से जुड़े मूल्यों के साथ। निश्चित रूप से, यह है (यदि गैर-रिक्त होना आवश्यक है):
* मूल दिशा से दूर एक [[जड़ वाला पेड़]] (एक अधिक संकीर्ण शब्द एक आर्बोरेसेंस (ग्राफ सिद्धांत) है), जिसका अर्थ है:
* मूल दिशा से दूर एक [[जड़ वाला पेड़|जड़ वाला]] वृक्ष (एक अधिक संकीर्ण शब्द एक आर्बोरेसेंस (ग्राफ सिद्धांत) है), जिसका अर्थ है:
** एक [[निर्देशित ग्राफ]],
** एक [[निर्देशित ग्राफ]],
** जिसका अंतर्निहित [[अप्रत्यक्ष ग्राफ]] एक पेड़ (ग्राफ सिद्धांत) है (कोई भी दो कोने बिल्कुल एक साधारण पथ से जुड़े हुए हैं),
** जिसका अंतर्निहित [[अप्रत्यक्ष ग्राफ]] एक वृक्ष (ग्राफ सिद्धांत) है (कोई भी दो कोने बिल्कुल एक साधारण पथ से जुड़े हुए हैं),
** एक विशिष्ट जड़ के साथ (एक शीर्ष को जड़ के रूप में नामित किया गया है),
** एक विशिष्ट जड़ के साथ (एक शीर्ष को जड़ के रूप में नामित किया गया है),
** जो किनारों पर दिशा निर्धारित करता है (तीर जड़ से दूर इंगित करता है; एक किनारे दिया गया है, जिस नोड से किनारे को इंगित करता है उसे माता-पिता कहा जाता है और किनारे को इंगित करने वाले नोड को बच्चे कहा जाता है), साथ में:
** जो किनारों पर दिशा निर्धारित करता है (तीर जड़ से दूर इंगित करता है; एक किनारे दिया गया है, जिस नोड से किनारे को इंगित करता है उसे माता-पिता कहा जाता है और किनारे को इंगित करने वाले नोड को बच्चे कहा जाता है), साथ में:
Line 160: Line 160:
* प्रत्येक नोड पर एक मान (कुछ डेटा प्रकार का)।
* प्रत्येक नोड पर एक मान (कुछ डेटा प्रकार का)।


अक्सर पेड़ों में एक निश्चित (अधिक ठीक से, बाउंडेड) [[ब्रांचिंग कारक]] ([[आगे की डिग्री]]) होता है, विशेष रूप से हमेशा दो चाइल्ड नोड्स होते हैं (संभवतः खाली, इसलिए अधिकतम दो नॉन-रिक्त चाइल्ड नोड्स), इसलिए एक बाइनरी ट्री।
अक्सर वृक्षों में एक निश्चित (अधिक ठीक से, बाउंडेड) [[ब्रांचिंग कारक]] ([[आगे की डिग्री]]) होता है, विशेष रूप से हमेशा दो चाइल्ड नोड्स होते हैं (संभवतः खाली, इसलिए अधिकतम दो नॉन-रिक्त चाइल्ड नोड्स), इसलिए एक द्विआधारी वृक्ष।


खाली पेड़ों की अनुमति से कुछ परिभाषाएँ सरल हो जाती हैं, कुछ अधिक जटिल: एक जड़ वाला पेड़ गैर-रिक्त होना चाहिए, इसलिए यदि खाली पेड़ों को उपरोक्त परिभाषा की अनुमति दी जाती है, तो इसके बजाय एक खाली पेड़ या एक जड़ वाला पेड़ बन जाता है ...। दूसरी ओर, खाली पेड़ फिक्स्ड ब्रांचिंग फैक्टर को परिभाषित करना आसान बनाते हैं: खाली पेड़ों की अनुमति के साथ, एक बाइनरी ट्री एक ऐसा पेड़ होता है, जिसमें हर नोड में दो बच्चे होते हैं, जिनमें से प्रत्येक एक पेड़ (संभवतः खाली) होता है। पेड़ पर संचालन के पूर्ण सेट में फोर्क ऑपरेशन शामिल होना चाहिए।{{huh|date=April 2022}}
खाली वृक्षों की अनुमति से कुछ परिभाषाएँ सरल हो जाती हैं, कुछ अधिक जटिल: एक जड़ वाला वृक्ष गैर-रिक्त होना चाहिए, इसलिए यदि खाली वृक्षों को उपरोक्त परिभाषा की अनुमति दी जाती है, तो इसके बजाय एक खाली वृक्ष या एक जड़ वाला वृक्ष बन जाता है ...। दूसरी ओर, खाली वृक्ष फिक्स्ड ब्रांचिंग फैक्टर को परिभाषित करना आसान बनाते हैं: खाली वृक्षों की अनुमति के साथ, एक द्विआधारी वृक्ष एक ऐसा वृक्ष होता है, जिसमें हर नोड में दो बच्चे होते हैं, जिनमें से प्रत्येक एक वृक्ष (संभवतः खाली) होता है। वृक्ष पर संचालन के पूर्ण समूह में फोर्क ऑपरेशन सम्मिलित होना चाहिए।{{huh|date=April 2022}}




== यह भी देखें ==
== यह भी देखें ==
* वृक्ष संरचना (सामान्य)
* वृक्ष संरचना (सामान्य)
* : श्रेणी: पेड़ (डेटा संरचनाएं) (कम्प्यूटेशनल पेड़ों की सूची प्रकार)
* : श्रेणी: वृक्ष (डेटा संरचनाएं) (कम्प्यूटेशनल वृक्षों की सूची प्रकार)


==टिप्पणियाँ==
==टिप्पणियाँ==

Revision as of 23:03, 27 February 2023

Not to be confused with Trie, a specific type of tree data structure.
इस अवर्गीकृत वृक्ष के गैर-अद्वितीय मान हैं और यह गैर-द्विआधारी है, क्योंकि बच्चों की संख्या एक (जैसे नोड 9) से तीन (नोड 7) तक भिन्न होती है। मूल नोड, शीर्ष पर, कोई पैरेंट नहीं है।

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

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

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

कंप्यूटिंग में उपयोग किए जाने वाले वृक्ष समान हैं परन्तु वृक्ष (ग्राफ सिद्धांत), वृक्ष (समूह सिद्धांत), और वृक्ष (वर्णनात्मक समूह सिद्धांत) के गणितीय निर्माणों से भिन्न हो सकते हैं।

अनुप्रयोग

वृक्षों का उपयोग सामान्यतः अनुप्रयोगों में पदानुक्रमित डेटा का प्रतिनिधित्व या क्रमभंग करने के लिए किया जाता है जैसे:

वृक्षों का उपयोग विभिन्न गणितीय संरचनाओं का प्रतिनिधित्व और क्रमभंग करने के लिए किया जा सकता है, जैसे:

वृक्ष संरचनाओं का उपयोग अक्सर चीजों के बीच संबंधों को मैप करने के लिए किया जाता है, जैसे कि:

  • अवयव और उप-घटक जिन्हें विस्फोट-दृश्य आरेखण में देखा जा सकता है
  • सबमूलीन कॉल का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से सबमूलीन्स अन्य सबमूलीन्स को गैर-पुनरावर्ती रूप से कॉल करते हैं
  • विकास द्वारा प्रजातियों के बीच डीएनए की विरासत, of source code by software projects (e.g. [[:File:Linux_Distribution_Timeline_Dec._2020.svg|लिनक्स वितरण समयरेखा), विभिन्न प्रकार की कारों में डिज़ाइन आदि।
  • पदानुक्रमित नामस्थानों की सामग्री

JSON और YAML दस्तावेज़ों को वृक्षों के रूप में माना जा सकता है, परन्तु सामान्यतः नेस्टेड सूची (संक्षेप डेटा प्रकार) और साहचर्य सरणी द्वारा प्रतिनिधित्व किया जाता है।

शब्दावली

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

एक आंतरिक नोड (जिसे एक आंतरिक नोड के रूप में भी जाना जाता है, लघु या शाखा नोड के लिए इनोड) एक वृक्ष का कोई भी नोड होता है जिसमें बच्चे के नोड होते हैं। इसी वृक्ष, एक बाहरी नोड (जिसे बाहरी नोड, लीफ नोड या टर्मिनल नोड के रूप में भी जाना जाता है) कोई भी नोड होता है जिसमें चाइल्ड नोड नहीं होता है।

एक नोड की ऊंचाई उस नोड से एक पत्ती के सबसे लंबे नीचे की ओर जाने वाले पथ की लंबाई है। जड़ की ऊंचाई ही वृक्ष की ऊंचाई होती है। एक नोड की गहराई इसकी जड़ के पथ की लंबाई है (यानी, इसका 'मूल पथ')। शून्य-आधारित गणना का उपयोग करते समय, मूल नोड की गहराई शून्य होती है, लीफ नोड्स की ऊंचाई शून्य होती है, और मात्र एक नोड वाले वृक्ष (इसलिए जड़ और पत्ती दोनों) की गहराई और ऊंचाई शून्य होती है। परंपरागत रूप से, एक खाली वृक्ष (बिना नोड्स वाला वृक्ष, अगर इसकी अनुमति है) की ऊंचाई -1 है।

प्रत्येक गैर-मूल नोड को अपने स्वयं के उपवृक्ष के मूल नोड के रूप में माना जा सकता है, जिसमें वह नोड और उसके सभी वंशज सम्मिलित हैं।[lower-alpha 1][1] वृक्षों के साथ प्रयुक्त अन्य शब्द:

Neighbor
Parent or child.
Ancestor
A node reachable by repeated proceeding from child to parent.
Descendant
A node reachable by repeated proceeding from parent to child. Also known as subchild.
Degree
For a given node, its number of children. A leaf has necessarily degree zero.
Degree of tree
The degree of a tree is the maximum degree of a node in the tree.
Distance
The number of edges along the shortest path between two nodes.
Level
The level of a node is the number of edges along the unique path between it and the root node.[2]
शून्य-आधारित गणना का उपयोग करते समय यह गहराई के समान है।
Width
The number of nodes in a level.
Breadth
The number of leaves.
Forest
A set of one or more disjoint trees.
Ordered tree
A rooted tree in which an ordering is specified for the children of each vertex. The book The Art of Computer Programming uses the term oriented tree.[3]
Size of a tree
Number of nodes in the tree.


वृक्षों और गैर-वृक्षों के उदाहरण

Not a tree: two non-connected parts, A→B and C→D→E. There is more than one root.
Not a tree: undirected cycle 1-2-4-3. 4 has more than one parent (inbound edge).
Not a tree: cycle B→C→E→D→B. B has more than one parent (inbound edge).
Not a tree: cycle A→A. A is the root but it also has a parent.
Each linear list is trivially a tree


सामान्य संचालन

Template:Graph search algorithm

पथक्रमण और खोज के तरीके

Main article: Tree traversal

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

प्रतिनिधित्व

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

नोड्स को एक सरणी डेटा संरचना में आइटम के रूप में भी संग्रहीत किया जा सकता है, उनके बीच संबंधों को सरणी में उनकी स्थिति द्वारा निर्धारित किया जाता है (जैसा कि द्विआधारी ढेर में)।

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

क्रमिक वृक्षों को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा एन्कोड किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।[4]


प्रकार सिद्धांत

संक्षेप डेटा प्रकार के रूप में, संक्षेप वृक्ष प्रकार T किसी प्रकार के मूल्यों के साथ E संक्षेप वन प्रकार का उपयोग करके परिभाषित किया गया है F (वृक्षों की सूची), कार्यों द्वारा:

कीमत: T → E
बच्चे: T → F
शून्य: () → F
नोड: E × F → T

सिद्धांतों के साथ:

मान (नोड (e, f)) = e
बच्चे (नोड (e, f)) = f

प्रकार के सिद्धांत के संदर्भ में, एक वृक्ष एक पुनरावर्ती डेटा प्रकार है जिसे निर्माणकर्ताओं द्वारा परिभाषित किया गया है nil (खाली जंगल) और node (दिए गए मूल्य और बच्चों के साथ मूल नोड वाला वृक्ष)।

गणितीय शब्दावली

एक पूरे के रूप में देखा जाए तो एक वृक्ष डेटा स्ट्रक्चर एक ऑर्डर किया हुआ वृक्ष है, आम तौर पर प्रत्येक नोड से जुड़े मूल्यों के साथ। निश्चित रूप से, यह है (यदि गैर-रिक्त होना आवश्यक है):

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

अक्सर वृक्षों में एक निश्चित (अधिक ठीक से, बाउंडेड) ब्रांचिंग कारक (आगे की डिग्री) होता है, विशेष रूप से हमेशा दो चाइल्ड नोड्स होते हैं (संभवतः खाली, इसलिए अधिकतम दो नॉन-रिक्त चाइल्ड नोड्स), इसलिए एक द्विआधारी वृक्ष।

खाली वृक्षों की अनुमति से कुछ परिभाषाएँ सरल हो जाती हैं, कुछ अधिक जटिल: एक जड़ वाला वृक्ष गैर-रिक्त होना चाहिए, इसलिए यदि खाली वृक्षों को उपरोक्त परिभाषा की अनुमति दी जाती है, तो इसके बजाय एक खाली वृक्ष या एक जड़ वाला वृक्ष बन जाता है ...। दूसरी ओर, खाली वृक्ष फिक्स्ड ब्रांचिंग फैक्टर को परिभाषित करना आसान बनाते हैं: खाली वृक्षों की अनुमति के साथ, एक द्विआधारी वृक्ष एक ऐसा वृक्ष होता है, जिसमें हर नोड में दो बच्चे होते हैं, जिनमें से प्रत्येक एक वृक्ष (संभवतः खाली) होता है। वृक्ष पर संचालन के पूर्ण समूह में फोर्क ऑपरेशन सम्मिलित होना चाहिए।[clarification needed]


यह भी देखें

  • वृक्ष संरचना (सामान्य)
  • : श्रेणी: वृक्ष (डेटा संरचनाएं) (कम्प्यूटेशनल वृक्षों की सूची प्रकार)

टिप्पणियाँ

  1. ↑ This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no descendants).


संदर्भ

  1. ↑ Weisstein, Eric W. "Subtree". MathWorld.
  2. ↑ Susanna S. Epp (Aug 2010). Discrete Mathematics with Applications. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694. ISBN 978-0-495-39132-6.
  3. ↑ Donald Knuth (1997). "Section 2.3.4.2: Oriented trees". The Art of Computer Programming. Vol. 1: Fundamental Algorithms (Third ed.). Addison-Wesley. p. 373.
  4. ↑ L. Afanasiev; P. Blackburn; I. Dimitriou; B. Gaiffe; E. Goris; M. Marx; M. de Rijke (2005). "PDL for ordered trees" (PDF). Journal of Applied Non-Classical Logics. 15 (2): 115–135. doi:10.3166/jancl.15.115-135. S2CID 1979330.


अग्रिम पठन


बाहरी संबंध

Wikimedia Commons has media related to Tree structures.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ट्री_(डेटा_संरचना)&oldid=102442’