algorithm - example - binary search tree program in c



इष्टतम तरीके से एक बाइनरी खोज पेड़ में kth सबसे छोटा तत्व खोजें (20)

मुझे किसी स्थिर / वैश्विक चर का उपयोग किए बिना बाइनरी खोज पेड़ में kth सबसे छोटा तत्व ढूंढना होगा। इसे कुशलतापूर्वक कैसे प्राप्त करें? मेरे दिमाग में जो समाधान है, वह ओ (एन) में ऑपरेशन कर रहा है, सबसे खराब मामला है क्योंकि मैं पूरे पेड़ के इनऑर्डर ट्रैवर्सल करने की योजना बना रहा हूं। लेकिन गहराई से मुझे लगता है कि मैं यहां बीएसटी संपत्ति का उपयोग नहीं कर रहा हूं। क्या मेरा ग्रहण समाधान सही है या क्या कोई बेहतर उपलब्ध है?


Answer #1

एक काउंटर के साथ रिकर्सिव इन-ऑर्डर चलना

Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack

यह विचार @prasadvk समाधान के समान है, लेकिन इसमें कुछ कमियां हैं (नीचे नोट देखें), इसलिए मैं इसे एक अलग उत्तर के रूप में पोस्ट कर रहा हूं।

// Private Helper Macro
#define testAndReturn( k, counter, result )                         \
    do { if( (counter == k) && (result == -1) ) {                   \
        result = pn->key_;                                          \
        return;                                                     \
    } } while( 0 )

// Private Helper Function
static void findKthSmallest(
    BstNode const * pn, int const k, int & counter, int & result ) {

    if( ! pn ) return;

    findKthSmallest( pn->left_, k, counter, result );
    testAndReturn( k, counter, result );

    counter += 1;
    testAndReturn( k, counter, result );

    findKthSmallest( pn->right_, k, counter, result );
    testAndReturn( k, counter, result );
}

// Public API function
void findKthSmallest( Bst const * pt, int const k ) {
    int counter = 0;
    int result = -1;        // -1 := not found
    findKthSmallest( pt->root_, k, counter, result );
    printf("%d-th element: element = %d\n", k, result );
}

नोट्स (और प्रसादव के समाधान से मतभेद):

  1. if( counter == k ) परीक्षण तीन स्थानों पर आवश्यक है: (ए) बाएं-उपट्री के बाद, (बी) रूट के बाद, और (सी) दाएं उपट्री के बाद। यह सुनिश्चित करना है कि सभी स्थानों के लिए kth तत्व का पता लगाया गया हो , यानी यह उपनिवेश के बावजूद स्थित है।

  2. if( result == -1 ) परीक्षण सुनिश्चित करने के लिए केवल परिणाम तत्व मुद्रित किया जाता है , अन्यथा केथ से शुरू होने वाले सभी तत्व रूट तक छोटे होते हैं।


Answer #2

// रिकर्सन के बिना जावा संस्करण जोड़ें

public static <T> void find(TreeNode<T> node, int num){
    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();

    TreeNode<T> current = node;
    int tmp = num;

    while(stack.size() > 0 || current!=null){
        if(current!= null){
            stack.add(current);
            current = current.getLeft();
        }else{
            current = stack.pop();
            tmp--;

            if(tmp == 0){
                System.out.println(current.getValue());
                return;
            }

            current = current.getRight();
        }
    }
}

Answer #3

एक सरल समाधान एक इनऑर्डर ट्रैवर्सल करना होगा और वर्तमान में काउंटर के साथ मुद्रित तत्व का ट्रैक रखना होगा। जब हम के पास पहुंचते हैं, तो तत्व मुद्रित करें। रनटाइम ओ (एन) है। याद रखें कि फ़ंक्शन रिटर्न प्रकार शून्य नहीं हो सकता है, इसे प्रत्येक रिकर्सिव कॉल के बाद के के अपडेट किए गए मान को वापस करना होगा। इसके लिए एक बेहतर समाधान प्रत्येक नोड पर एक क्रमबद्ध स्थिति मूल्य के साथ एक बढ़ाया बीएसटी होगा।

public static int kthSmallest (Node pivot, int k){
    if(pivot == null )
        return k;   
    k = kthSmallest(pivot.left, k);
    k--;
    if(k == 0){
        System.out.println(pivot.value);
    }
    k = kthSmallest(pivot.right, k);
    return k;
}

