रैंडम नोड: बीएसटी से समान संभावना वाला चयन (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.११: इन्सर्ट, फाइंड, डिलीट और गेट-रैंडम-नोड वाला बीएसटी बनाओ ताकि हर नोड बराबर संभावना रखे। हर नोड पर सबट्री साइज़ रखो और रैंडम इंडेक्स से चलो।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक लॉटरी चलाते हो जहाँ पारिवारिक वृक्ष का हर व्यक्ति बराबर जीत की संभावना रखे। हर बार विजेता माँगने पर सबको सूची में उतारना काम करता है, पर धीमा और भारी है। अगर हर व्यक्ति पहले से जानता है कि उसके नीचे कितने लोग हैं, तो एक पासा फेंको और चुनी हुई सीट तक पेड़ उतरो। यही रैंडम नोड है।

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

---

१. रोज़मर्रा की उपमा

एक कंपनी का संगठन चार्ट सोचो जो बाइनरी सर्च ट्री भी है (बाएँ की कुंजियाँ छोटी या बराबर, दाएँ की बड़ी)। हर कर्मचारी कार्ड पर:

• उसका नंबर (कुंजी)
• उसके पूरे सबट्री में कितने लोग हैं, खुद समेत (size)

getRandomNode() ऐसा चाहिए कि १० लोग हों तो हर एक की संभावना १/१० हो।

सबट्री साइज़ को सीट गिनती मानो:

१. मौजूदा व्यक्ति पर देखो बाएँ दल में कितनी सीटें हैं। २. ० से size - १ तक कोई सीट नंबर चुनो। ३. सीट बाएँ दायरे में हो तो बाएँ जाओ। ४. ठीक बाएँ गिनती के बराबर हो तो वही व्यक्ति हो। ५. नहीं तो बाएँ सीटें और मौजूदा सीट घटाकर दाएँ जाओ।

एक रैंडम संख्या (या हर स्तर पर एक, वही भाव) सीट चुनती है। इन्सर्ट और डिलीट के बाद साइज़ सीटें सही रखता है।

---

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

बनाओ शुरू से एक बाइनरी सर्च ट्री क्लास, जिसमें:

विधि	अर्थ
insert(value)	बीएसटी में डालो
find(value)	उस कुंजी वाला नोड लौटाओ, या नाल
delete(value)	उस कुंजी का एक नोड हटाओ (अगर हो)
getRandomNode()	सभी नोडों में से समान संभावना से एक नोड लौटाओ

नियम:

• पेड़ में अभी मौजूद हर नोड की संभावना बराबर हो।
• नोड का प्रकार तुम्हारा है, इसलिए अतिरिक्त फ़ील्ड रख सकते हो (यही बात है)।
• खाली पेड़: getRandomNode null लौटाए।

कोड से पहले स्पष्ट करो:

• डुप्लिकेट? (हाँ, इस लेख में: <= बाएँ जाता है।)
• डिलीट से रीबैलेंस? (नहीं। सामान्य बीएसटी डिलीट काफी। size सही रखो।)
• समानता नोडों पर, मानों पर नहीं? (हाँ। एक ही मान के दो नोड दो सीटें हैं।)

---

३. पहले सोचो

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

इंटरव्यूअर ने सिर्फ "बाइनरी ट्री से रैंडम नोड दो" नहीं कहा। कहा कि क्लास शुरू से लिखोगे। संकेत: संरचना बदलो। फ़ील्ड जोड़ो। इन्सर्ट-डिलीट पर अपडेट करो।

विकल्प क: सारे नोड ऐरे में कॉपी (धीमा)

पेड़ घूमो, सूची भरो, list.get(random.nextInt(list.size())) चुनो।

• सही और समान।
• हर कॉल पर समय ओ(एन), जगह ओ(एन)।
• पहला जवाब ठीक। आमतौर पर बेहतर माँगते हैं।

विकल्प ख: नोडों की स्थायी ऐरे

वही विचार, हर इन्सर्ट-डिलीट पर। ऐरे के बीच से हटाना ओ(एन)। कमजोर।

विकल्प ग: हर नोड पर size (मुख्य समाधान)

हर नोड रखे:

size = 1 + size(left) + size(right)

इन्सर्ट पर रास्ते के हर पूर्वज पर size बढ़ाओ (या वापस आते हुए गिनो)।

डिलीट पर संरचना बदलने के बाद साइज़ घटाओ।

getRandomNode पर:

१. रूट नाल हो तो नाल। २. i = random.nextInt(root.size()) लो (दायरा ० .. एन-१)। ३. getIthNode(i) से चलो:

शर्त	क्रिया
i < leftSize	उसी i से बाएँ
i == leftSize	यही नोड लौटाओ
i > leftSize	दाएँ जाओ i - leftSize - 1 से

दाएँ - leftSize - 1 क्यों? पूरा बायाँ सबट्री और मौजूदा नोड छोड़ते हो, इसलिए दायाँ इंडेक्स फिर से ० से गिनता है।

यह "इन-ऑर्डर का आई-वाँ नोड" है, बिना सूची बनाए।

विकल्प घ: हर स्तर पर नया रैंडम

हर नोड पर ० .. size-1 में नया इंडेक्स लो और शाखा चुनो। भी समान। ज़्यादा रैंडम कॉल। एक इंडेक्स वाला घूमना साफ है और इंटरव्यू में काफी।

क्या न करो

• बाएँ/दाएँ/खुद को १/३-१/३-१/३ तय संभावना (टेढ़े पेड़ समानता तोड़ते हैं)।
• सिर्फ रूट साइज़ देखकर बाएँ साइज़ नज़रअंदाज़ (निष्पक्ष चाल नहीं)।
• इन्सर्ट-डिलीट पर size अपडेट भूलना (बाद के चयन झुक जाते हैं)।

---

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

import java.util.Random;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    int size; // nodes in this subtree, including this

    TreeNode(int d) {
        data = d;
        size = 1;
    }

    /** Insert value into this BST subtree. Call on root from Tree. */
    void insertInOrder(int d) {
        if (d <= data) {
            if (left == null) {
                left = new TreeNode(d);
            } else {
                left.insertInOrder(d);
            }
        } else {
            if (right == null) {
                right = new TreeNode(d);
            } else {
                right.insertInOrder(d);
            }
        }
        size++; // this subtree grew by one
    }

    TreeNode find(int d) {
        if (d == data) {
            return this;
        } else if (d < data) {
            return left != null ? left.find(d) : null;
        } else {
            return right != null ? right.find(d) : null;
        }
    }

    /**
     * Return the node at in-order index i (0-based) in this subtree.
     * leftSize seats are on the left, then this node, then the right.
     */
    TreeNode getIthNode(int i) {
        int leftSize = left == null ? 0 : left.size;
        if (i < leftSize) {
            return left.getIthNode(i);
        } else if (i == leftSize) {
            return this;
        } else {
            // skip left subtree and this node
            return right.getIthNode(i - leftSize - 1);
        }
    }

    void refreshSize() {
        int ls = left == null ? 0 : left.size;
        int rs = right == null ? 0 : right.size;
        size = 1 + ls + rs;
    }
}

