Meilleure façon de sélectionner le plus petit nombre d'une séquence de nombres délimitée

Question

Si on me donne un certain nombre de nombres (que je stocke dans un arbre de recherche binaire équilibré pour la facilité), alors je veux répondre à une requête qui me demande Pour savoir quel est le plus petit nombre entre [A, B], quel serait un algorithme rapide pour effectuer cette tâche? Techniquement, je pourrais traverser l'arbre de la racine en cherchant A (ou un nombre immédiatement supérieur à celui si A n'est pas présent), que revenir en arrière en cherchant B (ou un nombre plus petit que B), et en faisant cela je pourrais garde un compteur pour moi, pour déterminer quand je serais au numéro it. Mais cela ne me semble pas optimal. Puis-je effectuer cette opération sur O (log n), hauteur de l'arbre que j'utilise pour stocker l'ensemble de nombres universel?

Merci

Answer 1

Vous ne pouvez certainement le faire, si vous pouvez conserver certaines informations dans les noeuds. Pour faire la traversée O(logn), nous avons besoin que chaque nœud sache combien de nœuds son sous-arbre a. (Vous pouvez conserver ces informations et que vous avez encore ajouter à/enlever de l'arbre en O (log (n)))

def search(currentNode, k) 
    if k == 0 then 
     return currentNode 
    else if currentNode.rightBranchSize >= k then 
     // we remove 1 from k because currentNode isn't considered anymore 
     return search(currentNode.right, k - 1) 
    else 
     // we decrease k because currentNode and its whole right subtree aren't considered anymore 
     return search(currentNode.parent, k - currentNode.rightBranchSize - 1) 
    end 
end 

Le code devrait être assez explicite.
Nous commençons par currentNode étant le premier noeud avec le numéro >= A et recherchons l'élément k (th est 0).

1. Comme schnaader dans son commentaire, il serait plus facile de l'arbre traverse si k est petit.
2. La plupart des librairies étendues (comme STL) ne vous permettent pas de traverser l'arborescence de cette façon (elles ne fournissent aucun type de struct Node avec des pointeurs vers les sous-arborescences gauche et droite). Donc, bien que l'algorithme soit simple, sa mise en œuvre pourrait être difficile.
3. Il suffit de peu de modifications pour considérer B de votre question.