Answer #4

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

void findK(Node* p, int* k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}

Answer #5

खैर यहाँ मेरा 2 सेंट है ...

int numBSTnodes(const Node* pNode){
     if(pNode == NULL) return 0;
     return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1);
}


//This function will find Kth smallest element
Node* findKthSmallestBSTelement(Node* root, int k){
     Node* pTrav = root;
     while(k > 0){
         int numNodes = numBSTnodes(pTrav->left);
         if(numNodes >= k){
              pTrav = pTrav->left;
         }
         else{
              //subtract left tree nodes and root count from 'k'
              k -= (numBSTnodes(pTrav->left) + 1);
              if(k == 0) return pTrav;
              pTrav = pTrav->right;
        }

        return NULL;
 }

Answer #6

खैर हम आसानी से ऑर्डर ट्रैवर्सल का उपयोग कर सकते हैं और विज़िट किए गए तत्व को स्टैक पर दबा सकते हैं। उत्तर पाने के लिए पॉप बार की संख्या।

हम के तत्वों के बाद भी रोक सकते हैं


Answer #7

नोड पाया जाता है और वर्तमान के ट्रैक करने के लिए सहायक परिणाम वर्ग का उपयोग करना।

public class KthSmallestElementWithAux {

public int kthsmallest(TreeNode a, int k) {
    TreeNode ans = kthsmallestRec(a, k).node;
    if (ans != null) {
        return ans.val;
    } else {
        return -1;
    }
}

private Result kthsmallestRec(TreeNode a, int k) {
    //Leaf node, do nothing and return
    if (a == null) {
        return new Result(k, null);
    }

    //Search left first
    Result leftSearch = kthsmallestRec(a.left, k);

    //We are done, no need to check right.
    if (leftSearch.node != null) {
        return leftSearch;
    }

    //Consider number of nodes found to the left
    k = leftSearch.k;

    //Check if current root is the solution before going right
    k--;
    if (k == 0) {
        return new Result(k - 1, a);
    }

    //Check right
    Result rightBalanced = kthsmallestRec(a.right, k);

    //Consider all nodes found to the right
    k = rightBalanced.k;

    if (rightBalanced.node != null) {
        return rightBalanced;
    }

    //No node found, recursion will continue at the higher level
    return new Result(k, null);

}

private class Result {
    private final int k;
    private final TreeNode node;

    Result(int max, TreeNode node) {
        this.k = max;
        this.node = node;
    }
}
}

Answer #8

पूर्ण बीएसटी मामले के लिए समाधान: -

Node kSmallest(Node root, int k) {
  int i = root.size(); // 2^height - 1, single node is height = 1;
  Node result = root;
  while (i - 1 > k) {
    i = (i-1)/2;  // size of left subtree
    if (k < i) {
      result = result.left;
    } else {
      result = result.right;
      k -= i;
    }  
  }
  return i-1==k ? result: null;
}

Answer #9

मुझे लगता है कि यह स्वीकार किए गए उत्तर से बेहतर है क्योंकि इसे मूल पेड़ नोड को अपने बच्चों के नोड्स की संख्या को स्टोर करने के लिए संशोधित करने की आवश्यकता नहीं है।

बाएं से दाएं छोटे से नोड को गिनने के लिए हमें इन-ऑर्डर ट्रैवर्सल का उपयोग करने की आवश्यकता है, गणना के बाद एक बार गणना बंद हो जाती है।

private static int count = 0;
public static void printKthSmallestNode(Node node, int k){
    if(node == null){
        return;
    }

    if( node.getLeftNode() != null ){
        printKthSmallestNode(node.getLeftNode(), k);
    }

    count ++ ;
    if(count <= k )
        System.out.println(node.getValue() + ", count=" + count + ", k=" + k);

    if(count < k  && node.getRightNode() != null)
        printKthSmallestNode(node.getRightNode(), k);
}

Answer #10

मैंने kth सबसे छोटे तत्व की गणना करने के लिए एक साफ समारोह लिखा था। मैं इन-ऑर्डर ट्रैवर्सल का उपयोग करता हूं और जब यह केथ सबसे छोटे तत्व तक पहुंच जाता है तो बंद हो जाता है।

void btree::kthSmallest(node* temp, int& k){
if( temp!= NULL)   {
 kthSmallest(temp->left,k);       
 if(k >0)
 {
     if(k==1)
    {
      cout<<temp->value<<endl;
      return;
    }

    k--;
 }

 kthSmallest(temp->right,k);  }}

Answer #11

यह भी काम करेगा। बस पेड़ में maxNode के साथ समारोह को बुलाओ

def k_largest (स्वयं, नोड, के): यदि के <0: कोई भी वापस नहीं
अगर के == 0: वापस नोड वापस करें: के - = 1 वापसी self.k_largest (self.predecessor (नोड), के)


Answer #12

यह वही है जो मैं करता हूं और यह काम करता है। यह ओ में चलाएगा (लॉग एन)

public static int FindkThSmallestElemet(Node root, int k)
    {
        int count = 0;
        Node current = root;

        while (current != null)
        {
            count++;
            current = current.left;
        }
        current = root;

        while (current != null)
        {
            if (count == k)
                return current.data;
            else
            {
                current = current.left;
                count--;
            }
        }

        return -1;


    } // end of function FindkThSmallestElemet

Answer #13

यहां विचार की एक रूपरेखा है:

बीएसटी में, नोड T के बाएं उपट्री में केवल T में संग्रहीत मूल्य से छोटे तत्व होते हैं। यदि के बाएं उपट्री में तत्वों की संख्या से छोटा है, तो k सबसे छोटे तत्व को बाएं उपट्री से संबंधित होना चाहिए। अन्यथा, यदि k बड़ा है, तो के वें सबसे छोटे तत्व दाएं उपट्री में हैं।

हम बीएसटी को बढ़ा सकते हैं ताकि इसमें प्रत्येक नोड अपने बाएं उपट्री में तत्वों की संख्या संग्रहीत कर सके (मान लीजिए कि दिए गए नोड के बाएं उपट्री में नोड शामिल है)। जानकारी के इस टुकड़े के साथ, बाएं या दाएं उपट्री में रिकर्स करना है या नहीं, यह तय करने के लिए बाएं उपट्री में तत्वों की संख्या को बार-बार पूछकर पेड़ को पार करना आसान है।

अब, मान लीजिए कि हम नोड टी पर हैं:

  1. यदि k == num_elements (टी का बायां उपट्री) , तो हम जिस उत्तर को खोज रहे हैं वह नोड T में मान है।
  2. यदि k> num_elements (टी के बाएं उपट्री) , तो जाहिर है कि हम बाएं उपट्री को अनदेखा कर सकते हैं, क्योंकि वे तत्व छोटे से छोटे से भी छोटे होंगे। इसलिए, हम सही subtree के छोटे तत्व के k - num_elements(left subtree of T) को खोजने के लिए समस्या को कम करते हैं।
  3. यदि k <num_elements (टी का बायां उपट्री) है , तो केएच सबसे छोटा बाएं उपट्री में कहीं है, इसलिए हम बाएं उपट्री में के सबसे छोटे तत्व को खोजने के लिए समस्या को कम करते हैं।

जटिलता विश्लेषण:

यह O(depth of node) समय लेता है, जो एक संतुलित बीएसटी पर सबसे बुरे मामले में O(log n) है, या एक यादृच्छिक बीएसटी के लिए औसत पर O(log n) होता है।

एक बीएसटी के लिए O(n) भंडारण की आवश्यकता होती है, और तत्वों की संख्या के बारे में जानकारी संग्रहीत करने के लिए यह एक और O(n) लेता है। सभी बीएसटी ऑपरेशंस O(depth of node) समय लेते हैं, और इसमें नोड्स के सम्मिलन, हटाने या घूर्णन के लिए "तत्वों की संख्या" जानकारी को बनाए रखने के लिए O(depth of node) अतिरिक्त समय लगता है। इसलिए, बाएं उपट्री में तत्वों की संख्या के बारे में जानकारी संग्रहीत करना एक बीएसटी की अंतरिक्ष और समय जटिलता रखता है।


Answer #14

लिनक्स कर्नेल में एक उत्कृष्ट संवर्धित लाल-काला पेड़ डेटा संरचना है जो लिनक्स / lib / rbtree.c में ओ (लॉग एन) में रैंक-आधारित संचालन का समर्थन करती है।

एक बहुत कच्चा जावा पोर्ट http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java पर भी पाया जा सकता है, RbRoot.java और RbNode.java के साथ। N'th तत्व पेड़ की जड़ में गुजरने, RbNode.nth (RbNode नोड, int n) को कॉल करके प्राप्त किया जा सकता है।


Answer #15

सबसे अच्छा तरीका पहले से ही है। लेकिन मैं इसके लिए एक साधारण कोड जोड़ना चाहता हूं

int kthsmallest(treenode *q,int k){
int n = size(q->left) + 1;
if(n==k){
    return q->val;
}
if(n > k){
    return kthsmallest(q->left,k);
}
if(n < k){
    return kthsmallest(q->right,k - n);
}

}

int size(treenode *q){
if(q==NULL){
    return 0;
}
else{
    return ( size(q->left) + size(q->right) + 1 );
}}

Answer #16

हस्ताक्षर:

Node * find(Node* tree, int *n, int k);

के रूप में कॉल करें:

*n = 0;
kthNode = find(root, n, k);

परिभाषा:

Node * find ( Node * tree, int *n, int k)
{
   Node *temp = NULL;

   if (tree->left && *n<k)
      temp = find(tree->left, n, k);

   *n++;

   if(*n==k)
      temp = root;

   if (tree->right && *n<k)
      temp = find(tree->right, n, k);

   return temp;
}

Answer #17

http://www.geeksforgeeks.org/archives/10379

यह इस सवाल का सही जवाब है: -

1. ओ (एन) समय पर विकृत ट्रैवर्सल का उपयोग 2. के + लॉग एन समय में Augmented पेड़ का उपयोग करना


Answer #18

order statistics tree का उपयोग करते हुए IVlad समाधान सबसे कुशल है। लेकिन यदि आप order statistics tree उपयोग नहीं कर सकते हैं और नियमित रूप से पुराने बीएसटी के साथ फंस गए हैं तो सबसे अच्छा तरीका इन ऑर्डर ट्रैवर्सल (जैसा कि प्रसादव द्वारा इंगित किया गया है) करना है। लेकिन अगर आप केथ सबसे छोटे तत्व को वापस करना चाहते हैं और न केवल मूल्य को प्रिंट करना चाहते हैं तो उसका समाधान अपर्याप्त है। इसके अलावा, चूंकि उनका समाधान रिकर्सिव है, स्टैक ओवरफ़्लो का खतरा है। इसलिए, मैंने एक जावा समाधान लिखा जो किथ सबसे छोटा नोड देता है और इन ऑर्डर ट्रैवर्सल करने के लिए एक स्टैक का उपयोग करता है। रन टाइम ओ (एन) है जबकि अंतरिक्ष जटिलता ओ (एच) है जहां एच पेड़ की अधिकतम ऊंचाई है।

// The 0th element is defined to be the smallest element in the tree.
public Node find_kth_element(Node root , int k) {

    if (root == null || k < 0) return null;

    Deque<Node> stack = new ArrayDeque<Node>();
    stack.push(root);

    while (!stack.isEmpty()) {

        Node curr = stack.peek();

        if (curr.left != null) {

            stack.push(curr.left);
            continue;
        }

        if (k == 0) return curr;
        stack.pop();
        --k;

        if (curr.right != null) {

            stack.push(curr.right);

        }

    }

    return null;
}

Answer #19
public TreeNode findKthElement(TreeNode root, int k){
    if((k==numberElement(root.left)+1)){
        return root;
    }
    else if(k>numberElement(root.left)+1){
        findKthElement(root.right,k-numberElement(root.left)-1);
    }
    else{
        findKthElement(root.left, k);
    }
}

public int numberElement(TreeNode node){
    if(node==null){
        return 0;
    }
    else{
        return numberElement(node.left) + numberElement(node.right) + 1;
    }
}

Answer #20
public int ReturnKthSmallestElement1(int k)
    {
        Node node = Root;

        int count = k;

        int sizeOfLeftSubtree = 0;

        while(node != null)
        {

            sizeOfLeftSubtree = node.SizeOfLeftSubtree();

            if (sizeOfLeftSubtree + 1 == count)
                return node.Value;
            else if (sizeOfLeftSubtree < count)
            {
                node = node.Right;
                count -= sizeOfLeftSubtree+1;
            }
            else
            {
                node = node.Left;
            }
        }

        return -1;
    }

यह उपरोक्त एल्गोरिदम पर आधारित सी # में मेरा कार्यान्वयन है, मैंने सोचा कि मैं इसे पोस्ट करूंगा ताकि लोग बेहतर समझ सकें कि यह मेरे लिए काम करता है

धन्यवाद Illad





binary-search