class Tree {
    private TreeNode root;
    private final Random random = new Random();

    int size() {
        return root == null ? 0 : root.size;
    }

    void insert(int value) {
        if (root == null) {
            root = new TreeNode(value);
        } else {
            root.insertInOrder(value);
        }
    }

    TreeNode find(int value) {
        return root == null ? null : root.find(value);
    }

    TreeNode getRandomNode() {
        if (root == null) {
            return null;
        }
        int i = random.nextInt(size()); // 0 .. N-1
        return root.getIthNode(i);
    }

    /** Delete one occurrence of value. Returns true if something was removed. */
    boolean delete(int value) {
        if (root == null) {
            return false;
        }
        int before = size();
        root = deleteNode(root, value);
        return size() < before;
    }

    private TreeNode deleteNode(TreeNode node, int value) {
        if (node == null) {
            return null;
        }
        if (value < node.data) {
            node.left = deleteNode(node.left, value);
        } else if (value > node.data) {
            node.right = deleteNode(node.right, value);
        } else {
            // found: standard BST delete
            if (node.left == null) {
                return node.right;
            }
            if (node.right == null) {
                return node.left;
            }
            // two children: copy in-order successor, then remove it from the right
            TreeNode succ = minNode(node.right);
            node.data = succ.data;
            node.right = deleteNode(node.right, succ.data);
        }
        node.refreshSize();
        return node;
    }

