डेटा स्ट्रक्चर में ट्री: बाइनरी ट्री और बाइनरी सर्च ट्री

ट्री क्या है?

ट्री ऊपर से नीचे वाली बनावट में डेटा रखने का तरीका है। हर चीज़ एक नोड में रहती है। नोड्स किनारों (edges) से जुड़ते हैं।

• रूट (मूल): सबसे ऊपर का एक नोड। इसका कोई पैरेंट नहीं।
• पैरेंट और चाइल्ड: ठीक ऊपर वाला नोड पैरेंट; ठीक नीचे वाले उसके बच्चे।
• सिबलिंग: एक ही पैरेंट के बच्चे।
• लीफ (पत्ती): जिसका कोई बच्चा नहीं। आंतरिक नोड: जिसका कम से कम एक बच्चा हो।
• सबट्री: कोई नोड और उसके नीचे का सब कुछ।

ट्री में कोई लूप नहीं होता और किन्हीं दो नोड्स के बीच ठीक एक रास्ता होता है। n नोड हों तो किनारे हमेशा n − 1।

स्तर, गहराई, ऊँचाई और डिग्री

नोड की गहराई = रूट से उस तक के किनारों की संख्या। रूट की गहराई 0। एक ही गहराई वाले नोड एक स्तर (level) बनाते हैं।

ट्री की ऊँचाई = किसी भी पत्ती की सबसे बड़ी गहराई। सिर्फ़ रूट वाले ट्री की ऊँचाई 0। (कुछ किताबें किनारों की जगह नोड गिनती हैं, तो 1 जुड़ जाता है। नियम हमेशा देख लें।)

नोड की डिग्री = उसके बच्चों की संख्या।

रूटेड ट्री को रखना: पैरेंट ऐरे

नोड्स को 1 से n तक नंबर दें। हर नोड के आगे उसका पैरेंट लिखें; रूट के लिए 0। उदाहरण: नोड 1..5 का पैरेंट ऐरे [0, 1, 1, 2, 2] है, तो 1 रूट है, 2 और 3 नोड 1 के बच्चे, 4 और 5 नोड 2 के बच्चे। जो नोड कभी पैरेंट के रूप में नहीं आता वह पत्ती है (यहाँ 3, 4, 5)। दूसरा तरीका चाइल्ड लिस्ट है।

बाइनरी ट्री

बाइनरी ट्री में हर नोड के अधिकतम दो बच्चे होते हैं: बायाँ और दायाँ।

• फुल बाइनरी ट्री: हर नोड के 0 या 2 बच्चे।
• कम्प्लीट बाइनरी ट्री: आख़िरी को छोड़ सब स्तर भरे, आख़िरी बाएँ से भरा।
• परफ़ेक्ट बाइनरी ट्री: सारे स्तर पूरे भरे। ऊँचाई h हो तो नोड = 2^h+1 − 1।

स्तर k पर अधिकतम 2^k नोड हो सकते हैं। कोड में नोड एक रिकॉर्ड होता है: key, left, right (बच्चा न हो तो खाली/None)।

बाइनरी सर्च ट्री (BST)

BST वह बाइनरी ट्री है जिसमें हर नोड पर एक नियम है: बाईं सबट्री की सारी कुंजियाँ छोटी, दाईं की सारी बड़ी।

खोज (Search)

रूट से शुरू करें। कुंजी बराबर हो तो रुकें। छोटी हो तो बाएँ, बड़ी हो तो दाएँ जाएँ। खाली जगह पहुँचे तो कुंजी नहीं है।

जोड़ना (Insert)

कुंजी को खोजें; जहाँ खोज ट्री से बाहर गिरे, वहाँ नई पत्ती जोड़ दें।

संतुलित BST में n नोड हों तो खोज लगभग log₂ n कदम लेती है (10 लाख कुंजियाँ → लगभग 20 जाँच)। अगर कुंजियाँ पहले से क्रम में (10, 20, 30, …) डालें तो BST लंबी चेन बन जाता है और खोज धीमी (n कदम) हो जाती है।

ट्री ट्रैवर्सल

ट्रैवर्सल में हर नोड पर ठीक एक बार जाते हैं।

• प्री-ऑर्डर: रूट, फिर बायाँ, फिर दायाँ। ट्री की कॉपी बनाने में काम आता है।
• इन-ऑर्डर: बायाँ, रूट, दायाँ। BST पर कुंजियाँ क्रम से छपती हैं।
• पोस्ट-ऑर्डर: बायाँ, दायाँ, रूट। ट्री मिटाने या फ़ोल्डर का साइज़ जोड़ने में काम आता है।
• लेवल-ऑर्डर: स्तर-दर-स्तर, बाएँ से दाएँ, क्यू (queue) की मदद से।

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.key)
    inorder(node.right)

घर पर करके देखें

सात पर्चियों पर 50, 30, 70, 20, 40, 60, 80 लिखिए। BST नियम से उन्हें एक-एक करके फ़र्श पर रखिए। फिर इन-ऑर्डर में उठाइए और देखिए कि वे क्रम से आती हैं। अब 10, 20, 30, 40 डालकर देखिए: कैसी आकृति बनती है?

मुख्य सूत्र और परिभाषाएँ

• ट्री में किनारे = नोड − 1
• बाइनरी ट्री के स्तर k पर अधिकतम नोड = 2^k
• ऊँचाई h वाले बाइनरी ट्री में अधिकतम नोड = 2^(h+1) − 1
• संतुलित BST में खोज ≈ log₂ n कदम
• प्री: रूट-बायाँ-दायाँ; इन: बायाँ-रूट-दायाँ; पोस्ट: बायाँ-दायाँ-रूट

हल किए गए उदाहरण

आम गलतियाँ

• ऊँचाई कहीं नोड में और कहीं किनारों में गिनना। एक नियम (यहाँ: किनारे) चुनकर उसी पर टिके रहें।
• सोचना कि BST में नोड की तुलना सिर्फ़ पैरेंट से होती है। नियम पूरी बाईं और दाईं सबट्री पर लागू होता है।
• प्री-ऑर्डर और पोस्ट-ऑर्डर में उलझना। याद रखें रूट कहाँ है: PRE = पहले, POST = आख़िर में।
• मानना कि BST हमेशा तेज़ है। क्रम से डाला गया इनपुट चेन बना देता है, तब खोज लिस्ट जितनी धीमी।