This post is also available in: English العربية (Arabic)
इस आलेख में “6 विशेष प्रकार के बाइनरी ट्री बच्चों को समझाए गए”, हम आपको डेटा संरचना (डेटा स्ट्रक्चर) में विभिन्न बाइनरी ट्री के प्रकार के बारे में बताएँगे। इन विभिन्न प्रकार के बाइनरी ट्री के बारे में जानें और लेख के अंत में एक प्रश्नोत्तरी में प्रश्नों के उत्तर दें। आइए पहले समझते हैं कि डेटा संरचना (डेटा स्ट्रक्चर) में ट्री क्या है?
डेटा स्ट्रक्चर में ट्री क्या होता है?
कई प्रकार की डेटा संरचनाएं होती हैं जैसे ऐरे, लिंक्ड लिस्ट, स्टैक और क्यू। ये सभी डेटा स्ट्रक्चर लीनियर डेटा स्ट्रक्चर होते हैं। लीनियर डेटा स्ट्रक्चर के अलावा, एक और प्रकार होता है। और यह होता है – नॉन-लीनियर डेटा स्ट्रक्चर।
एक लीनियर डेटा स्ट्रक्चर डेटा को क्रमिक रूप से संग्रहीत करता है, जबकि एक नॉन-लीनियर डेटा स्ट्रक्चर डेटा को क्रमिक रूप से डेटा को संग्रहीत नहीं करता है।
नॉन-लीनियर डेटा स्ट्रक्चर लीनियर डेटा स्ट्रक्चर से अधिक लाभदायक इसलिए है क्योंकि नॉन-लीनियर डेटा स्ट्रक्चर की प्रोसेसिंग में कम समय लगता है। यही कारण है कि नॉन-लीनियर डेटा स्ट्रक्चर डेटा को त्वरित और आसान एक्सेस की अनुमति देती हैं।
ट्री एक नॉन-लीनियर पदानुक्रमित डेटा संरचना है जिसमें किनारों में नोड्स जुड़े होते हैं।
ट्री शब्दावली
नोड (Node) एक इकाई है जिसमें एक कुंजी या मान होता है और अन्य नोड्स को इंगित करता है।
एज (Edge) दो नोड्स के बीच की एक कड़ी होती है।
रुट (Root) एक ट्री की सबसे ऊपरी नोड होती है।
प्रत्येक पथ के अंतिम नोड्स को लीफ (Leaf) नोड्स या बाहरी नोड्स (Exterior Node) कहा जाता है।
जो नोड्स लीफ नोड्स नहीं होते हैं उन्हें आंतरिक नोड्स (Interior Nodes) कहा जाता है।
एक नोड की ऊंचाई (हाइट ऑफ़ नोड) नोड से सबसे गहरी लीफ तक किनारों की संख्या है (यानी, नोड से लीफ नोड के लिए सबसे लंबा पथ)।
एक नोड की गहराई (डेप्थ ऑफ़ नोड) रुट से नोड तक किनारों (एज) की संख्या होती है।
एक ट्री की ऊंचाई (हाइट ऑफ़ ट्री) रुट नोड की ऊंचाई या सबसे गहरी नोड की गहराई होती है।
एक नोड की डिग्री उस नोड की शाखाओं की कुल संख्या है।
यदि A और B दो नोड हैं, तो नोड B की ऊँचाई n है और नोड A की (n – 1) है, तो A को B का पैरेंट नोड (Parent Node) कहा जाता है, और B को A का चाइल्ड नोड (Child Node) कहा जाता है।
यदि उनकी गहराई समान है, तो दो नोड्स को सिब्लिंग्स (Siblings) कहा जाता है।
सभी नोड्स जिनकी गहराई किसी भी दिए गए नोड X की गहराई से अधिक है, उन्हें नोड X के डेसेंडेंट नोड्स (Descendent Nodes) कहा जाता है। उसी तरह, सभी नोड्स जिनकी गहराई किसी भी दिए गए नोड X की गहराई से कम है, नोड के एंसेस्टर नोड्स (Ancestor Nodes) कहलाते हैं।
बाइनरी ट्री क्या होता है?
बाइनरी ट्री एक ट्री डेटा स्ट्रक्चर है जिसमें प्रत्येक पैरेंट नोड में अधिकतम दो चाइल्ड नोड्स (0, 1, या 2) हो सकते हैं।
बाइनरी ट्री के प्रकार
निम्नलिखित विभिन्न प्रकार के बाइनरी ट्री होते हैं:
- फुल बाइनरी ट्री (Full Binary Tree): फुल बाइनरी ट्री एक विशेष प्रकार का बाइनरी ट्री है जिसमें प्रत्येक नोड में दो चाइल्ड नोड या एक भी चाइल्ड नोड नहीं होता है। हम यह भी कह सकते हैं कि फुल बाइनरी ट्री एक बाइनरी ट्री है, जिसमें लीफ नोड्स को छोड़कर सभी नोड्स में दो चाइल्ड नोड्स होते हैं। (लीफ नोड्स बाहरी नोड्स हैं और इसलिए कोई चाइल्ड नोड नहीं है)
2. कम्पलीट बाइनरी ट्री (Complete Binary Tree): एक बाइनरी ट्री कम्पलीट बाइनरी ट्री तब होता है यदि सभी स्तर पूरी तरह से भरे हुए हैं, संभवत: अंतिम स्तर को छोड़कर और अंतिम स्तर में सभी कुंजियां बाईं ओर होती हैं।
3. परफेक्ट बाइनरी ट्री (Perfect Binary Tree): एक बाइनरी ट्री को परफेक्ट बाइनरी ट्री तब कहा जाता है जिसमें सभी आंतरिक नोड्स में दो चाइल्ड नोड्स होते हैं और सभी लीफ नोड एक ही स्तर पर होते हैं।
4. बैलेंस्ड बाइनरी ट्री (Balanced Binary Tree): एक बाइनरी ट्री को बैलेंस्ड बाइनरी ट्री तब कहा जाता है जिसमें प्रत्येक नोड के लिए बाएँ और दाएँ सब-ट्री के बीच का अंतर 0 या 1 होता है।
5. डीजेनरेट (या पैथोलॉजिकल) बाइनरी ट्री (Degenerate Binary Tree): एक बाइनरी ट्री जहां हर आंतरिक नोड में केवल एक चाइल्ड नोड होता है। इस प्रकार के बाइनरी ट्री का प्रदर्शन एक लिंक्ड लिस्ट के समान होता है।
6. स्क्वीड बाइनरी ट्री (Skewed Binary Tree): एक बाइनरी ट्री जहां हर आंतरिक नोड में केवल एक चाइल्ड नोड होता है। यदि सभी आंतरिक नोड्स में एक बाएं चाइल्ड नोड होता है, तो इसे लेफ्ट स्केव्ड बाइनरी ट्री (Left Skewed Binary Tree) कहा जाता है और यदि सभी आंतरिक नोड्स में एक सही चाइल्ड नोड होता है, तो इसे राइट स्क्यूड बाइनरी ट्री (Right Skewed Binary Tree) कहा जाता है।
C++ में बाइनरी ट्री को लागू करना
एक बाइनरी ट्री में निम्नलिखित घटक होते हैं:
- एक बायाँ सबट्री
- एक रूट नोड
- एक बायाँ सबट्री
C ++ में बाइनरी ट्री बनाने के लिए निम्न कोड का उपयोग किया जाता है:
struct node
{
int key_value;
node *left;
node *right;
};
रूट में key_value होती है और यह दो अन्य नोड्स की ओर पॉइंट करता है – एक बाईं ओर और दूसरा दाईं ओर।
बाइनरी ट्री के उपयोग
ऐरे और लिंक्ड लिस्ट के विपरीत, जो रैखिक डेटा संरचनाएं हैं, ट्री एक पदानुक्रमित (या गैर-रैखिक) डेटा संरचना है।
- बाइनरी ट्री का उपयोग करने का एक कारण यह हो सकता है कि आप जानकारी को संग्रहीत करना चाहते हैं जो स्वाभाविक रूप से एक पदानुक्रम बनाता है। उदाहरण के लिए कंप्यूटर पर फ़ाइल सिस्टम को लागू करना।
- यदि हम एक ट्री के रूप में कुंजियों को व्यवस्थित करते हैं, तो हम लीनियर डेटा स्ट्रक्चर्स की तुलना में बाइनरी सर्च ट्री में किसी दिए गए कुंजी शीघ्र खोज सकते हैं।
