मिनिमल ट्री: सॉर्टेड ऐरे से संतुलित बीएसटी (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.२: अद्वितीय पूर्णांकों की सॉर्टेड ऐरे से न्यूनतम ऊँचाई वाला बाइनरी सर्च ट्री बनाओ। मध्य को रूट लो, बाएँ-दाएँ आधे पर रीकर्स करो।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

अद्वितीय संख्याओं की सॉर्टेड पंक्ति पहले से आधा बाइनरी सर्च ट्री है। सवाल सिर्फ यह है कि कौन सा मान रूट बने ताकि पेड़ छोटा रहे। खाली बीएसटी में बाएँ से दाएँ इन्सर्ट करोगे तो ऊँचाई एन का लंबा डंडा मिलता है। ऐरे का मध्य रूट लो, हर आधे पर वही चाल दोहराओ, ऊँचाई लगभग लॉग२(एन) रह जाती है।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली बीएसटी निर्माण परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ४ ग्राफ से खुला; यहाँ ट्री निर्माण जारी है।

१. संतुलित किताबों की उपमा

१ से ७ तक सॉर्टेड किताबों की शेल्फ सोचो:

[1, 2, 3, 4, 5, 6, 7]

चाहिए बाइनरी सर्च ट्री: बायाँ बच्चा हमेशा छोटे मान, दायाँ बड़े। साथ ही पेड़ जितना छोटा हो सके (न्यूनतम ऊँचाई), ताकि खोज लंबी रीढ़ न चले।

अगर १ रूट बनाकर २, ३, ४, ... डालते रहो तो:

ऊँचाई ७। दर्द।

अगर ४ (मध्य) रूट हो, बायाँ आधा [1, 2, 3] बायाँ सबट्री, दायाँ [5, 6, 7] दायाँ। हर आधे पर दोहराओ: बाएँ का मध्य २, दाएँ का ६। ऊँचाई ३ का घना पेड़:

यही पूरा एल्गोरिदम है: मध्य रूट, बाएँ रीकर्स, दाएँ रीकर्स।

२. समस्या सादे शब्दों में

इनपुट: बढ़ते क्रम में अद्वितीय पूर्णांकों की सॉर्टेड ऐरे। उदाहरण: int[] arr = {1, 2, 3, 4, 5, 6, 7}।

आउटपुट: हर मान वाला बाइनरी सर्च ट्री का रूट, संभव न्यूनतम ऊँचाई के साथ।

नोड का आकार:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

नियम और स्पष्टता:

मान अद्वितीय (बाएँ-दाएँ रखने को डुप्लिकेट नहीं)।
ऐरे पहले से आरोही सॉर्टेड। फिर सॉर्ट की ज़रूरत नहीं।
न्यूनतम ऊँचाई मतलब एन अद्वितीय कुंजियों पर बीएसटी जितना संतुलित हो सकता है: भरी आकृति पर ऊँचाई फ्लोर(लॉग२(एन)) + १, या जब एन दो की घात घटा एक न हो तो उसके पास।
खाली रेंज पर null लौटा सकते हो (खाली ऐरे या खाली सबऐरे)।

इंटरव्यू में पूछो

ऐरे गारंटी से सॉर्टेड और अद्वितीय? (इस क्लासिक संस्करण में हाँ।)
पैरेंट पॉइंटर चाहिए? (इस समस्या में नहीं।)
ऐरे के टुकड़े कॉपी या इंडेक्स सीमा? (इंडेक्स साफ, प्रति कॉल ओ(१) अतिरिक्त।)

३. पहले सोचो

सीधा: बाएँ से एक-एक इन्सर्ट

खाली शुरू, इंडेक्स ० से एन-१ तक insert(arr[i])।

सही बीएसटी: हाँ।
ऊँचाई: ओ(एन), क्योंकि सॉर्टेड क्रम हमेशा दाएँ जाता है।
समय: रीबैलेंस वाले इन्सर्ट पर ओ(एन लॉग एन), साधारण इन्सर्ट पर सॉर्टेड इनपुट से ओ(एन²)।

ज़िक्र करो, ऊँचाई लक्ष्य के लिए छोड़ दो।

बेहतर: रूट सोच-समझकर चुनो

बीएसटी में रूट बाएँ-दाएँ सबट्री के बीच बैठता है। सॉर्टेड ऐरे पर कोई भी इंडेक्स mid सबऐरे arr[start..end] का रूट बन सकता है:

बायाँ सबट्री = arr[start..mid-1] का बीएसटी
दायाँ सबट्री = arr[mid+1..end] का बीएसटी

ऊँचाई कम करने के लिए बाएँ-दाएँ लगभग बराबर आकार। मध्य इंडेक्स वही करता है:

mid = (start + end) / 2

(या बहुत बड़ी ऐरे पर ओवरफ्लो से बचने को start + (end - start) / 2)।

बेस केस: start > end हो तो null। उस तरफ कोई नोड नहीं।

संरचना बाइनरी सर्च जैसी, पर खोज के बजाय पेड़ बनाते हो।

वैध बीएसटी क्यों: mid के बाएँ सब छोटे arr[mid] से, दाएँ सब बड़े। रीकर्शन हर सबट्री पर वही रखता है। ऊँचाई न्यूनतम क्यों: हर स्तर लगभग आधे बचे तत्व काटता है, गहराई ओ(लॉग एन)।

४. जावा समाधान

public class MinimalTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    /** Build a minimal-height BST from a sorted unique array. */
    public static TreeNode createMinimalBST(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        return build(arr, 0, arr.length - 1);
    }

    private static TreeNode build(int[] arr, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(arr[mid]);
        node.left = build(arr, start, mid - 1);
        node.right = build(arr, mid + 1, end);
        return node;
    }
}

