त्रिचर ट्री

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

त्रिगुट ट्री के उदाहरण

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

यह भी देखें

• बाइनरी ट्री
• ट्री संरचना