    private TreeNode minNode(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

चलकर देखो (इन्सर्ट २०, १०, ३०, ५, १५):

        20 (size 5)
       /  \
   10 (3)  30 (1)
   /  \
5(1) 15(1)

• रैंडम i = 0 → २० के बाएँ साइज़ ३, 0 < 3 → १० → बाएँ साइज़ १, 0 < 1 → ५ → बाएँ ०, 0 == 0 → ५।
• रैंडम i = 2 → २० पर leftSize ३, 2 < 3 → १० पर leftSize १, 2 > 1 → दाएँ 2 - 1 - 1 = 0 → १५ → १५।
• रैंडम i = 3 → २० पर 3 == 3 → २०।
• रैंडम i = 4 → दाएँ 4 - 3 - 1 = 0 → ३०।

पाँचों नोड ठीक एक-एक इंडेक्स पर। समान।

बाएँ को leftSize / size, खुद को 1 / size, दाएँ को rightSize / size संभावना क्यों न दें? दे सकते हो। वह बहु-रोल संस्करण है। एक इंडेक्स ऊपर से वही गणित है।

---

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

ऑपरेशन	समय (संतुलित)	समय (सबसे खराब, टेढ़ा)	नोट
insert	ओ(लॉग एन)	ओ(एन)	ऊँचाई का रास्ता + size++
find	ओ(लॉग एन)	ओ(एन)	सामान्य बीएसटी खोज
delete	ओ(लॉग एन)	ओ(एन)	बीएसटी डिलीट + साइज़ रिफ्रेश
getRandomNode	ओ(लॉग एन)	ओ(एन)	एक रैंडम पूर्णांक + चाल
हर बार ऐरे कॉपी	ओ(एन)	ओ(एन)	हमेशा पूरा घूमना

जगह ओ(एन) पेड़ के लिए। size फ़ील्ड प्रति नोड ओ(१)। रैंडम के लिए अतिरिक्त ओ(एन) बफ़र नहीं।

समय ओ(डी) भी कह सकते हो, जहाँ डी गहराई है। संतुलित पेड़ ओ(लॉग एन)। बिना रीबैलेंस क्रम में इन्सर्ट भी सही, बस धीमा।

---

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

इंटरव्यूअर यहाँ छूते हैं:

• खाली पेड़ → getRandomNode नाल। nextInt(0) मत बुलाओ।
• एक नोड → सिर्फ इंडेक्स ०, हमेशा वही।
• सब इन्सर्ट एक तरफ़ → साइज़ सही हों तो समानता बनी रहती है; रास्ता गहरा।
• डुप्लिकेट → हर नोड अपनी सीट। साइज़ नोड गिनता है, अलग कुंजियाँ नहीं।
• रूट / पत्ती / दो बच्चों वाला डिलीट → आकार बदलता है; साइज़ मेल खाना चाहिए।

आम गलतियाँ:

१. बाएँ, खुद, दाएँ को १/३-१/३-१/३। असंतुलित पेड़ में पक्षपात। २. इन्सर्ट रास्ते पर size++ भूलना। रूट साइज़ झूठ बोलता है। ३. डिलीट के बाद साइज़ न सुधारना। वही पक्षपात, समय के साथ बुरा। ४. दाएँ जाते समय i - leftSize बिना अतिरिक्त -1। एक कम-ज़्यादा: मौजूदा नोड ने भी इंडेक्स खाया। ५. गिनते समय मान अद्वितीय मानना। समानता नोडों पर है। ६. साइज़ होते हुए भी पूरी सूची बनाना "सुरक्षा" के लिए। ओ(डी) फायदा फेंकना।

छोटा उपयोग:

Tree tree = new Tree();
tree.insert(20);
tree.insert(10);
tree.insert(30);
TreeNode r = tree.getRandomNode(); // one of 20, 10, 30 with equal chance
tree.delete(10);
TreeNode f = tree.find(30);

---

७. दोस्त को समझाओ सार

रैंडम नोड सिर्फ "रैंडम चुनो" नहीं, ट्री डिज़ाइन समस्या है:

१. बीएसटी क्लास तुम्हारी है, इसलिए हर नोड पर size रखो: उस सबट्री के नोडों की गिनती। २. इन्सर्ट और डिलीट पर साइज़ ईमानदार रखो। ३. getRandomNode ० से एन - १ तक i चुनता है, फिर चलता है: बाएँ अगर i बाएँ गिनती में, मौजूदा अगर बराबर, नहीं तो समायोजित i से दाएँ। ४. यह चाल बिना ऐरे के "इन-ऑर्डर का आई-वाँ नोड" है। ५. समय ऊँचाई पर चलता है। जगह प्रति नोड एक पूर्णांक।

छोटा पेड़ साइज़ के साथ बना सको, इंडेक्स ०..एन-१ नोड से जोड़ सको, और समझा सको कि दाएँ i - leftSize - 1 क्यों है, तो समस्या ४.११ तुम्हारी है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: चेक सबट्री
• अगला: पाथ्स विद सम