पाठ · #5 / 11

बाइनरी पेड़ (Binary Trees)

एक नोड, दो संतान — हर रिकर्सिव डेटा स्ट्रक्चर

Binary tree · traversal orders

pick a traversal → · preorder / inorder / postorder / level

init

value

खुद आज़माएँ: कुछ मान insert कीजिए। फिर हर traversal आज़माइए — preorder, inorder, postorder, level — और देखिए कि पेड़ के नीचे विज़िट का क्रम कैसे जगमगाता है।

यह क्यों मायने रखता है

पदानुक्रमिक (hierarchical) डेटा के लिए पेड़ स्वाभाविक संरचना हैं: फ़ाइल सिस्टम, HTML दस्तावेज़, संगठन-चार्ट, निर्णय-वृक्ष (decision trees)। बाइनरी पेड़ BST, हीप और अभिव्यक्ति पार्सिंग की बुनियाद हैं।

मूल विचार

एक वंश-वृक्ष (family tree) की कल्पना कीजिए, पर जहाँ हर व्यक्ति की अधिक से अधिक दो संतान हों (बाएँ और दाएँ)। एक अकेले मूल पूर्वज (root) से शुरू कीजिए।

यही एक बाइनरी पेड़ है। हर नोड की अधिक से अधिक दो संतान होती हैं।

पेड़ डेटा को व्यवस्थित करने के नए तरीक़े खोलते हैं:

पदानुक्रम: माता-पिता-संतान संबंधों के लिए स्वाभाविक
रिकर्शन: हर उपवृक्ष (subtree) ख़ुद एक पेड़ है — समस्याएँ ख़ूबसूरती से टुकड़ों में बँट जाती हैं
कई रास्ते: रैखिक संरचनाओं से उलट, पेड़ शाखाएँ बनाते हैं

Traversal नोडों को अलग-अलग क्रम में देखते हैं:

Pre-order: नोड को संसाधित करो, फिर संतानें (serialization)
In-order: बायाँ बच्चा, नोड, दायाँ बच्चा (BST में क्रमबद्ध क्रम)
Post-order: पहले संतानें, फिर नोड (deletion)
Level-order: एक क़तार से परत-दर-परत (BFS)

मुख्य बातें

हर नोड की अधिक से अधिक 2 संतान होती हैं (बाएँ और दाएँ)
ऊँचाई (height) कुशलता तय करती है — संतुलित होने पर O(log n), असंतुलित होने पर O(n) तक
चार traversal क्रम: pre-order, in-order, post-order, level-order
BST, हीप, अभिव्यक्ति-वृक्षों की बुनियाद

और गहराई में

एक पूर्ण (complete) बाइनरी पेड़ अगला स्तर शुरू करने से पहले हर स्तर को भर देता है (आख़िरी स्तर शायद अपवाद हो)। एक भरा हुआ (full) बाइनरी पेड़ वह है जिसमें हर नोड के 0 या 2 बच्चे हों। एक परिपूर्ण (perfect) बाइनरी पेड़ complete और full दोनों होता है। ये भेद हीप इम्प्लीमेंटेशन (जिसके लिए complete ज़रूरी है) और पेड़ संतुलन के लिए मायने रखते हैं।

"स्तर k पर अधिकतम नोड = 2ᵏ" वाला सूत्र आगमन (induction) से निकल आता है: स्तर 0 पर एक नोड होता है (root); हर स्तर पर पिछले से अधिक से अधिक दुगुने। स्तर 0 से ऊँचाई h तक गुणोत्तर श्रेणी जोड़ने पर अधिकतम 2^(h+1) − 1 नोड मिलते हैं। उलट दीजिए: n नोडों का एक संतुलित पेड़ ⌊log₂ n⌋ ऊँचाई का होता है।

असल दुनिया में

फ़ाइल सिस्टम। डायरेक्टरियाँ एक पेड़ बनाती हैं (कुछ symlink इसे एक DAG बना देते हैं)। find / बस एक पेड़ traversal है।
DOM पेड़। हर HTML दस्तावेज़ एक पेड़ है; CSS selector और DOM query traversal पैटर्न हैं। getElementById ऊपर से चढ़ी एक हैश-टेबल है ताकि lookup O(1) हो जाए।
ग्राफ़िक्स + रोबोटिक्स में scene graph। किसी रोबोट का URDF (Unified Robot Description Format) joint से जुड़े link का एक पेड़ है; किसी हाथ की pose को विश्व-फ़्रेम में निकालना पत्ती से जड़ तक चलते हुए मैट्रिक्स गुणनों की एक ज़ंजीर है।
Octree और KD-tree। स्थानिक उपविभाजन (spatial subdivision) पेड़ टक्कर-पहचान (collision detection), point-cloud nearest-neighbor (हर SLAM सिस्टम इस्तेमाल करता है), और ray tracing को शक्ति देते हैं।
अभिव्यक्ति-वृक्ष। हर कंपाइलर स्रोत-कोड को एक AST में बदलता है — एक पेड़ जहाँ operator भीतरी नोड हैं और operand पत्तियाँ। traversal का क्रम आपकी मूल्यांकन रणनीति चुनता है।

गणितीय ब्यौरा

Tree properties: max nodes at level k 2ᵏ; max nodes in tree, height h 2ʰ⁺¹ − 1; min height, n nodes ⌊log₂ n⌋; max height (degenerate) n − 1
Traversal time: O(n) — हर नोड ठीक एक बार देखा जाता है
Space: recursive traversal O(h) कॉल स्टैक पर; iterative (BFS) O(w) जहाँ w सबसे चौड़ा स्तर है

क्रियान्वयन (Implementation)

बाइनरी पेड़ नोड

struct TreeNode<T> {
    data: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

// In-order traversal (recursive)
fn inorder(node: Option<&Box<TreeNode<T>>>) {
    if let Some(n) = node {
        inorder(n.left.as_ref());
        process(n.data);
        inorder(n.right.as_ref());
    }
}

Traversal क्रम

Pre-order: नोड -> बायाँ -> दायाँ
In-order: बायाँ -> नोड -> दायाँ
Post-order: बायाँ -> दायाँ -> नोड
Level-order: क़तार के साथ BFS

अभ्यास

तीन सवाल, हर एक अलग रिकर्शन आकार सिखाता है:

Maximum Depth — आसान · सीधी दो-पंक्ति रिकर्शन (1 + max(left, right)); वह वार्म-अप जिससे हर पेड़ इंटरव्यू शुरू होता है
Level-Order Traversal — मध्यम · पेड़ क़तार से मिलता है; स्तर वापस पाने के लिए "आकार का स्नैपशॉट" तरकीब वाला BFS
Diameter of Binary Tree — मध्यम · "प्रति-रिकर्शन दो मान" पैटर्न — ऊँचाई लौटाओ, और सबसे अच्छे को side-effect से अद्यतन करो

→ सभी अभ्यास सवाल देखें

🌳 बाइनरी पेड़ (Binary Trees)