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

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 4 users not shown)
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}}
[[File:Tree (computer science).svg|right|thumb|इस अवर्गीकृत वृक्ष के गैर-अद्वितीय मान हैं और यह गैर-द्विआधारी है, क्योंकि बच्चों की संख्या एक(जैसे नोड 9) से तीन(नोड 7) तक भिन्न होती है। मूल नोड, शीर्ष पर, कोई जनक नहीं है।]][[कंप्यूटर विज्ञान]] में, एक वृक्ष व्यापक रूप से उपयोग किया जाने वाला संक्षेप डेटा प्रकार है जो जुड़े हुए [[नोड (कंप्यूटर विज्ञान)|नोड(कंप्यूटर विज्ञान)]] के एक समूह के साथ पदानुक्रमित वृक्ष संरचना का प्रतिनिधित्व करता है। वृक्ष में प्रत्येक नोड को कई बच्चों(वृक्ष के प्रकार के आधार पर) से जोड़ा जा सकता है, परन्तु 'मूल' नोड को छोड़कर, जिसका कोई जनक नहीं है, को ठीक से एक जनक से जोड़ा जाना चाहिए। इन बाधाओं का तात्पर्य है कि कोई चक्र या लूप नहीं है(कोई भी नोड उसका स्वयं का पूर्वज नहीं हो सकता है), और यह भी कि प्रत्येक बच्चे को अपने स्वयं के उपवृक्ष के मूल नोड के जैसे माना जा सकता है, जिससे पुनरावृत्ति [[ट्री ट्रैवर्सल|वृक्ष पथक्रमण]] के लिए एक उपयोगी तकनीक बन जाती है। [[रैखिक डेटा संरचना|रैखिक डेटा संरचनाओं]] के विपरीत, कई वृक्षों को एक सीधी रेखा में निकटतम नोड्स के बीच संबंधों द्वारा प्रदर्शित नहीं किया जा सकता है।
[[File:Tree (computer science).svg|right|thumb|इस अवर्गीकृत ट्री के गैर-अद्वितीय मान हैं और यह गैर-द्विआधारी है, क्योंकि बच्चों की संख्या एक(जैसे नोड 9) से तीन(नोड 7) तक भिन्न होती है। रुट नोड, शीर्ष पर, कोई जनक नहीं है।]][[कंप्यूटर विज्ञान]] में, एक ट्री व्यापक रूप से उपयोग किया जाने वाला संक्षेप डेटा प्रकार है जो जुड़े हुए [[नोड (कंप्यूटर विज्ञान)|नोड(कंप्यूटर विज्ञान)]] के एक समूह के साथ पदानुक्रमित ट्री संरचना का प्रतिनिधित्व करता है। ट्री में प्रत्येक नोड को कई बच्चों(ट्री के प्रकार के आधार पर) से जोड़ा जा सकता है, परन्तु 'रुट' नोड को छोड़कर, जिसका कोई जनक नहीं है, को ठीक से एक जनक से जोड़ा जाना चाहिए। इन बाधाओं का तात्पर्य है कि कोई चक्र या लूप नहीं है(कोई भी नोड उसका स्वयं का पूर्वज नहीं हो सकता है), और यह भी कि प्रत्येक बच्चे को अपने स्वयं के उपट्री के रुट नोड के जैसे माना जा सकता है, जिससे पुनरावृत्ति [[ट्री ट्रैवर्सल|ट्री पथक्रमण]] के लिए एक उपयोगी तकनीक बन जाती है। [[रैखिक डेटा संरचना|रैखिक डेटा संरचनाओं]] के विपरीत, कई ट्री को एक सीधी रेखा में निकटतम नोड्स के बीच संबंधों द्वारा प्रदर्शित नहीं किया जा सकता है।


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


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


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


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


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


वृक्ष संरचनाओं का उपयोग प्रायः चीजों के बीच संबंधों को प्रतिचित्रित करने के लिए किया जाता है, जैसे कि:
ट्री संरचनाओं का उपयोग प्रायः चीजों के बीच संबंधों को प्रतिचित्रित करने के लिए किया जाता है, जैसे कि:
* अवयव और उप-घटक जिन्हें [[विस्फोट-दृश्य आरेखण]] में देखा जा सकता है
* अवयव और उप-घटक जिन्हें [[विस्फोट-दृश्य आरेखण]] में देखा जा सकता है
* [[सबरूटीन कॉल|प्रक्रिया कॉल]] का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से प्रक्रिया् अन्य प्रक्रिया् को गैर-पुनरावर्ती रूप से कॉल करते हैं
* [[सबरूटीन कॉल|प्रक्रिया कॉल]] का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से प्रक्रिया् अन्य प्रक्रिया् को गैर-पुनरावर्ती रूप से कॉल करते हैं
Line 44: Line 44:
* पदानुक्रमित नामस्थानों की विषय सूची
* पदानुक्रमित नामस्थानों की विषय सूची


