Trouver le kème plus petit élément dans un arbre de recherche binaire de manière optimale

Une solution plus simple serait de faire un afinde de la traversée et de garder trace de l'élément actuellement à imprimer (sans impression). Quand nous atteignons k, Imprimez l'élément et sautez le reste de la traversée de l'arbre.

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); 
}

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;
    }

c'est mon implémentation en C# basée sur l'algorithme ci-dessus je pensais juste que je l'aurais posté pour que les gens puissent mieux comprendre que ça fonctionne pour moi

merci IVlad

une solution plus simple serait de faire une traversée ordonnée et de garder la trace de l'élément actuellement à imprimer avec un compteur K. Quand nous atteindrons k, Imprimez l'élément. Le moteur d'exécution est O(n). Rappelez-vous que le type de retour de fonction ne peut pas être nul, il doit retourner sa valeur actualisée de k après chaque appel récursif. Une meilleure solution serait une TSB augmentée avec une valeur de position triée à chaque noeud.

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;
}

/ / ajouter une version java sans récursion

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();
        }
    }
}

Vous pouvez utiliser itératif afinde traversée: http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal avec une simple vérification de l'élément kth après avoir sorti un noeud de la pile.

donné juste un simple arbre de recherche binaire, à peu près tout ce que vous pouvez faire est de commencer par le plus petit, et de traverser vers le haut pour trouver le bon noeud.

si vous allez faire cela très souvent, vous pouvez ajouter un attribut à chaque noeud indiquant combien de noeuds sont dans son sous-arbre de gauche. En utilisant cela, vous pouvez descendre l'arbre directement au noeud correct.

Récursive En ordre de Marche avec un compteur

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

l'idée est similaire à @prasadvk solution, mais il a quelques lacunes (Voir notes ci-dessous), donc je poste ceci comme une réponse séparée.

// 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 );
}

Notes (et différences avec la solution de @prasadvk):

1. if( counter == k ) l'essai doit être effectué à trois places: a) après le sous-virage à gauche, b) après la racine, et c) après le sous-virage à droite. Il s'agit de s'assurer que l'élément kth est détecté pour tous les emplacements , c'est-à-dire quel que soit le sous-arbre où il se trouve.

2. if( result == -1 ) test requis pour s'assurer que seul l'élément de résultat est imprimé , sinon tous les éléments à partir de la kème plus petite jusqu'à la racine sont imprimés.

Pour pas équilibré à la recherche de l'arbre, il faut O(n) .

Pour équilibré à la recherche de l'arbre, il faut O(k + log n) dans le pire des cas, mais juste O(k) dans Amorti sens.

Ayant et gérant l'entier supplémentaire pour chaque noeud: la taille du sous-arbre donne O (log n) complexité temporelle. Un tel arbre de recherche équilibré est généralement appelé RankTree.

