ट्री (डेटा संरचना): Difference between revisions
No edit summary |
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}} | ||
[[File:Tree (computer science).svg|right|thumb|इस अवर्गीकृत | [[File:Tree (computer science).svg|right|thumb|इस अवर्गीकृत ट्री के गैर-अद्वितीय मान हैं और यह गैर-द्विआधारी है, क्योंकि बच्चों की संख्या एक(जैसे नोड 9) से तीन(नोड 7) तक भिन्न होती है। मूल नोड, शीर्ष पर, कोई जनक नहीं है।]][[कंप्यूटर विज्ञान]] में, एक ट्री व्यापक रूप से उपयोग किया जाने वाला संक्षेप डेटा प्रकार है जो जुड़े हुए [[नोड (कंप्यूटर विज्ञान)|नोड(कंप्यूटर विज्ञान)]] के एक समूह के साथ पदानुक्रमित ट्री संरचना का प्रतिनिधित्व करता है। ट्री में प्रत्येक नोड को कई बच्चों(ट्री के प्रकार के आधार पर) से जोड़ा जा सकता है, परन्तु 'मूल' नोड को छोड़कर, जिसका कोई जनक नहीं है, को ठीक से एक जनक से जोड़ा जाना चाहिए। इन बाधाओं का तात्पर्य है कि कोई चक्र या लूप नहीं है(कोई भी नोड उसका स्वयं का पूर्वज नहीं हो सकता है), और यह भी कि प्रत्येक बच्चे को अपने स्वयं के उपट्री के मूल नोड के जैसे माना जा सकता है, जिससे पुनरावृत्ति [[ट्री ट्रैवर्सल|ट्री पथक्रमण]] के लिए एक उपयोगी तकनीक बन जाती है। [[रैखिक डेटा संरचना|रैखिक डेटा संरचनाओं]] के विपरीत, कई वृक्षों को एक सीधी रेखा में निकटतम नोड्स के बीच संबंधों द्वारा प्रदर्शित नहीं किया जा सकता है। | ||
[[बाइनरी ट्री|द्विआधारी | [[बाइनरी ट्री|द्विआधारी]] ट्री सामान्यतः उपयोग किया जाने वाला प्रकार है, जो प्रत्येक जनक के लिए अधिकतम दो बच्चों की संख्या को सीमित करता है। जब बच्चों का क्रम निर्दिष्ट किया जाता है, तो यह डेटा संरचना [[ग्राफ सिद्धांत|रेखा-चित्र सिद्धांत]] में एक क्रमिक ट्री से मेल खाती है। अन्य डेटा के लिए मूल्य या सूचक ट्री में प्रत्येक नोड के साथ जुड़ा हो सकता है, या कभी-कभी मात्र 'पत्ती नोड्स' के साथ जुड़ा हो सकता है, जिसमें कोई संतान नहीं है। | ||
[[सार डेटा प्रकार|संक्षेप डेटा प्रकार]] को कई विधियों से प्रदर्शित किया जा सकता है, जिसमें जनक की सूची बच्चों के लिए संकेत, जनक के संकेत वाले बच्चों की सूची, या नोड्स की सूची और जनक-बाल संबंधों की एक अलग सूची(एक विशिष्ट प्रकार [[निकटता सूची]] )सम्मिलित है। अभ्यावेदन भी अधिक जटिल हो सकते हैं, उदाहरण के लिए निष्पादन के लिए [[डाटाबेस इंडेक्स|डाटाबेस अनुक्रमणिका]] या पूर्वजों की सूची का उपयोग करना। | [[सार डेटा प्रकार|संक्षेप डेटा प्रकार]] को कई विधियों से प्रदर्शित किया जा सकता है, जिसमें जनक की सूची बच्चों के लिए संकेत, जनक के संकेत वाले बच्चों की सूची, या नोड्स की सूची और जनक-बाल संबंधों की एक अलग सूची(एक विशिष्ट प्रकार [[निकटता सूची]] )सम्मिलित है। अभ्यावेदन भी अधिक जटिल हो सकते हैं, उदाहरण के लिए निष्पादन के लिए [[डाटाबेस इंडेक्स|डाटाबेस अनुक्रमणिका]] या पूर्वजों की सूची का उपयोग करना। | ||
कंप्यूटिंग में उपयोग किए जाने वाले | कंप्यूटिंग में उपयोग किए जाने वाले ट्री समान हैं परन्तु वृक्ष(रेखा-चित्र सिद्धांत), [[पेड़ (सेट सिद्धांत)|वृक्ष(समूह सिद्धांत)]], और वृक्ष(वर्णनात्मक समूह सिद्धांत) के गणितीय निर्माणों से भिन्न हो सकते हैं। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
वृक्षों का उपयोग सामान्यतः अनुप्रयोगों में पदानुक्रमित डेटा का प्रतिनिधित्व या क्रमभंग करने के लिए किया जाता है जैसे: | वृक्षों का उपयोग सामान्यतः अनुप्रयोगों में पदानुक्रमित डेटा का प्रतिनिधित्व या क्रमभंग करने के लिए किया जाता है जैसे: | ||
* [[फाइल सिस्टम|फाइल पद्धति]] के लिए: | * [[फाइल सिस्टम|फाइल पद्धति]] के लिए: | ||
** [[निर्देशिका संरचना]] का उपयोग उपनिर्देशिकाओं और फ़ाइलों को व्यवस्थित करने के लिए किया जाता है([[प्रतीकात्मक लिंक]] गैर- | ** [[निर्देशिका संरचना]] का उपयोग उपनिर्देशिकाओं और फ़ाइलों को व्यवस्थित करने के लिए किया जाता है([[प्रतीकात्मक लिंक]] गैर-ट्री रेखा-चित्ऱ बनाते हैं, जैसा कि एक ही फ़ाइल या निर्देशिका के लिए कई [[कड़ी कड़ी|दृढ़ लिंक]] करते हैं) | ||
** स्टोरेज डिवाइस पर डेटा के खंड आवंटित करने और लिंक करने के लिए प्रयुक्त तंत्र | ** स्टोरेज डिवाइस पर डेटा के खंड आवंटित करने और लिंक करने के लिए प्रयुक्त तंत्र | ||
* वर्ग पदानुक्रम या वंशानुक्रम | * वर्ग पदानुक्रम या वंशानुक्रम ट्री [[ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग]] में [[वर्ग (कंप्यूटर प्रोग्रामिंग)|वर्ग(कंप्यूटर प्रोग्रामिंग)]] के बीच संबंधों को दर्शाता है; [[एकाधिक वंशानुक्रम]] गैर-ट्री रेखांकन उत्पन्न करता है | ||
* कंप्यूटर भाषाओं के लिए [[सार वाक्य रचना का पेड़|संक्षेप वाक्य रचना का वृक्ष]] | * कंप्यूटर भाषाओं के लिए [[सार वाक्य रचना का पेड़|संक्षेप वाक्य रचना का वृक्ष]] | ||
* [[प्राकृतिक भाषा प्रसंस्करण]]: | * [[प्राकृतिक भाषा प्रसंस्करण]]: | ||
| Line 20: | Line 20: | ||
** वार्तालाप उत्पन्न करने के लिए [[संवाद वृक्ष]] | ** वार्तालाप उत्पन्न करने के लिए [[संवाद वृक्ष]] | ||
* [[XML|एक्सएमएल]] और [[HTML|एचटीएमएल]] दस्तावेज़ों के दस्तावेज़ ऑब्जेक्ट मॉडल(डीओएम वृक्ष)। | * [[XML|एक्सएमएल]] और [[HTML|एचटीएमएल]] दस्तावेज़ों के दस्तावेज़ ऑब्जेक्ट मॉडल(डीओएम वृक्ष)। | ||
* [[खोज पेड़|परीक्षण]] | * [[खोज पेड़|परीक्षण]] ट्री डेटा को एक ट्री से संंग्रहीत करता है जो ट्री पथक्रमण के माध्यम से एक कुशल [[खोज एल्गोरिदम|परीक्षण कलन विधि]] को संभव बनाता है | ||
** [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण | ** [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण]] ट्री एक प्रकार का द्विआधारी ट्री है | ||
* डेटा के [[छँटाई एल्गोरिथ्म|क्रमबद्ध कलन विधि]] का प्रतिनिधित्व करना | * डेटा के [[छँटाई एल्गोरिथ्म|क्रमबद्ध कलन विधि]] का प्रतिनिधित्व करना | ||
* [[कंप्यूटर जनित कल्पना]]: | * [[कंप्यूटर जनित कल्पना]]: | ||
** स्थान विभाजन, जिसमें [[बाइनरी स्पेस विभाजन|द्विआधारी स्थान विभाजन]] सम्मिलित है | ** स्थान विभाजन, जिसमें [[बाइनरी स्पेस विभाजन|द्विआधारी स्थान विभाजन]] सम्मिलित है | ||
** [[डिजिटल रचना]] | ** [[डिजिटल रचना]] | ||
* भंडारण बार्न्स-हट के | * भंडारण बार्न्स-हट के ट्री आकाशगंगाओं का अनुकरण करते थे | ||
* कार्यान्वयन ढेर(डेटा संरचना) | * कार्यान्वयन ढेर(डेटा संरचना) | ||
* [[नेस्टेड सेट|नीडित समूह]] | * [[नेस्टेड सेट|नीडित समूह]] | ||
| Line 35: | Line 35: | ||
वृक्षों का उपयोग विभिन्न गणितीय संरचनाओं का प्रतिनिधित्व और क्रमभंग करने के लिए किया जा सकता है, जैसे: | वृक्षों का उपयोग विभिन्न गणितीय संरचनाओं का प्रतिनिधित्व और क्रमभंग करने के लिए किया जा सकता है, जैसे: | ||
* एकपक्षीय [[ग्राफ (असतत गणित)|रेखा-चित्र(असतत गणित)]] के माध्यम से पथ | नोड-और -किनारे का रेखा-चित्र([[मल्टीग्राफ|बहु रेखांकन]] सहित), कई मार्गों में उपयोग किए जाने वाले प्रत्येक रेखा-चित्र नोड के लिए | * एकपक्षीय [[ग्राफ (असतत गणित)|रेखा-चित्र(असतत गणित)]] के माध्यम से पथ | नोड-और -किनारे का रेखा-चित्र([[मल्टीग्राफ|बहु रेखांकन]] सहित), कई मार्गों में उपयोग किए जाने वाले प्रत्येक रेखा-चित्र नोड के लिए ट्री में कई नोड बनाकर | ||
* कोई [[पदानुक्रम (गणित)|पदानुक्रम(गणित)]] | * कोई [[पदानुक्रम (गणित)|पदानुक्रम(गणित)]] | ||
ट्री संरचनाओं का उपयोग प्रायः चीजों के बीच संबंधों को प्रतिचित्रित करने के लिए किया जाता है, जैसे कि: | |||
* अवयव और उप-घटक जिन्हें [[विस्फोट-दृश्य आरेखण]] में देखा जा सकता है | * अवयव और उप-घटक जिन्हें [[विस्फोट-दृश्य आरेखण]] में देखा जा सकता है | ||
* [[सबरूटीन कॉल|प्रक्रिया कॉल]] का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से प्रक्रिया् अन्य प्रक्रिया् को गैर-पुनरावर्ती रूप से कॉल करते हैं | * [[सबरूटीन कॉल|प्रक्रिया कॉल]] का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से प्रक्रिया् अन्य प्रक्रिया् को गैर-पुनरावर्ती रूप से कॉल करते हैं | ||
| Line 47: | Line 47: | ||
== शब्दावली == | == शब्दावली == | ||
एक नोड(कंप्यूटर विज्ञान) एक संरचना है जिसमें डेटा और अन्य नोड्स के संयोजन हो सकते हैं, जिन्हें कभी-कभी किनारे या लिंक कहा जाता है। एक | एक नोड(कंप्यूटर विज्ञान) एक संरचना है जिसमें डेटा और अन्य नोड्स के संयोजन हो सकते हैं, जिन्हें कभी-कभी किनारे या लिंक कहा जाता है। एक ट्री में प्रत्येक नोड में शून्य या अधिक बच्चे के नोड होते हैं, जो ट्री में इसके नीचे होते हैं(अभिसमय के अनुसार, वृक्षों को 'अवरोही' नीचे की ओर जाते हुए खींचा जाता है)। एक नोड जिसमें एक बच्चा होता है उसे बच्चे का मूल नोड(या [[सुपीरियर (पदानुक्रम)|सुपीरियर(पदानुक्रम)]]) कहा जाता है। शीर्षतम मूल नोड को छोड़कर, जिसमें कोई नहीं है, सभी नोड्स में निश्चित एक जनक है। नोड में कई पूर्वज नोड हो सकते हैं, जैसे कि जनक के जनक। एक ही जनक वाले सन्तान नोड समाभासी नोड होते हैं। सामान्यतः समाभासी का एक क्रम होता है, जिसमें प्रथम पारंपरिक रूप से बाईं ओर खींचा जाता है। कुछ परिभाषाएँ एक ट्री को कोई नोड नहीं होने देती हैं, जिस स्थिति में इसे ''रिक्त'' कहा जाता है। | ||
एक आंतरिक नोड(जिसे एक आंतरिक नोड के रूप में भी जाना जाता है, लघु या | एक आंतरिक नोड(जिसे एक आंतरिक नोड के रूप में भी जाना जाता है, लघु या ब्रांच नोड के लिए इनोड) एक ट्री का कोई भी नोड होता है जिसमें बच्चे के नोड होते हैं। इसी वृक्ष, एक बाह्य नोड(जिसे बाह्य नोड, पत्ती नोड या आवधिक नोड के रूप में भी जाना जाता है) कोई भी नोड होता है जिसमें सन्तान नोड नहीं होता है। | ||
एक नोड की ऊंचाई उस नोड से एक पत्ती के सबसे लंबे नीचे की ओर जाने वाले पथ की लंबाई है। मूल की ऊंचाई ही | एक नोड की ऊंचाई उस नोड से एक पत्ती के सबसे लंबे नीचे की ओर जाने वाले पथ की लंबाई है। मूल की ऊंचाई ही ट्री की ऊंचाई होती है। एक नोड की गहराई इसकी मूल के पथ की लंबाई है(यानी, इसका 'मूल पथ')। शून्य-आधारित गणना का उपयोग करते समय, मूल नोड की गहराई शून्य होती है, पत्ती नोड्स की ऊंचाई शून्य होती है, और मात्र एक नोड वाले वृक्ष(इसलिए जड़ और पत्ती दोनों) की गहराई और ऊंचाई शून्य होती है। परंपरागत रूप से, एक रिक्त वृक्ष(बिना नोड्स वाला वृक्ष, यदि इसकी अनुमति है) की ऊंचाई -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> | ||
वृक्षों के साथ प्रयुक्त अन्य शब्द: | वृक्षों के साथ प्रयुक्त अन्य शब्द: | ||
| Line 97: | Line 97: | ||
== सामान्य संचालन == | == सामान्य संचालन == | ||
* सभी वस्तुओं की गणना करना | * सभी वस्तुओं की गणना करना | ||
* | * ट्री के एक खंड की गणना | ||
* किसी वस्तु की परीक्षण करना | * किसी वस्तु की परीक्षण करना | ||
* | * ट्री पर एक निश्चित स्थान पर एक नवीन वस्तु जोड़ना | ||
* किसी वस्तु को हटाना | * किसी वस्तु को हटाना | ||
* [[प्रूनिंग (एल्गोरिदम)|प्रूनिंग(कलन विधि)]]: | * [[प्रूनिंग (एल्गोरिदम)|प्रूनिंग(कलन विधि)]]: ट्री के पूरे खंड को हटाना | ||
* [[ग्राफ्टिंग (एल्गोरिदम)|रेखा-चित्र्टिंग(कलन विधि)]]: | * [[ग्राफ्टिंग (एल्गोरिदम)|रेखा-चित्र्टिंग(कलन विधि)]]: ट्री में एक पूरा खंड जोड़ना | ||
* किसी भी नोड के लिए मूल ढूँढना | * किसी भी नोड के लिए मूल ढूँढना | ||
* दो नोड्स के [[सबसे कम सामान्य पूर्वज]] का पता लगाना | * दो नोड्स के [[सबसे कम सामान्य पूर्वज]] का पता लगाना | ||
| Line 108: | Line 108: | ||
=== पथक्रमण और परीक्षण की विधियां === | === पथक्रमण और परीक्षण की विधियां === | ||
{{Main article|वृक्ष पथक्रमण}} | {{Main article|वृक्ष पथक्रमण}} | ||
जनक और बच्चों के बीच संबंधों के माध्यम से एक | जनक और बच्चों के बीच संबंधों के माध्यम से एक ट्री की वस्तुओं के माध्यम से कदम रखना, ट्री पर चलना कहलाता है, और क्रिया ट्री का ''चलना'' है। जब कोई सूचक किसी विशेष नोड पर आता है, तो प्रायः एक संचालन किया जा सकता है। एक क़दम जिसमें प्रत्येक जनक नोड को उसके बच्चों से पूर्व पार किया जाता है, उसे पूर्व-क्रम क़दम कहा जाता है; एक क़दम जिसमें बच्चों को उनके संबंधित जनक से पूर्व पार किया जाता है, क्रमोत्तर क़दम कहा जाता है; एक क़दम जिसमें एक नोड का बायाँ उपवृक्ष, फिर नोड स्वयं, और अंत में इसका दाहिना उपट्री पार किया जाता है, इन-क्रम पथक्रमण कहलाता है।(यह अंतिम परिदृश्य, ठीक दो उपवृक्ष, एक बायाँ उपट्री और एक दाहिना उपट्री का उल्लेख करते हुए, विशेष रूप से एक द्विआधारी ट्री मानता है।) एक स्तर-क्रम क़दम प्रभावी रूप से एक ट्री की संपूर्णता पर चौड़ाई-प्रथम परीक्षण करता है; नोड्स को स्तर से पार किया जाता है, जहां पूर्व मूल नोड का भ्रमण किया जाता है, उसके बाद उसके प्रत्यक्ष बच्चे नोड्स और उनके भाई बहनों के बाद, उसके पोते नोड्स और उनके भाई बहनों आदि के बाद, जब तक ट्री में सभी नोड्स का पता नहीं लगाया जाता है। | ||
== प्रतिनिधित्व == | == प्रतिनिधित्व == | ||
| Line 116: | Line 116: | ||
नोड्स को एक [[सरणी डेटा संरचना]] में वस्तु के रूप में भी संग्रहीत किया जा सकता है, उनके बीच संबंधों को सरणी में उनकी स्थिति द्वारा निर्धारित किया जाता है(जैसा कि [[द्विआधारी ढेर]] में)। | नोड्स को एक [[सरणी डेटा संरचना]] में वस्तु के रूप में भी संग्रहीत किया जा सकता है, उनके बीच संबंधों को सरणी में उनकी स्थिति द्वारा निर्धारित किया जाता है(जैसा कि [[द्विआधारी ढेर]] में)। | ||
एक द्विआधारी | एक द्विआधारी ट्री को सूचियों की एक सूची के रूप में लागू किया जा सकता है: एक सूची का प्रमुख(पूर्व पद का मान) बायां बच्चा(उपवृक्ष) है, जबकि पुच्छ(दूसरी और बाद की पदों की सूची) दाहिना बच्चा है( उपवृक्ष)। इसे मूल्यों की अनुमति देने के लिए संशोधित किया जा सकता है, जैसा कि संसाधन [[एस-अभिव्यक्ति]] में है, जहां सिर(पूर्व पद का मान) नोड का मान है, पुच्छ का सिर(दूसरे पद का मान) बायां बच्चा है, और पुच्छ की पुच्छ(तीसरी और बाद की पदों की सूची) दाहिना बच्चा है। | ||
क्रमिक वृक्षों को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा कोडित किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।<ref name="Afanasiev2005"> | क्रमिक वृक्षों को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा कोडित किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।<ref name="Afanasiev2005"> | ||
| Line 137: | Line 137: | ||
== प्रकार सिद्धांत == | == प्रकार सिद्धांत == | ||
संक्षेप डेटा प्रकार के रूप में, संक्षेप | संक्षेप डेटा प्रकार के रूप में, संक्षेप ट्री प्रकार {{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}}(दिए गए मूल्य और बच्चों के साथ मूल नोड वाला वृक्ष)। | ||
== गणितीय शब्दावली == | == गणितीय शब्दावली == | ||
एक संक्षेप के रूप में देखा जाए तो एक | एक संक्षेप के रूप में देखा जाए तो एक ट्री डेटा संरचना एक क्रम किया हुआ ट्री है, सामान्यतः प्रत्येक नोड से जुड़े मूल्यों के साथ। निश्चित रूप से, यह है(यदि गैर-रिक्त होना आवश्यक है): | ||
* मूल दिशा से दूर एक [[जड़ वाला पेड़|जड़ वाला]] वृक्ष(एक अधिक संकीर्ण शब्द एक आर्बोरेसेंस(रेखा-चित्र सिद्धांत) है), जिसका अर्थ है: | * मूल दिशा से दूर एक [[जड़ वाला पेड़|जड़ वाला]] वृक्ष(एक अधिक संकीर्ण शब्द एक आर्बोरेसेंस(रेखा-चित्र सिद्धांत) है), जिसका अर्थ है: | ||
** एक [[निर्देशित ग्राफ|निर्देशित रेखा-चित्र]], | ** एक [[निर्देशित ग्राफ|निर्देशित रेखा-चित्र]], | ||
| Line 157: | Line 157: | ||
* प्रत्येक नोड पर एक मान(कुछ डेटा प्रकार का)। | * प्रत्येक नोड पर एक मान(कुछ डेटा प्रकार का)। | ||
प्रायः वृक्षों में एक निश्चित(अधिक ठीक से, परिबद्ध) [[ब्रांचिंग कारक| | प्रायः वृक्षों में एक निश्चित(अधिक ठीक से, परिबद्ध) [[ब्रांचिंग कारक|ब्रांचिंग में कारक]] ([[आगे की डिग्री|बाह्य परिमाण]]) होता है, विशेष रूप से सदैव दो सन्तान नोड्स होते हैं(संभवतः रिक्त, इसलिए अधिकतम दो गैर-रिक्त सन्तान नोड्स), इसलिए एक द्विआधारी वृक्ष। | ||
रिक्त वृक्षों की अनुमति से कुछ परिभाषाएँ सरल हो जाती हैं, कुछ अधिक जटिल: एक जड़ वाला | रिक्त वृक्षों की अनुमति से कुछ परिभाषाएँ सरल हो जाती हैं, कुछ अधिक जटिल: एक जड़ वाला ट्री गैर-रिक्त होना चाहिए, इसलिए यदि रिक्त वृक्षों को उपरोक्त परिभाषा की अनुमति दी जाती है, तो इसके अतिरिक्त एक रिक्त ट्री या एक जड़ वाला ट्री बन जाता है ...। दूसरी ओर, रिक्त ट्री निश्चित ब्रांच कारक को परिभाषित करना आसान बनाते हैं: रिक्त वृक्षों की अनुमति के साथ, एक द्विआधारी ट्री एक ऐसा ट्री होता है, जिसमें हर नोड में दो बच्चे होते हैं, जिनमें से प्रत्येक एक वृक्ष(संभवतः रिक्त) होता है। ट्री पर संचालन के पूर्ण समूह में विशाख संचालन सम्मिलित होना चाहिए।{{huh|date=April 2022}} | ||
== यह भी देखें == | == यह भी देखें == | ||
* | * ट्री संरचना(सामान्य) | ||
* : श्रेणी: वृक्ष(डेटा संरचनाएं)( अभिकलनात्मक वृक्षों की सूची प्रकार) | * : श्रेणी: वृक्ष(डेटा संरचनाएं)( अभिकलनात्मक वृक्षों की सूची प्रकार) | ||
Revision as of 13:06, 28 February 2023
.svg)
कंप्यूटर विज्ञान में, एक ट्री व्यापक रूप से उपयोग किया जाने वाला संक्षेप डेटा प्रकार है जो जुड़े हुए नोड(कंप्यूटर विज्ञान) के एक समूह के साथ पदानुक्रमित ट्री संरचना का प्रतिनिधित्व करता है। ट्री में प्रत्येक नोड को कई बच्चों(ट्री के प्रकार के आधार पर) से जोड़ा जा सकता है, परन्तु 'मूल' नोड को छोड़कर, जिसका कोई जनक नहीं है, को ठीक से एक जनक से जोड़ा जाना चाहिए। इन बाधाओं का तात्पर्य है कि कोई चक्र या लूप नहीं है(कोई भी नोड उसका स्वयं का पूर्वज नहीं हो सकता है), और यह भी कि प्रत्येक बच्चे को अपने स्वयं के उपट्री के मूल नोड के जैसे माना जा सकता है, जिससे पुनरावृत्ति ट्री पथक्रमण के लिए एक उपयोगी तकनीक बन जाती है। रैखिक डेटा संरचनाओं के विपरीत, कई वृक्षों को एक सीधी रेखा में निकटतम नोड्स के बीच संबंधों द्वारा प्रदर्शित नहीं किया जा सकता है।
द्विआधारी ट्री सामान्यतः उपयोग किया जाने वाला प्रकार है, जो प्रत्येक जनक के लिए अधिकतम दो बच्चों की संख्या को सीमित करता है। जब बच्चों का क्रम निर्दिष्ट किया जाता है, तो यह डेटा संरचना रेखा-चित्र सिद्धांत में एक क्रमिक ट्री से मेल खाती है। अन्य डेटा के लिए मूल्य या सूचक ट्री में प्रत्येक नोड के साथ जुड़ा हो सकता है, या कभी-कभी मात्र 'पत्ती नोड्स' के साथ जुड़ा हो सकता है, जिसमें कोई संतान नहीं है।
संक्षेप डेटा प्रकार को कई विधियों से प्रदर्शित किया जा सकता है, जिसमें जनक की सूची बच्चों के लिए संकेत, जनक के संकेत वाले बच्चों की सूची, या नोड्स की सूची और जनक-बाल संबंधों की एक अलग सूची(एक विशिष्ट प्रकार निकटता सूची )सम्मिलित है। अभ्यावेदन भी अधिक जटिल हो सकते हैं, उदाहरण के लिए निष्पादन के लिए डाटाबेस अनुक्रमणिका या पूर्वजों की सूची का उपयोग करना।
कंप्यूटिंग में उपयोग किए जाने वाले ट्री समान हैं परन्तु वृक्ष(रेखा-चित्र सिद्धांत), वृक्ष(समूह सिद्धांत), और वृक्ष(वर्णनात्मक समूह सिद्धांत) के गणितीय निर्माणों से भिन्न हो सकते हैं।
अनुप्रयोग
वृक्षों का उपयोग सामान्यतः अनुप्रयोगों में पदानुक्रमित डेटा का प्रतिनिधित्व या क्रमभंग करने के लिए किया जाता है जैसे:
- फाइल पद्धति के लिए:
- निर्देशिका संरचना का उपयोग उपनिर्देशिकाओं और फ़ाइलों को व्यवस्थित करने के लिए किया जाता है(प्रतीकात्मक लिंक गैर-ट्री रेखा-चित्ऱ बनाते हैं, जैसा कि एक ही फ़ाइल या निर्देशिका के लिए कई दृढ़ लिंक करते हैं)
- स्टोरेज डिवाइस पर डेटा के खंड आवंटित करने और लिंक करने के लिए प्रयुक्त तंत्र
- वर्ग पदानुक्रम या वंशानुक्रम ट्री ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग में वर्ग(कंप्यूटर प्रोग्रामिंग) के बीच संबंधों को दर्शाता है; एकाधिक वंशानुक्रम गैर-ट्री रेखांकन उत्पन्न करता है
- कंप्यूटर भाषाओं के लिए संक्षेप वाक्य रचना का वृक्ष
- प्राकृतिक भाषा प्रसंस्करण:
- पदव्याख्या वृक्ष
- एक उत्पादक व्याकरण में मॉडलिंग उच्चारण
- वार्तालाप उत्पन्न करने के लिए संवाद वृक्ष
- एक्सएमएल और एचटीएमएल दस्तावेज़ों के दस्तावेज़ ऑब्जेक्ट मॉडल(डीओएम वृक्ष)।
- परीक्षण ट्री डेटा को एक ट्री से संंग्रहीत करता है जो ट्री पथक्रमण के माध्यम से एक कुशल परीक्षण कलन विधि को संभव बनाता है
- द्विआधारी परीक्षण ट्री एक प्रकार का द्विआधारी ट्री है
- डेटा के क्रमबद्ध कलन विधि का प्रतिनिधित्व करना
- कंप्यूटर जनित कल्पना:
- स्थान विभाजन, जिसमें द्विआधारी स्थान विभाजन सम्मिलित है
- डिजिटल रचना
- भंडारण बार्न्स-हट के ट्री आकाशगंगाओं का अनुकरण करते थे
- कार्यान्वयन ढेर(डेटा संरचना)
- नीडित समूह
- टैक्सोनॉमी(सामान्य)एप्लिकेशन जैसे डेवी दशमलव वर्गीकरण जिसमें बढ़ती विशेषता के अनुभाग हों।
- पदानुक्रमित अस्थायी मेमोरी
- आनुवंशिक प्रोग्रामिंग
- पदानुक्रमित गुच्छन
वृक्षों का उपयोग विभिन्न गणितीय संरचनाओं का प्रतिनिधित्व और क्रमभंग करने के लिए किया जा सकता है, जैसे:
- एकपक्षीय रेखा-चित्र(असतत गणित) के माध्यम से पथ | नोड-और -किनारे का रेखा-चित्र(बहु रेखांकन सहित), कई मार्गों में उपयोग किए जाने वाले प्रत्येक रेखा-चित्र नोड के लिए ट्री में कई नोड बनाकर
- कोई पदानुक्रम(गणित)
ट्री संरचनाओं का उपयोग प्रायः चीजों के बीच संबंधों को प्रतिचित्रित करने के लिए किया जाता है, जैसे कि:
- अवयव और उप-घटक जिन्हें विस्फोट-दृश्य आरेखण में देखा जा सकता है
- प्रक्रिया कॉल का उपयोग यह पहचानने के लिए किया जाता है कि प्रोग्राम में कौन से प्रक्रिया् अन्य प्रक्रिया् को गैर-पुनरावर्ती रूप से कॉल करते हैं
- विकास द्वारा प्रजातियों के बीच डीएनए की वंशागति,(लिनक्स वितरण समयरेखा), विभिन्न प्रकार की कारों में डिज़ाइन आदि।
- पदानुक्रमित नामस्थानों की विषय सूची
जेएसओएन और वाईएएमएल दस्तावेज़ों को वृक्षों के रूप में माना जा सकता है, परन्तु सामान्यतः नीडित सूची(संक्षेप डेटा प्रकार) और साहचर्य सरणी द्वारा प्रतिनिधित्व किया जाता है।
शब्दावली
एक नोड(कंप्यूटर विज्ञान) एक संरचना है जिसमें डेटा और अन्य नोड्स के संयोजन हो सकते हैं, जिन्हें कभी-कभी किनारे या लिंक कहा जाता है। एक ट्री में प्रत्येक नोड में शून्य या अधिक बच्चे के नोड होते हैं, जो ट्री में इसके नीचे होते हैं(अभिसमय के अनुसार, वृक्षों को 'अवरोही' नीचे की ओर जाते हुए खींचा जाता है)। एक नोड जिसमें एक बच्चा होता है उसे बच्चे का मूल नोड(या सुपीरियर(पदानुक्रम)) कहा जाता है। शीर्षतम मूल नोड को छोड़कर, जिसमें कोई नहीं है, सभी नोड्स में निश्चित एक जनक है। नोड में कई पूर्वज नोड हो सकते हैं, जैसे कि जनक के जनक। एक ही जनक वाले सन्तान नोड समाभासी नोड होते हैं। सामान्यतः समाभासी का एक क्रम होता है, जिसमें प्रथम पारंपरिक रूप से बाईं ओर खींचा जाता है। कुछ परिभाषाएँ एक ट्री को कोई नोड नहीं होने देती हैं, जिस स्थिति में इसे रिक्त कहा जाता है।
एक आंतरिक नोड(जिसे एक आंतरिक नोड के रूप में भी जाना जाता है, लघु या ब्रांच नोड के लिए इनोड) एक ट्री का कोई भी नोड होता है जिसमें बच्चे के नोड होते हैं। इसी वृक्ष, एक बाह्य नोड(जिसे बाह्य नोड, पत्ती नोड या आवधिक नोड के रूप में भी जाना जाता है) कोई भी नोड होता है जिसमें सन्तान नोड नहीं होता है।
एक नोड की ऊंचाई उस नोड से एक पत्ती के सबसे लंबे नीचे की ओर जाने वाले पथ की लंबाई है। मूल की ऊंचाई ही ट्री की ऊंचाई होती है। एक नोड की गहराई इसकी मूल के पथ की लंबाई है(यानी, इसका 'मूल पथ')। शून्य-आधारित गणना का उपयोग करते समय, मूल नोड की गहराई शून्य होती है, पत्ती नोड्स की ऊंचाई शून्य होती है, और मात्र एक नोड वाले वृक्ष(इसलिए जड़ और पत्ती दोनों) की गहराई और ऊंचाई शून्य होती है। परंपरागत रूप से, एक रिक्त वृक्ष(बिना नोड्स वाला वृक्ष, यदि इसकी अनुमति है) की ऊंचाई -1 है।
प्रत्येक गैर-मूल नोड को अपने स्वयं के उपट्री के मूल नोड के रूप में माना जा सकता है, जिसमें वह नोड और उसके सभी वंशज सम्मिलित हैं।[lower-alpha 1][1]
वृक्षों के साथ प्रयुक्त अन्य शब्द:
- निकटवर्ती
- माता-पिता या बच्चा।
- पूर्वज
- बच्चे से माता-पिता के लिए बार-बार आगे बढ़ने से पहुंचने योग्य नोड।
- वंशज
- माता-पिता से बच्चे के लिए बार-बार आगे बढ़ने पर एक नोड। 'उपबच्चे ' के रूप में भी जाना जाता है।
- परिमाण
- किसी दिए गए नोड के लिए, उसके बच्चों की संख्या। एक पत्ते की आवश्यक रूप से परिमाण शून्य होता है।
- वृक्ष का परिमाण
- वृक्ष का परिमाण पेड़ में नोड का अधिकतम परिमाण है।
- दूरी
- दो नोड्स के बीच सबसे छोटे पथ के किनारों की संख्या।
- स्तर
- एक नोड का स्तर इसके साथ किनारों की संख्या है इसके और रूट नोड के बीच अद्वितीय पथ।[2] शून्य-आधारित गणना का उपयोग करते समय यह गहराई के समान है।
- Width
- एक स्तर में नोड्स की संख्या।
- चौड़ाई
- पत्तों की संख्या।
- वन
- एक या एक से अधिक असंबद्ध वृक्षों का समूह।
- क्रमित वृक्ष
- एक जड़ वाला वृक्ष जिसमें प्रत्येक शीर्ष के बच्चों के लिए एक क्रम निर्दिष्ट किया गया है। कंप्यूटर प्रोग्रामिंग की कला पुस्तक उन्मुखी वृक्ष शब्द का प्रयोग करती है।[3]
- एक वृक्ष का आकार
- वृक्ष में नोड्स की संख्या।
वृक्षों और गैर-वृक्षों के उदाहरण
सामान्य संचालन
- सभी वस्तुओं की गणना करना
- ट्री के एक खंड की गणना
- किसी वस्तु की परीक्षण करना
- ट्री पर एक निश्चित स्थान पर एक नवीन वस्तु जोड़ना
- किसी वस्तु को हटाना
- प्रूनिंग(कलन विधि): ट्री के पूरे खंड को हटाना
- रेखा-चित्र्टिंग(कलन विधि): ट्री में एक पूरा खंड जोड़ना
- किसी भी नोड के लिए मूल ढूँढना
- दो नोड्स के सबसे कम सामान्य पूर्वज का पता लगाना
पथक्रमण और परीक्षण की विधियां
जनक और बच्चों के बीच संबंधों के माध्यम से एक ट्री की वस्तुओं के माध्यम से कदम रखना, ट्री पर चलना कहलाता है, और क्रिया ट्री का चलना है। जब कोई सूचक किसी विशेष नोड पर आता है, तो प्रायः एक संचालन किया जा सकता है। एक क़दम जिसमें प्रत्येक जनक नोड को उसके बच्चों से पूर्व पार किया जाता है, उसे पूर्व-क्रम क़दम कहा जाता है; एक क़दम जिसमें बच्चों को उनके संबंधित जनक से पूर्व पार किया जाता है, क्रमोत्तर क़दम कहा जाता है; एक क़दम जिसमें एक नोड का बायाँ उपवृक्ष, फिर नोड स्वयं, और अंत में इसका दाहिना उपट्री पार किया जाता है, इन-क्रम पथक्रमण कहलाता है।(यह अंतिम परिदृश्य, ठीक दो उपवृक्ष, एक बायाँ उपट्री और एक दाहिना उपट्री का उल्लेख करते हुए, विशेष रूप से एक द्विआधारी ट्री मानता है।) एक स्तर-क्रम क़दम प्रभावी रूप से एक ट्री की संपूर्णता पर चौड़ाई-प्रथम परीक्षण करता है; नोड्स को स्तर से पार किया जाता है, जहां पूर्व मूल नोड का भ्रमण किया जाता है, उसके बाद उसके प्रत्यक्ष बच्चे नोड्स और उनके भाई बहनों के बाद, उसके पोते नोड्स और उनके भाई बहनों आदि के बाद, जब तक ट्री में सभी नोड्स का पता नहीं लगाया जाता है।
प्रतिनिधित्व
वृक्षों का प्रतिनिधित्व करने के कई अलग-अलग विधियां हैं। कार्यरत मेमोरी में, नोड्स सामान्यतः गतिशील मेमोरी आवंटन रिकॉर्ड होते हैं, जो उनके बच्चों, उनके जनक या दोनों के साथ-साथ किसी भी संबंधित डेटा के लिए होते हैं। यदि एक निश्चित आकार का है, तो नोड्स को एक सूची में संग्रहित किया जा सकता है। नोड्स और नोड्स के बीच संबंधों को एक अलग विशेष प्रकार की आसन्न सूची में संग्रहीत किया जा सकता है। संबंधपरक डेटाबेस में, नोड्स को सामान्यतः तालिका पंक्तियों के रूप में दर्शाया जाता है, अनुक्रमित पंक्ति आईडी के साथ जनक और बच्चों के बीच संकेत की सुविधा होती है।
नोड्स को एक सरणी डेटा संरचना में वस्तु के रूप में भी संग्रहीत किया जा सकता है, उनके बीच संबंधों को सरणी में उनकी स्थिति द्वारा निर्धारित किया जाता है(जैसा कि द्विआधारी ढेर में)।
एक द्विआधारी ट्री को सूचियों की एक सूची के रूप में लागू किया जा सकता है: एक सूची का प्रमुख(पूर्व पद का मान) बायां बच्चा(उपवृक्ष) है, जबकि पुच्छ(दूसरी और बाद की पदों की सूची) दाहिना बच्चा है( उपवृक्ष)। इसे मूल्यों की अनुमति देने के लिए संशोधित किया जा सकता है, जैसा कि संसाधन एस-अभिव्यक्ति में है, जहां सिर(पूर्व पद का मान) नोड का मान है, पुच्छ का सिर(दूसरे पद का मान) बायां बच्चा है, और पुच्छ की पुच्छ(तीसरी और बाद की पदों की सूची) दाहिना बच्चा है।
क्रमिक वृक्षों को स्वाभाविक रूप से परिमित अनुक्रमों द्वारा कोडित किया जा सकता है, उदाहरण के लिए प्राकृतिक संख्याओं के साथ।[4]
प्रकार सिद्धांत
संक्षेप डेटा प्रकार के रूप में, संक्षेप ट्री प्रकार T किसी प्रकार के मूल्यों के साथ E संक्षेप वन प्रकार का उपयोग करके परिभाषित किया गया है F(वृक्षों की सूची), कार्यों द्वारा:
- मूल्य: T → E
- बच्चे: T → F
- शून्य:() → F
- नोड: E × F → T
सिद्धांतों के साथ:
- मान(नोड(e, f)) = e
- बच्चे(नोड(e, f)) = f
प्रकार के सिद्धांत के संदर्भ में, एक ट्री एक पुनरावर्ती डेटा प्रकार है जिसे निर्माणकर्ताओं द्वारा परिभाषित किया गया है nil(रिक्त जंगल) और node(दिए गए मूल्य और बच्चों के साथ मूल नोड वाला वृक्ष)।
गणितीय शब्दावली
एक संक्षेप के रूप में देखा जाए तो एक ट्री डेटा संरचना एक क्रम किया हुआ ट्री है, सामान्यतः प्रत्येक नोड से जुड़े मूल्यों के साथ। निश्चित रूप से, यह है(यदि गैर-रिक्त होना आवश्यक है):
- मूल दिशा से दूर एक जड़ वाला वृक्ष(एक अधिक संकीर्ण शब्द एक आर्बोरेसेंस(रेखा-चित्र सिद्धांत) है), जिसका अर्थ है:
- एक निर्देशित रेखा-चित्र,
- जिसका अंतर्निहित अप्रत्यक्ष रेखा-चित्र एक वृक्ष(रेखा-चित्र सिद्धांत) है(कोई भी दो कोने निश्चित एक साधारण पथ से जुड़े हुए हैं),
- एक विशिष्ट मूल के साथ(एक शीर्ष को मूल के रूप में नामित किया गया है),
- जो किनारों पर दिशा निर्धारित करता है(तीर मूल से दूर इंगित करता है; एक किनारे दिया गया है, जिस नोड से किनारे को इंगित करता है उसे जनक कहा जाता है और किनारे को इंगित करने वाले नोड को बच्चे कहा जाता है), साथ में:
- किसी दिए गए नोड के सन्तान नोड्स पर क्रमण, और
- प्रत्येक नोड पर एक मान(कुछ डेटा प्रकार का)।
प्रायः वृक्षों में एक निश्चित(अधिक ठीक से, परिबद्ध) ब्रांचिंग में कारक (बाह्य परिमाण) होता है, विशेष रूप से सदैव दो सन्तान नोड्स होते हैं(संभवतः रिक्त, इसलिए अधिकतम दो गैर-रिक्त सन्तान नोड्स), इसलिए एक द्विआधारी वृक्ष।
रिक्त वृक्षों की अनुमति से कुछ परिभाषाएँ सरल हो जाती हैं, कुछ अधिक जटिल: एक जड़ वाला ट्री गैर-रिक्त होना चाहिए, इसलिए यदि रिक्त वृक्षों को उपरोक्त परिभाषा की अनुमति दी जाती है, तो इसके अतिरिक्त एक रिक्त ट्री या एक जड़ वाला ट्री बन जाता है ...। दूसरी ओर, रिक्त ट्री निश्चित ब्रांच कारक को परिभाषित करना आसान बनाते हैं: रिक्त वृक्षों की अनुमति के साथ, एक द्विआधारी ट्री एक ऐसा ट्री होता है, जिसमें हर नोड में दो बच्चे होते हैं, जिनमें से प्रत्येक एक वृक्ष(संभवतः रिक्त) होता है। ट्री पर संचालन के पूर्ण समूह में विशाख संचालन सम्मिलित होना चाहिए।[clarification needed]
यह भी देखें
- ट्री संरचना(सामान्य)
- : श्रेणी: वृक्ष(डेटा संरचनाएं)( अभिकलनात्मक वृक्षों की सूची प्रकार)
टिप्पणियाँ
- ↑ 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).
संदर्भ
- ↑ Weisstein, Eric W. "Subtree". MathWorld.
- ↑ Susanna S. Epp (Aug 2010). Discrete Mathematics with Applications. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694. ISBN 978-0-495-39132-6.
- ↑ 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.
- ↑ 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.
अग्रिम पठन
- Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp. 308–423.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14(Binary Search Trees, Red–Black Trees, Augmenting Data Structures), pp. 253–320.
बाह्य संबंध
- Data Trees as a Means of Presenting Complex Data Analysis by Sally Knipe on August 8, 2013
- Description from the Dictionary of Algorithms and Data Structures
- CRAN package data.tree – implementation of a tree data structure in the R programming language
- WormWeb.org: Interactive Visualization of the C. elegans Cell Tree – Visualize the entire cell lineage tree of the nematode C. elegans(javascript)
- Binary Trees by L. Allison