[[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|निकटवर्ती}} {{defn|माता-पिता या बच्चा।}}
{{term|निकटवर्ती}} {{defn|माता-पिता या बच्चा।}}
Line 61: Line 61:
{{term|वंशज}} {{defn|माता-पिता से बच्चे के लिए बार-बार आगे बढ़ने पर एक नोड। 'उपबच्चे ' के रूप में भी जाना जाता है।}}
{{term|वंशज}} {{defn|माता-पिता से बच्चे के लिए बार-बार आगे बढ़ने पर एक नोड। 'उपबच्चे ' के रूप में भी जाना जाता है।}}
{{term|परिमाण}} {{defn|किसी दिए गए नोड के लिए, उसके बच्चों की संख्या। एक पत्ते की आवश्यक रूप से परिमाण शून्य होता है।}}
{{term|परिमाण}} {{defn|किसी दिए गए नोड के लिए, उसके बच्चों की संख्या। एक पत्ते की आवश्यक रूप से परिमाण शून्य होता है।}}
{{term|वृक्ष का परिमाण}} {{defn|वृक्ष का परिमाण पेड़ में नोड का अधिकतम परिमाण है।}}
{{term|ट्री का परिमाण}} {{defn|ट्री का परिमाण ट्री में नोड का अधिकतम परिमाण है।}}
{{term|दूरी}} {{defn|दो नोड्स के बीच सबसे छोटे पथ के किनारों की संख्या।}}
{{term|दूरी}} {{defn|दो नोड्स के बीच सबसे छोटे पथ के किनारों की संख्या।}}
{{term|स्तर}} {{defn|एक नोड का स्तर इसके साथ किनारों की संख्या है
{{term|स्तर}} {{defn|एक नोड का स्तर इसके साथ किनारों की संख्या है
इसके और रूट नोड के बीच अद्वितीय पथ।<ref>{{cite book | url=https://dl.acm.org/doi/book/10.5555/1941983 | isbn=978-0-495-39132-6 | author=Susanna S. Epp | title=Discrete Mathematics with Applications | location=Pacific Grove, CA | publisher=Brooks/Cole Publishing Co. | date=Aug 2010 | page=694 }}</ref>}} शून्य-आधारित गणना का उपयोग करते समय यह गहराई के समान है।
इसके और रुट नोड के बीच अद्वितीय पथ।<ref>{{cite book | url=https://dl.acm.org/doi/book/10.5555/1941983 | isbn=978-0-495-39132-6 | author=Susanna S. Epp | title=Discrete Mathematics with Applications | location=Pacific Grove, CA | publisher=Brooks/Cole Publishing Co. | date=Aug 2010 | page=694 }}</ref>}} शून्य-आधारित गणना का उपयोग करते समय यह गहराई के समान है।
{{term|Width}} {{defn|एक स्तर में नोड्स की संख्या।}}
{{term|Width}} {{defn|एक स्तर में नोड्स की संख्या।}}
{{term|चौड़ाई}} {{defn|पत्तों की संख्या।}}
{{term|चौड़ाई}} {{defn|पत्तों की संख्या।}}
{{term|वन}} {{defn|एक या एक से अधिक असंबद्ध वृक्षों का समूह।}}
{{term|वन}} {{defn|एक या एक से अधिक असंबद्ध ट्री का समूह।}}
{{term|क्रमित वृक्ष}} {{defn|एक जड़ वाला वृक्ष जिसमें प्रत्येक शीर्ष के बच्चों के लिए एक क्रम निर्दिष्ट किया गया है। ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' पुस्तक ''उन्मुखी वृक्ष'' शब्द का प्रयोग करती है।<ref name="TAoCP_oriented_trees">{{cite book |author=[[Donald Knuth]] |title=The Art of Computer Programming |volume=1: ''Fundamental Algorithms'' |edition=Third |publisher=Addison-Wesley |year=1997 |section=Section 2.3.4.2: Oriented trees |url=http://elganzua124.github.io/taocp/OEBPS/Text/ch02b.html#page_373 |page=373}}</ref>}}
{{term|क्रमित ट्री}} {{defn|एक रुट वाला ट्री जिसमें प्रत्येक शीर्ष के बच्चों के लिए एक क्रम निर्दिष्ट किया गया है। ''[[कंप्यूटर प्रोग्रामिंग की कला]]'' पुस्तक ''उन्मुखी ट्री'' शब्द का प्रयोग करती है।<ref name="TAoCP_oriented_trees">{{cite book |author=[[Donald Knuth]] |title=The Art of Computer Programming |volume=1: ''Fundamental Algorithms'' |edition=Third |publisher=Addison-Wesley |year=1997 |section=Section 2.3.4.2: Oriented trees |url=http://elganzua124.github.io/taocp/OEBPS/Text/ch02b.html#page_373 |page=373}}</ref>}}
{{term|एक वृक्ष का आकार}} {{defn|वृक्ष में नोड्स की संख्या।}}
{{term|एक ट्री का आकार}} {{defn|ट्री में नोड्स की संख्या।}}
{{glossary end}}
{{glossary end}}




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


{{multiple image
{{multiple image
Line 79: Line 79:
| image1 = Directed graph, disjoint.svg
| image1 = Directed graph, disjoint.svg
| width1 = 130
| width1 = 130
| caption1 = {{color|#800000|Not a tree}}: two non-[[Connectivity (graph theory)#Definitions of components, cuts and connectivity|connected]] parts, A→B and C→D→E. एक से अधिक जड़े होती है।
| caption1 = {{color|#800000|ट्री नहीं}}: दो गैर-[[Connectivity (graph theory)#Definitions of components, cuts और connectivity|संयुक्त]] भाग, A→B and C→D→E. एक से अधिक जड़े होती है।
| image2 = Directed graph with branching SVG.svg
| image2 = Directed graph with branching SVG.svg
| width2 = 101
| width2 = 101
| caption2 = {{color|#800000|Not a tree}}: undirected cycle 1-2-4-3. 4 has more than one parent (inbound edge).
| caption2 = {{color|#800000|ट्री नहीं}}: अप्रत्यक्ष चक्र 1-2-4-3. 4 में एक से अधिक पैरेंट (भीतर का किनारा) हैं।
| image3 = Directed graph, cyclic.svg
| image3 = Directed graph, cyclic.svg
| width3 = 211
| width3 = 211
| caption3 = {{color|#800000|Not a tree}}: cycle B→C→E→D→B. B has more than one parent (inbound edge).
| caption3 = {{color|#800000|ट्री नहीं}}: चक्र B→C→E→D→B. B के एक से अधिक माता पिता(भीतर का किनारा) हैं।
| image4 = Graph single node.svg
| image4 = Graph single node.svg
| width4 = 92
| width4 = 92
| caption4 = {{color|#800000|Not a tree}}: cycle A→A. A is the root but it also has a parent.
| caption4 = {{color|#800000|ट्री नहीं}}: चक्र A→A. A रुट है परन्तु इसके एक माता पिता भी है।
| image5 = Directed Graph Edge.svg
| image5 = Directed Graph Edge.svg
| width5 = 173
| width5 = 173
| caption5 = Each linear list is trivially {{color|#008000|a tree}}
| caption5 = प्रत्येक रैखिक सूची तुच्छ रूप से एक {{color|#008000|ट्री}} है
}}
}}


Line 97: Line 97:
== सामान्य संचालन ==
== सामान्य संचालन ==
* सभी वस्तुओं की गणना करना
* सभी वस्तुओं की गणना करना
* वृक्ष के एक खंड की गणना
* ट्री के एक खंड की गणना
* किसी वस्तु की परीक्षण करना
* किसी वस्तु की परीक्षण करना
* वृक्ष पर एक निश्चित स्थान पर एक नवीन वस्तु जोड़ना
* ट्री पर एक निश्चित स्थान पर एक नवीन वस्तु जोड़ना
* किसी वस्तु को हटाना
* किसी वस्तु को हटाना
* [[प्रूनिंग (एल्गोरिदम)|प्रूनिंग(कलन विधि)]]: वृक्ष के पूरे खंड को हटाना
* [[प्रूनिंग (एल्गोरिदम)|प्रूनिंग(कलन विधि)]]: ट्री के पूरे खंड को हटाना
* [[ग्राफ्टिंग (एल्गोरिदम)|रेखा-चित्र्टिंग(कलन विधि)]]: वृक्ष में एक पूरा खंड जोड़ना
* [[ग्राफ्टिंग (एल्गोरिदम)|रेखा-चित्र्टिंग(कलन विधि)]]: ट्री में एक पूरा खंड जोड़ना
* किसी भी नोड के लिए मूल ढूँढना
* किसी भी नोड के लिए रुट ढूँढना
* दो नोड्स के [[सबसे कम सामान्य पूर्वज]] का पता लगाना
* दो नोड्स के [[सबसे कम सामान्य पूर्वज]] का पता लगाना


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


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


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


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


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


क्रमिक वृक्षों को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा कोडित किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।<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 137: Line 137:


== प्रकार सिद्धांत ==
== प्रकार सिद्धांत ==
संक्षेप डेटा प्रकार के रूप में, संक्षेप वृक्ष प्रकार {{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 145: Line 145:
: मान(नोड({{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}}(दिए गए मूल्य और बच्चों के साथ मूल नोड वाला ट्री)।


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


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


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




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


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 188: Line 188:
* [http://www.allisons.org/ll/AlgDS/Tree/ ''Binary Trees'' by L. Allison]
* [http://www.allisons.org/ll/AlgDS/Tree/ ''Binary Trees'' by L. Allison]


{{DEFAULTSORT:Tree (Data Structure)}}[[Category: डेटा के प्रकार]] [[Category: पेड़ (डेटा संरचनाएं) | पेड़ (डेटा संरचनाएं) ]] [[Category: ज्ञान निरूपण]] [[Category: सार डेटा प्रकार]]
{{DEFAULTSORT:Tree (Data Structure)}}  


[[de:Baum (Graphentheorie)]]
[[de:Baum (Graphentheorie)]]


 
[[Category:Articles with hatnote templates targeting a nonexistent page|Tree (Data Structure)]]
 
[[Category:CS1]]
[[Category: Machine Translated Page]]
[[Category:Created On 17/02/2023|Tree (Data Structure)]]
[[Category:Created On 17/02/2023]]
[[Category:Lua-based templates|Tree (Data Structure)]]
[[Category:Machine Translated Page|Tree (Data Structure)]]
[[Category:Pages with script errors|Tree (Data Structure)]]
[[Category:Short description with empty Wikidata description|Tree (Data Structure)]]
[[Category:Templates Vigyan Ready|Tree (Data Structure)]]
[[Category:Templates that add a tracking category|Tree (Data Structure)]]
[[Category:Templates that generate short descriptions|Tree (Data Structure)]]
[[Category:Templates using TemplateData|Tree (Data Structure)]]
[[Category:Wikipedia articles needing clarification from April 2022|Tree (Data Structure)]]
[[Category:ज्ञान निरूपण|Tree (Data Structure)]]
[[Category:डेटा के प्रकार|Tree (Data Structure)]]
[[Category:पेड़ (डेटा संरचनाएं)| पेड़ (डेटा संरचनाएं) ]]
[[Category:सार डेटा प्रकार|Tree (Data Structure)]]

Latest revision as of 10:59, 10 March 2023

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

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

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

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

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

अनुप्रयोग

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

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

ट्री संरचनाओं का उपयोग प्रायः चीजों के बीच संबंधों को प्रतिचित्रित करने के लिए किया जाता है, जैसे कि:

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

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

शब्दावली

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

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

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

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

ट्री के साथ प्रयुक्त अन्य शब्द:

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


ट्री और गैर-ट्री के उदाहरण

ट्री नहीं: दो गैर-संयुक्त भाग, A→B and C→D→E. एक से अधिक जड़े होती है।
ट्री नहीं: अप्रत्यक्ष चक्र 1-2-4-3. 4 में एक से अधिक पैरेंट (भीतर का किनारा) हैं।
ट्री नहीं: चक्र B→C→E→D→B. B के एक से अधिक माता पिता(भीतर का किनारा) हैं।
ट्री नहीं: चक्र A→A. A रुट है परन्तु इसके एक माता पिता भी है।
प्रत्येक रैखिक सूची तुच्छ रूप से एक ट्री है


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

पथक्रमण और परीक्षण की विधियां

Main article: वृक्ष पथक्रमण

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

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

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

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

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

क्रमिक ट्री को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा कोडित किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।[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.


अग्रिम पठन


बाह्य संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ट्री_(डेटा_संरचना)&oldid=102905’