en général, il y a des solutions (basées pas sur l'arbre).

Cordialement.

cela fonctionne bien: status : est le tableau qui tient si l'élément est trouvé. k : est-k-ième élément à être trouvé. count: enregistre le nombre de noeuds parcourus pendant la traversée de l'arbre.

int kth(struct tree* node, int* status, int k, int count)
{
    if (!node) return count;
    count = kth(node->lft, status, k, count);  
    if( status[1] ) return status[0];
    if (count == k) { 
        status[0] = node->val;
        status[1] = 1;
        return status[0];
    }
    count = kth(node->rgt, status, k, count+1);
    if( status[1] ) return status[0];
    return count;
}

bien que ce ne soit certainement pas la solution optimale au problème, c'est une autre solution potentielle que j'ai pensé que certaines personnes pourraient trouver intéressant:

/**
 * Treat the bst as a sorted list in descending order and find the element 
 * in position k.
 *
 * Time complexity BigO ( n^2 )
 *
 * 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) = 
 * 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4
 *
 * @param t The root of the binary search tree.
 * @param k The position of the element to find.
 * @return The value of the element at position k.
 */
public static int kElement2( Node t, int k ) {
    int treeSize = sizeOfTree( t );

    return kElement2( t, k, treeSize, 0 ).intValue();
}

/**
 * Find the value at position k in the bst by doing an in-order traversal 
 * of the tree and mapping the ascending order index to the descending order 
 * index.
 *
 *
 * @param t Root of the bst to search in.
 * @param k Index of the element being searched for.
 * @param treeSize Size of the entire bst.
 * @param count The number of node already visited.
 * @return Either the value of the kth node, or Double.POSITIVE_INFINITY if 
 *         not found in this sub-tree.
 */
private static Double kElement2( Node t, int k, int treeSize, int count ) {
    // Double.POSITIVE_INFINITY is a marker value indicating that the kth 
    // element wasn't found in this sub-tree.
    if ( t == null )
        return Double.POSITIVE_INFINITY;

    Double kea = kElement2( t.getLeftSon(), k, treeSize, count );

    if ( kea != Double.POSITIVE_INFINITY )
        return kea;

    // The index of the current node.
    count += 1 + sizeOfTree( t.getLeftSon() );

    // Given any index from the ascending in order traversal of the bst, 
    // treeSize + 1 - index gives the
    // corresponding index in the descending order list.
    if ( ( treeSize + 1 - count ) == k )
        return (double)t.getNumber();

    return kElement2( t.getRightSon(), k, treeSize, count );
}

signature:

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

appel:

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

définition:

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;
}

voilà mes 2 cents...

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;
 }

C'est ce que je pense et ça marche. Il va s'exécuter en o(log n )

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

Eh bien, nous pouvons tout simplement utiliser l'ordre transversal et pousser l'élément visité sur une pile. pop k nombre de fois, pour avoir la réponse.

nous pouvons aussi nous arrêter après K elements

Solution pour caisse complète de la BST: -

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;
}

le noyau Linux a une excellente structure augmentée de données rouge-noir qui prend en charge les opérations basées sur les grades dans O(log n) sous linux/lib/rbtree.C.

un port Java très rudimentaire se trouve aussi à http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java , avec RbRoot.java et RbNode.Java. Le n'ème élément peut être obtenu en appelant RbNode.nth(RbNode nœud, int n), en passant la racine de l'arbre.

Voici une version concise dans c# que retourne le k-ème plus petit élément, mais nécessite passer k comme argument ref (c'est la même approche que @prasadvk):

Node FindSmall(Node root, ref int k)
{
    if (root == null || k < 1)
        return null;

    Node node = FindSmall(root.LeftChild, ref k);
    if (node != null)
        return node;

    if (--k == 0)
        return node ?? root;
    return FindSmall(root.RightChild, ref k);
}

c'est O(log n) pour trouver le plus petit noeud, puis O(k) pour traverser au noeud k-th, donc C'est O(k + log n).

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

c'est la réponse exacte à cette question:-

1.utilisation de l'ordre transversal on O(n) time 2.utilisation de l'arbre augmenté en k + log N temps

Je n'ai pas pu trouver un meilleur algorithme..alors j'ai décidé d'en écrire un :) Corrigez-moi si c'est faux.

class KthLargestBST{
protected static int findKthSmallest(BSTNode root,int k){//user calls this function
    int [] result=findKthSmallest(root,k,0);//I call another function inside
    return result[1];
}
private static int[] findKthSmallest(BSTNode root,int k,int count){//returns result[]2 array containing count in rval[0] and desired element in rval[1] position.
    if(root==null){
        int[]  i=new int[2];
        i[0]=-1;
        i[1]=-1;
        return i;
    }else{
        int rval[]=new int[2];
        int temp[]=new int[2];
        rval=findKthSmallest(root.leftChild,k,count);
        if(rval[0]!=-1){
            count=rval[0];
        }
        count++;
        if(count==k){
            rval[1]=root.data;
        }
        temp=findKthSmallest(root.rightChild,k,(count));
        if(temp[0]!=-1){
            count=temp[0];
        }
        if(temp[1]!=-1){
            rval[1]=temp[1];
        }
        rval[0]=count;
        return rval;
    }
}
public static void main(String args[]){
    BinarySearchTree bst=new BinarySearchTree();
    bst.insert(6);
    bst.insert(8);
    bst.insert(7);
    bst.insert(4);
    bst.insert(3);
    bst.insert(4);
    bst.insert(1);
    bst.insert(12);
    bst.insert(18);
    bst.insert(15);
    bst.insert(16);
    bst.inOrderTraversal();
    System.out.println();
    System.out.println(findKthSmallest(bst.root,11));
}

}

