ट्री (डेटा संरचना)

Not to be confused with Trie, a specific type of tree data structure.

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

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

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

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

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

अनुप्रयोग

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

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

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

• एक मनमाना ग्राफ (असतत गणित) के माध्यम से पथ | नोड-एंड-एज ग्राफ (मल्टीग्राफ सहित), कई रास्तों में उपयोग किए जाने वाले प्रत्येक ग्राफ नोड के लिए वृक्ष में कई नोड बनाकर
• कोई पदानुक्रम (गणित)

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

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

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

शब्दावली

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

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

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

शून्य-आधारित गणना का उपयोग करते समय यह गहराई के समान है।

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.

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

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

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

पथक्रमण और परीक्षण के तरीके

Main article: Tree traversal

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

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

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

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

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

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

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

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

कीमत: T → E

बच्चे: T → F

शून्य: () → F

नोड: E × F → T

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

मान (नोड (e, f)) = e

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

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

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

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

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

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

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

यह भी देखें

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

अग्रिम पठन

• 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