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

J'ai besoin de trouver le kème plus petit élément dans l'arbre de recherche binaire sans utiliser de variable statique / globale. Comment y parvenir efficacement? La solution que j'ai dans mon esprit est de faire l'opération en O (n), le pire des cas puisque je prévois de faire une traversée en ordre de l'arbre entier. Mais au fond, je sens que je n'utilise pas la propriété BST ici. Ma solution hypothétique est-elle correcte ou existe-t-il une meilleure solution disponible?

Voici juste un aperçu de l'idée:

Dans un BST, le sous-arbre gauche du nœud Tcontient uniquement des éléments plus petits que la valeur stockée dans T. Si kest inférieur au nombre d'éléments dans le sous-arbre de gauche, le ke plus petit élément doit appartenir au sous-arbre de gauche. Sinon, si kest plus grand, alors le ke plus petit élément se trouve dans le sous-arbre de droite.

Nous pouvons augmenter le BST pour que chaque nœud qu'il contient stocke le nombre d'éléments dans son sous-arbre gauche (supposons que le sous-arbre gauche d'un nœud donné inclut ce nœud). Avec cette information, il est simple de parcourir l'arborescence en demandant à plusieurs reprises le nombre d'éléments dans le sous-arbre de gauche, pour décider s'il faut récurer dans le sous-arbre de gauche ou de droite.

Maintenant, supposons que nous soyons au nœud T:

1. Si k == num_elements (sous-arbre gauche de T) , alors la réponse que nous recherchons est la valeur dans node T.
2. Si k> num_elements (sous-arbre gauche de T) , alors évidemment nous pouvons ignorer le sous-arbre gauche, car ces éléments seront également plus petits que le ke plus petit. Ainsi, nous réduisons le problème à la recherche du k - num_elements(left subtree of T)plus petit élément du bon sous-arbre.
3. Si k <num_elements (sous-arbre gauche de T) , alors le ke plus petit se trouve quelque part dans le sous-arbre gauche, nous réduisons donc le problème à trouver le ke plus petit élément dans le sous-arbre gauche.

Analyse de complexité:

Cela prend du O(depth of node)temps, ce qui est O(log n)dans le pire des cas sur un BST équilibré, ou O(log n)en moyenne pour un BST aléatoire.

Un BST nécessite un O(n)stockage, et il en faut un autre O(n)pour stocker les informations sur le nombre d'éléments. Toutes les opérations BST prennent du O(depth of node)temps, et il faut O(depth of node)plus de temps pour conserver les informations de «nombre d'éléments» pour l'insertion, la suppression ou la rotation des nœuds. Par conséquent, le stockage des informations sur le nombre d'éléments dans le sous-arbre de gauche conserve la complexité spatiale et temporelle d'un BST.

Une solution plus simple serait de faire une traversée dans l'ordre et de garder une trace de l'élément actuellement à imprimer (sans l'imprimer). Lorsque 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 le publierais pour que les gens puissent mieux comprendre que cela fonctionne pour moi

merci IVlad

Une solution plus simple serait de faire une traversée dans l'ordre et de garder une trace de l'élément actuellement à imprimer avec un compteur k. Lorsque nous atteignons k, imprimez l'élément. Le runtime est O (n). Rappelez-vous que le type de retour de fonction ne peut pas être void, il doit renvoyer sa valeur mise à jour de k après chaque appel récursif. Une meilleure solution à cela serait un BST augmenté avec une valeur de position triée à chaque nœud.

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

// ajoute une version java sans récursivité

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 la traversée itérative dans l'ordre: http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal avec une simple vérification du kème élément après avoir sorti un nœud de la pile.

Étant donné juste un arbre de recherche binaire simple, tout ce que vous pouvez faire est de commencer par le plus petit et de traverser vers le haut pour trouver le bon nœud.

Si vous comptez faire cela très souvent, vous pouvez ajouter un attribut à chaque nœud indiquant le nombre de nœuds dans sa sous-arborescence de gauche. En utilisant cela, vous pouvez descendre l'arborescence directement vers le nœud correct.

Marche dans l'ordre récursive 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 à la solution @prasadvk, mais elle présente quelques lacunes (voir les notes ci-dessous), je publie donc 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 )le test est requis à trois endroits: (a) après le sous-arbre de gauche, (b) après la racine et (c) après le sous-arbre de droite. Ceci permet de garantir que le kème élément est détecté pour tous les emplacements , c'est-à-dire quel que soit le sous-arbre dans lequel 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 du kème plus petit jusqu'à la racine sont imprimés.

Pour un arbre de recherche non équilibré, il faut O (n) .

Pour un arbre de recherche équilibré , il prend O (k + log n) dans le pire des cas mais juste O (k) au sens Amorti .

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

En général, il existe des solutions (non basées sur l'arbre).

Cordialement.

Cela fonctionne bien: status: est le tableau qui contient si l'élément est trouvé. k: est le kième élément à trouver. count: garde la trace du nombre de nœuds traversés pendant la traversée de l'arborescence.

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 je pensais que certaines personnes pourraient trouver intéressante:

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

appeler comme:

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

Et bien voici mes 2 centimes ...

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 j'ai pensé et ça marche. Il fonctionnera 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 simplement utiliser la traversée dans l'ordre et pousser l'élément visité sur une pile. pop k nombre de fois, pour obtenir la réponse.

on peut aussi s'arrêter après k éléments

Solution pour un cas BST complet: -

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 de données arborescente rouge-noire augmentée qui prend en charge les opérations basées sur les rangs dans O (log n) dans linux / lib / rbtree.c.

Un port Java très grossier peut également être trouvé à 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 nième élément peut être obtenu en appelant RbNode.nth (nœud RbNode, int n), en passant à la racine de l'arbre.

Voici une version concise en C # qui renvoie le k-ième élément le plus petit, mais nécessite de 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 nœud, puis O (k) pour traverser jusqu'au k-ème nœud, donc c'est O (k + log n).

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

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

1. utilisation de la traversée en ordre sur le temps O (n) 2. utilisation de l'arbre augmenté en temps k + log n

Je n'ai pas pu trouver un meilleur algorithme ... j'ai donc 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 (Node root, int k) - pour trouver kth plus grand

min (Node root, int k) - pour trouver le kth le 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);
}

cela fonctionnerait aussi. appelez simplement la fonction avec maxNode dans l'arborescence

def k_largest (self, node, k): if k <0: return None
if k == 0: return node else: k - = 1 return self.k_largest (self.predecessor (node), k)

Je pense que c'est mieux que la réponse acceptée car il n'est pas nécessaire de modifier le nœud d'arbre d'origine pour stocker le nombre de ses nœuds enfants.

Nous avons juste besoin d'utiliser le parcours dans l'ordre pour compter le plus petit nœud de gauche à droite, arrêtez la recherche une fois que le nombre est égal à 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);
}

La meilleure approche existe déjà, mais j'aimerais ajouter un code simple pour cela

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

Utilisation de la classe Result auxiliaire pour suivre si le nœud est trouvé et le k courant.

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

Complexité temporelle de la solution Python: O (n) Complexité spatiale: O (1)

L'idée est d'utiliser Morris Inorder Traversal

class Solution(object):
def inorderTraversal(self, current , k ):
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                k -= 1
                if(k == 0):
                    return current.val
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R 
            k -= 1
            if(k == 0):
                return current.val
            current = current.right

    return 0

def kthSmallest(self, root, k):
    return self.inorderTraversal( root , k  )

J'ai écrit une fonction soignée pour calculer le kième élément le plus petit. J'utilise la traversée dans l'ordre et m'arrête quand il 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;

      }
  }

}