voici le code java,

max(Nœud racine, int k) - pour trouver kth plus grand

min (racine de Noeud, int k) - pour trouver kth plus petit

static int count(Node root){
    if(root == null)
        return 0;
    else
        return count(root.left) + count(root.right) +1;
}
static int max(Node root, int k) {
    if(root == null)
        return -1;
    int right= count(root.right);

    if(k == right+1)
        return root.data;
    else if(right < k)
        return max(root.left, k-right-1);
    else return max(root.right, k);
}

static int min(Node root, int k) {
    if (root==null)
        return -1;

    int left= count(root.left);
    if(k == left+1)
        return root.data;
    else if (left < k)
        return min(root.right, k-left-1);
    else
        return min(root.left, k);
}

ça marcherait aussi. il suffit d'appeler la fonction avec maxNode dans l'arbre

def k_largest(self, node, k): si k < 0 : return None

si k = = 0: retour nœud autre: k - =1 retour auto.k_largest(de soi.prédécesseur (noeud), k)

je pense que c'est mieux que la réponse acceptée parce qu'il n'a pas besoin de modifier le noeud original de l'arbre pour stocker le nombre de ses noeuds enfants.

nous avons juste besoin d'utiliser la traversée en ordre pour compter le plus petit noeud de gauche à droite, arrêter la recherche une fois que le compte égale à K.

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);
}

utilisant une solution order statistics tree est la plus efficace. Mais si vous ne pouvez pas utiliser un order statistics tree et que vous êtes coincé avec un ancien BST régulier, alors la meilleure approche est de faire une traversée dans l'ordre (comme le souligne prasadvk). Mais sa solution est inadéquate si vous voulez rendre le kème plus petit élément et pas simplement imprimer la valeur. De plus, comme sa solution est récursive, il y a un risque de débordement de la pile. Par conséquent, j'ai écrit une solution java qui renvoie la kème plus petite noeud et utilise une pile pour faire la traversée dans L'ordre. Le temps d'exécution est O(n) tandis que la complexité de l'espace est O(h) où h est la hauteur maximale de l'arbre.

// 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;
}

la meilleure approche existe déjà.Mais je voudrais ajouter un Code simple pour que

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 );
}}

utilisant la classe de résultat auxiliaire pour suivre si le noeud est trouvé et le courant K.

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;
    }
}
}

j'ai écrit une fonction soignée pour calculer le kème plus petit élément. J'utilise l'ordre transversal et s'arrête quand le it atteint le kème plus petit élément.

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);  }}

int RecPrintKSmallest(Node_ptr head,int k){
  if(head!=NULL){
    k=RecPrintKSmallest(head->left,k);
    if(k>0){
      printf("%c ",head->Node_key.key);
      k--;
    }
    k=RecPrintKSmallest(head->right,k);
  }
  return k;
}

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;
    }
}

public static Node kth(Node n, int k){
    Stack<Node> s=new Stack<Node>();
    int countPopped=0;
    while(!s.isEmpty()||n!=null){
      if(n!=null){
        s.push(n);
        n=n.left;
      }else{
        node=s.pop();
        countPopped++;
        if(countPopped==k){
            return node;
        }
        node=node.right;

      }
  }

}