बीएसटीमधील केटी सर्वात लहान घटक  


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सफरचंद ब्लूमबर्ग फेसबुक Google ओरॅकल
बायनरी शोध वृक्ष बायनरी ट्री झाड

या समस्येमध्ये आम्ही बीएसटी आणि एक नंबर के दिला आहे, बीएसटीमध्ये kth सर्वात लहान घटक शोधा.

उदाहरणे  

इनपुट
वृक्ष [] = {5, 3, 6, 2, 4, निरर्थक, निरर्थक, 1}
के = 3

बीएसटीमधील केटी सर्वात लहान घटक
उत्पादन
3

इनपुट
झाड [] = {3, 1, 4, शून्य, 2
के = 1

बीएसटीमधील केटी सर्वात लहान घटक
उत्पादन
1

बीएसटीमध्ये कॅथचा सर्वात छोटा घटक शोधण्यासाठी भोळसट दृष्टिकोन  

अतिक्रमण करा आडवा बीएसटी च्या आणि तो एक मध्ये ठेवा अॅरे आणि अ‍ॅरेचा kth एलिमेंट परत करा. जसे बीएसटीच्या इनऑर्डर ट्रव्हर्सलचा क्रमवारी लावलेल्या अ‍ॅरेचा परिणाम होतो, म्हणूनच इनऑर्डर ट्रॅव्हर्सलमधील केटीएच घटक म्हणजे केटीएस सर्वात लहान घटक असतो.

  1. पूर्णांकांची एक सूची तयार करा जी बीएसटीच्या अंतर्गत आक्रमणास संचयित करेल.
  2. अतिक्रमण करणारा मार्ग करा
  3. जर रूट रिक्त होत नसेल तर डाव्या मुलासाठी आक्रमक ट्रॅव्हर्सल करा.
  4. सूचीमध्ये सद्य नोडचा डेटा घाला.
  5. योग्य मुलासाठी आवर्तपणे इनऑर्डर ट्रव्हर्सल करा.
  6. शेवटी, यादीतील kth स्थानावर उपस्थित घटक परत करा.

जावा कोड

import java.util.ArrayList;

public class KthSmallestInBST {
    // Class representing node of BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to do in order traversal of BST and store it in array
    private static void inorder(Node root, ArrayList<Integer> traversal) {
        if (root != null) {
            inorder(root.left, traversal);
            traversal.add(root.data);
            inorder(root.right, traversal);
        }
    }

    private static int kthSmallest(Node root, int k) {
        ArrayList<Integer> traversal = new ArrayList<>();
        // Do inorder traversal and store in an array
        inorder(root, traversal);
        
        // Return the kth element of the array
        return traversal.get(k - 1);
    }

    public static void main(String[] args) {
        // Example 1
        Node root = new Node(5);
        root.left = new Node(3);
        root.right = new Node(6);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.left.left.left = new Node(1);
        int k = 3;

        System.out.println(kthSmallest(root, k));

        // Example 2
        Node root2 = new Node(3);
        root2.left = new Node(1);
        root2.right = new Node(4);
        root2.left.right = new Node(2);
        k = 1;

        System.out.println(kthSmallest(root2, k));
    }
}

सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

// Class representing node of BST
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// Function to do in order traversal of BST and store it in array
void inorder(Node *root, vector<int> &traversal) {
    if (root != NULL) {
        inorder(root->left, traversal);
        traversal.push_back(root->data);
        inorder(root->right, traversal);
    }
}

int kthSmallest(Node *root, int k) {
    vector<int> traversal;
    // Do inorder traversal and store in an array
    inorder(root, traversal);
    
    // Return the kth element of the array
    return traversal[k - 1];
}

int main() {
    // Example 1
    Node *root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(6);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->left->left->left = new Node(1);
    int k = 3;
    
    cout<<kthSmallest(root, k)<<endl;
    
    // Example 2
    Node *root2 = new Node(3);
    root2->left = new Node(1);
    root2->right = new Node(4);
    root2->left->right = new Node(2);
    k = 1;
    
    cout<<kthSmallest(root2, k)<<endl;
    
    return 0;
}
3
1

बीएसटीमध्ये केथ सर्वात लहान घटक शोधण्याचे जटिल विश्लेषण

वेळ गुंतागुंत = O (n) 
स्पेस कॉम्प्लेक्सिटी = O (n)
जेथे एनएसटी मध्ये नोड्सची संख्या आहे.

हे सुद्धा पहा
बायनरी शोध वृक्षात किमान मूल्यासह नोड शोधा

बीएसटीमध्ये कॅथचा सर्वात छोटा घटक शोधण्यासाठी इष्टतम दृष्टीकोन  

या समस्येचे निराकरण करण्याचा अधिक चांगला दृष्टीकोन म्हणजे वाढीव बीएसटी वापरणे, म्हणजेच आम्ही डाव्या सबट्रीमध्ये नोड्सची संख्या प्रत्येक नोडसह संचयित करतो. हे लेफ्टकाउंट म्हणून दर्शवा.

  1. झाडाच्या मुळापासून प्रारंभ करा.
  2. जर सद्य नोडची डावीकडील संख्या (के - 1) असेल तर, ही कॅथ सर्वात छोटी नोड असेल तर नोड परत करा.
  3. जर सद्य नोडची डावीकडील संख्या (के - १) पेक्षा कमी असेल तर उजवीकडील उपखंडात शोधा आणि के (के - डावे खाते - 1) म्हणून अद्यतनित करा.
  4. अन्यथा सध्याच्या नोडची डावीकडील संख्या (के - 1) पेक्षा मोठी असल्यास डावीकडील सबट्रीमध्ये शोधा.

वेळ गुंतागुंत = ओ (ह), जेथे एच बीएसटीची उंची आहे

तसेच, बीएसटी मध्ये समाविष्ट करणे हे या रुपात सुधारित केले आहे,
जर नवीन नोड वर्तमान नोडच्या डाव्या सबट्रीमध्ये समाविष्ट करावयाचे असेल तर वर्तमान नोडच्या डाव्या खात्याचे मूल्य 1 ने वाढवावे, अन्यथा आम्ही सामान्य बीएसटीमध्ये समाविष्ट करा.

जावा कोड

public class KthSmallestInBST {
    // class representing Node of augmented BST
    static class Node {
        int data;
        int leftCount;
        Node left, right;

        public Node(int data) {
            this.data = data;
            this.leftCount = 0;
            left = right = null;
        }
    }

    private static Node insert(Node root, int value) {
        // Base Case
        if (root == null) {
            return new Node(value);
        }
        
        // If the new node is to be inserted in the left subtree, increment the leftCount
        // of the current node by 1
        if (value < root.data) {
            root.left = insert(root.left, value);
            root.leftCount++;
        } else if (value > root.data) {
            root.right = insert(root.right, value);
        }
        return root;
    }

    private static int kthSmallest(Node root, int k) {
        // kth smallest element does not exist
        if (root == null) {
            return -1;
        }
        
        // If lefCount is equals to k - 1, this is the kth smallest element
        if (root.leftCount == k - 1) {
            return root.data;
        } else if (root.leftCount > k - 1) {
            // If leftCount is greater than k - 1, search in the left subtree
            return kthSmallest(root.left, k);
        } else {
            // Else search in the right subtree
            return kthSmallest(root.right, k - root.leftCount - 1);
        }
    }

    public static void main(String[] args) {
        // Example 1
        Node root = null;
        root = insert(root, 5);
        root = insert(root, 3);
        root = insert(root, 6);
        root = insert(root, 2);
        root = insert(root, 4);
        root = insert(root, 1);
        int k = 3;

        System.out.println(kthSmallest(root, k));

        // Example 2
        Node root2 = null;
        root2 = insert(root2, 3);
        root2 = insert(root2, 1);
        root2 = insert(root2, 4);
        root2 = insert(root2, 2);
        k = 1;

        System.out.println(kthSmallest(root2, k));
    }
}

सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

// class representing Node of augmented BST
class Node {
    public:
    int data;
    int leftCount;
    Node *left;
    Node *right;
    Node(int d) {
        data = d;
        leftCount = 0;
        left = right = NULL;
    }
};

Node* insert(Node *root, int value) {
    // Base Case
    if (root == NULL) {
        return new Node(value);
    }
    
    // If the new node is to be inserted in the left subtree, increment the 
    // leftCount of the current node by 1
    if (value < root->data) {
        root->left = insert(root->left, value);
        root->leftCount++;
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

int kthSmallest(Node* root, int k) {
    // kth smallest element does not exist
    if (root == NULL) {
        return -1;
    }
    
    // If lefCount is equals to k - 1, this is the kth smallest element
    if (root->leftCount == k - 1) {
        return root->data;
    } else if (root->leftCount > k - 1) {
        // If leftCount is greater than k - 1, search in the left subtree
        return kthSmallest(root->left, k);
    } else {
        // Else search in the right subtree
        return kthSmallest(root->right, k - root->leftCount - 1);
    }
}

int main() {
    // Example 1
    Node *root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 6);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 1);
    int k = 3;
    
    cout<<kthSmallest(root, k)<<endl;
    
    // Example 2
    Node *root2 = NULL;
    root2 = insert(root2, 3);
    root2 = insert(root2, 1);
    root2 = insert(root2, 4);
    root2 = insert(root2, 2);
    k = 1;
    
    cout<<kthSmallest(root2, k)<<endl;
    
    return 0;
}
3
1

संदर्भ

हे सुद्धा पहा
बायनरी झाडाची जास्तीत जास्त खोली