{1, 2, 3, 4, 5, 6, 7} पर चलन:

कॉल रेंज	मिड इंडेक्स	रूट मान	बाईं रेंज	दाईं रेंज
०..६	३	४	०..२	४..६
०..२	१	२	०..०	२..२
०..०	०	१	खाली	खाली
२..२	२	३	खाली	खाली
४..६	५	६	४..४	६..६
४..४	४	५	खाली	खाली
६..६	६	७	खाली	खाली

नतीजा पेड़ (वही शेल्फ वाला चित्र):

विषम लंबाई ऐरे पर रूट साफ मध्य पर बैठता है। सम लंबाई (जैसे {1, 2, 3, 4}) पूर्णांक भाग से दो केंद्रों में से एक ले सकती है। दोनों न्यूनतम ऊँचाई देते हैं; आकृति थोड़ी बदल सकती है, ऊँचाई वर्ग नहीं।

तैयार पेड़ का इन-ऑर्डर ट्रैवर्सल मूल सॉर्टेड ऐरे वापस छापता है। कोड के बाद तेज़ मानसिक जाँच।

५. जटिलता तालिका

हिस्सा	लागत	क्यों
समय	ओ(एन)	हर ऐरे इंडेक्स ठीक एक नोड बनता है; प्रति इंडेक्स स्थिर काम
अतिरिक्त स्टैक	ओ(लॉग एन)	रीकर्शन गहराई = पेड़ की ऊँचाई
पेड़ स्थान	ओ(एन)	एन नोड संग्रहीत
साधारण सॉर्टेड इन्सर्ट	ओ(एन²) समय, ओ(एन) ऊँचाई	दाईं रीढ़

बाएँ-दाएँ आधे के लिए अतिरिक्त ऐरे नहीं। इंडेक्स सीमाएँ वही arr दोबारा इस्तेमाल करती हैं।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

खाली ऐरे या नल → null लौटाओ।
एक तत्व → एक नोड, दोनों बच्चे नल। ऊँचाई १।
दो तत्व → एक रूट, एक बच्चा (मिड के हिसाब से बायाँ या दायाँ)। ऊँचाई २।
सम लंबाई → कोई भी केंद्र ठीक; एक सूत्र चुनकर समझाओ।
दिमाग में पहले से पेड़ दिखे → फिर भी मध्य वाली रीकर्सिव नियम लिखो; आकार हार्डकोड मत करो।

आम गलतियाँ:

१. खाली बीएसटी में सॉर्टेड मान बाएँ से दाएँ इन्सर्ट। सही बीएसटी, भयानक ऊँचाई। २. हर कॉल पर सबऐरे कॉपी (Arrays.copyOfRange)। चलता है, समय-मेमोरी खर्च। start/end बेहतर। ३. सीमाओं पर एक का अंतर। बायाँ start..mid-1, दायाँ mid+1..end। mid दोबारा शामिल करने से रूट डुप्लिकेट। ४. बहुत बड़े इंडेक्स पर mid = (start + end) / 2। जहाँ इंट ओवरफ्लो हो वहाँ start + (end - start) / 2 (बाइनरी सर्च जैसी आदत)। ५. बेस केस start > end भूलना। अनंत रीकर्शन या नल अराजकता। ६. बीएसटी क्रम बिना हीप-जैसा पूरा पेड़। सिर्फ पूर्णता खोज-क्रम नहीं देती; सॉर्टेड रेंज का मध्य दोनों संतुलन और बीएसटी देता है।

न्यूनतम उपयोग रेखाचित्र:

int[] sorted = {1, 2, 3, 4, 5, 6, 7};
TreeNode root = MinimalTree.createMinimalBST(sorted);
// root.val == 4, left subtree has 1..3, right has 5..7

बनाने के बाद ऊँचाई जाँचने का वैकल्पिक हेल्पर:

static int height(TreeNode n) {
    if (n == null) return 0;
    return 1 + Math.max(height(n.left), height(n.right));
}
// for 7 nodes, height should be 3

७. दोस्त को समझाने वाला सार

मिनिमल ट्री है "सॉर्टेड अद्वितीय ऐरे से सबसे छोटा बीएसटी":

१. ऐरे पहले से सॉर्टेड। रूट के इर्द-गिर्द काटने पर बीएसटी क्रम मुफ्त। २. मौजूदा रेंज का मध्य तत्व रूट। ३. बायाँ आधा बायाँ बच्चा बनाता है। दायाँ आधा दायाँ। ४. खाली रेंज null। एक तत्व पत्ती। ५. समय ओ(एन), ऊँचाई ओ(लॉग एन)। सॉर्टेड कुंजी एक-एक करके मत डालो, नहीं तो डंडा बढ़ेगा।

अगर {1,2,3,4,5,6,7} को ऊपर वाले संतुलित पेड़ में खींच सको और समझा सको कि मध्य "हमेशा पहला तत्व" से क्यों जीतता है, समस्या ४.२ तुम्हारी है। अगला: गहराई के हिसाब से पेड़ चलना।