त्रिचर ट्री

This article is about rooted trees with three children per node. For unrooted trees with three neighbors per node, see unrooted binary tree.

आकार 10 और ऊँचाई 2 का एक साधारण त्रिगुट वृक्ष।

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

टर्नरी ट्री का उपयोग त्रिगुट खोज वृक्ष और त्रिगुट ढेर को लागू करने के लिए किया जाता है।

परिभाषा

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

- एक नोड p एक नोड q का पूर्वज है यदि यह q से रूट तक पथ पर मौजूद है। नोड q को तब p का वंशज कहा जाता है।

- एक नोड का आकार उसके स्वयं सहित वंशजों की संख्या है।

त्रिगुट वृक्षों के गुण

• नोड्स की अधिकतम संख्या

- होने देना $h$ एक त्रिगुट वृक्ष की ऊंचाई हो।

- होने देना $M(h)$ ऊंचाई एच के एक टर्नरी पेड़ में नोड्स की अधिकतम संख्या हो

h	M(h)
0	1
1	4
2	13
3	40

– $M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}$ – ऊंचाई h के हर पेड़ में ज्यादा से ज्यादा होता है ${\frac {3^{h+1}-1}{2}}$ नोड्स।

• यदि कोई नोड $N$ ट्री पर कब्जा कर लेता है $[k]$, तो इसका लेफ्ट चाइल्ड TREE में स्टोर हो जाता है $[3k-1]$.
• मिड चाइल्ड को TREE में स्टोर किया जाता है $[3k]$.
• राइट चाइल्ड को TREE में स्टोर किया जाता है $[3k+1]$.

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

सम्मिलन

नोड्स को तीन अन्य नोड्स के बीच टर्नरी ट्री में डाला जा सकता है या बाहरी नोड के बाद जोड़ा जा सकता है। टर्नरी पेड़ों में, डाला गया नोड निर्दिष्ट किया जाता है कि यह कौन सा बच्चा है।

बाहरी नोड्स

कहें कि बाहरी नोड को नोड ए पर जोड़ा जा रहा है। नोड ए के बाद एक नया नोड जोड़ने के लिए, ए अपने बच्चों में से एक के रूप में नया नोड असाइन करता है और नया नोड नोड ए को उसके माता-पिता के रूप में असाइन करता है।

आंतरिक नोड्स

बाहरी नोड्स की तुलना में आंतरिक नोड्स पर सम्मिलन अधिक जटिल है। कहें कि आंतरिक नोड नोड ए है और वह नोड बी ए का बच्चा है। ए अपने बच्चे को नए नोड को सौंपता है और नया नोड अपने माता-पिता को ए को सौंपता है। फिर नया नोड अपने बच्चे को बी को सौंपता है और बी अपने माता-पिता को नए नोड के रूप में सौंपता है।

विलोपन

विलोपन वह प्रक्रिया है जिससे पेड़ से एक नोड हटा दिया जाता है। एक टर्नरी ट्री में केवल कुछ नोड्स को स्पष्ट रूप से हटाया जा सकता है।

शून्य या एक बच्चे के साथ नोड

कहें कि हटाने के लिए नोड नोड ए है। यदि किसी नोड में कोई संतान नहीं है (बाहरी नोड), ए के माता-पिता के बच्चे को शून्य सूचक और ए के माता-पिता को शून्य करने के लिए विलोपन पूरा किया जाता है। यदि इसका एक बच्चा है, तो A के बच्चे के माता-पिता को A के माता-पिता के लिए सेट करें और A के माता-पिता के बच्चे को A के बच्चे के लिए सेट करें।

अन्य पेड़ों के साथ तुलना

नीचे दिया गया चित्र एक बाइनरी सर्च ट्री है जो 12 दो-अक्षर वाले शब्दों का प्रतिनिधित्व करता है। बाएं बच्चे के सभी नोड्स में छोटे मान होते हैं, जबकि दाएं बच्चे के सभी नोड्स में सभी नोड्स के लिए अधिक मूल्य होते हैं। जड़ से खोज शुरू होती है। ON शब्द को खोजने के लिए, हम इसकी तुलना IN से करते हैं और सही शाखा लेते हैं। प्रत्येक तुलना दोनों शब्दों के प्रत्येक वर्ण तक पहुँच सकती है।

        में
      / \
     का हो
    / \ / \
   के रूप में है या
    \ \ \ / \
    वह इसे पर

डिजिटल खोज तार के चरित्र को चरित्र से संग्रहीत करने का प्रयास करती है। अगली तस्वीर एक पेड़ है जो 12 शब्दों के समान सेट का प्रतिनिधित्व करती है;

         _ _ _ _ _ _ _ _ _ _ _ _ _ _
        / / / \ \ \
       / / / \ \ \
      ए बी एच आई ओ टी
     / \ / \ | / | \ /|\ |
    एस टी ई वाई ई एन एस टी एफ एन आर ओ
   के रूप में वह में यह पर या करने के लिए है

प्रत्येक इनपुट शब्द उस नोड के नीचे दिखाया जाता है जो इसका प्रतिनिधित्व करता है। लोअर केस अक्षरों के शब्दों का प्रतिनिधित्व करने वाले पेड़ में, प्रत्येक नोड में 26-वे ब्रांचिंग होती है। खोजें बहुत तेज़ हैं: IS की खोज जड़ से शुरू होती है, I शाखा, फिर S शाखा, और वांछित नोड पर समाप्त होती है। प्रत्येक नोड पर, एक सरणी तत्व का उपयोग करता है, शून्य के लिए परीक्षण करता है, और एक शाखा लेता है।

                    मैं
              / | \
             / | \
            बी एस ओ
         / | \ / \ | \
        एक ई एच एन टी एन टी
        | \ | / \ |
        एस वाई ई एफ आर ओ
         \
          टी

उपरोक्त चित्र 12 शब्दों के समान सेट के लिए एक संतुलित त्रिगुट खोज वृक्ष है। निम्न और उच्च पॉइंटर्स को कोण वाली रेखाओं के रूप में दिखाया गया है, जबकि समान पॉइंटर्स को लंबवत रेखाओं के रूप में दिखाया गया है। IS शब्द की खोज जड़ से शुरू होती है, बराबर चाइल्ड को मान S के साथ नोड तक ले जाती है, और दो तुलनाओं के बाद वहीं रुक जाती है। AX के लिए एक खोज पहले अक्षर A से तीन तुलना करती है और दूसरे अक्षर X से दो तुलना करके रिपोर्ट करती है कि शब्द ट्री में नहीं है।

त्रिगुट वृक्षों के उदाहरण

• त्रिगुट खोज वृक्ष
• टर्नरी बाइनरी ट्री
• त्रिगुट ढेर
• सभी आदिम पायथागॉरियन ट्रिपल्स युक्त दो अनंत टर्नरी पेड़ों का वर्णन आदिम पायथागॉरियन ट्रिपल्स का पेड़ और फ़ॉर्मूला_फॉर_जेनरेटिंग_पाइथागोरियन_ट्रिपल्स#पाइथागोरियन_ट्रिपल्स_बाय_यूज_ऑफ_मैट्रिसेस_एंड_लाइनियर_ट्रांसफॉर्मेशन में किया गया है। दोनों पेड़ों में रूट नोड में ट्रिपल [3,4,5] होता है।

यह भी देखें

• बाइनरी ट्री
• वृक्ष संरचना