त्रिचर ट्री

File:Ternary tree.png

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

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

त्रिचर ट्री का उपयोग त्रिचर खोज वृक्ष और त्रिचर अधिकांश को लागू करने के लिए किया जाता है।

परिभाषा

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

- एक नोड पी एक नोड क्यू का पूर्वज है यदि यह क्यू से मूल तक पथ पर उपस्थित है। नोड क्यू को तब पी का वंशज कहा जाता है।

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

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

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

- होने देना $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]$, तो इसका बाएँ बच्चे ट्री में संग्रहित हो जाता है $[3k-1]$.
• मध्य बच्चे को ट्री में संग्रहित किया जाता है $[3k]$.
• दायें बच्चे को ट्री में संग्रहित किया जाता है $[3k+1]$.

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

सम्मिलन

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

बाहरी नोड्स

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

आंतरिक नोड्स

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

विलोपन

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

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

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

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

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

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

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

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

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

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

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

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

• त्रिचर खोज ट्री
• त्रिचर बाइनरी ट्री
• अत्यधिक त्रिचर
• प्राचीन पायथागॉरियन त्रिगुण के ट्री और पाइथागोरियन त्रिगुण जारी करने के सूत्र में सभी प्राचीन पायथागॉरियन त्रिगुण वाले दो अनंत त्रिचर ट्री का वर्णन किया गया है। दोनों ट्री में मूल नोड त्रिगुण में होता है

यह भी देखें

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