Trouver le plus petit élément kth dans une arborescence de recherche binaire de manière Optimum

Question

J’ai besoin de trouver à coup sûr le plus petit élément de kth dans l’arborescence de recherche binaire à l’aide de n’importe quelle variable statique/globale. Comment faire pour y parvenir efficacement ? La solution que j’ai dans mon esprit fait l’opération en o (n), le pire des cas étant donné que j’ai l’intention de faire une traversée envue de l’intégralité de l’arborescence. Mais au plus profond, je pense que je n’utilise pas la propriété de CEST ici. Ma solution assumptive n’est correct ou y a-t-il un meilleur disponible ?

Answer 1

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

Laissez chaque nœud du BST ont un champ qui retourne le nombre d'éléments à sa gauche et à droite de la sous-arborescence. Laissez la gauche de la sous-arbre du nœud T contiennent que des éléments de plus petite que T et le droit de la sous-arborescence que des éléments de taille supérieure ou égale à T.

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

1. k == num_elements(à gauche sous-arbre de T), alors la réponse que nous recherchons est la valeur du nœud T
2. k > num_elements(à gauche sous-arbre de T) alors il est évident que nous ne pouvons ignorer le sous-arbre gauche, car ces éléments seront également plus petit que l' kème plus petite. Ainsi, nous réduisons le problème de trouver l' k - num_elements(left subtree of T) plus petit élément du sous-arbre droit.
3. k < num_elements(à gauche sous-arbre de T), alors l' kème plus petite est quelque part dans le sous-arbre gauche, nous avons donc de réduire le problème de trouver l' kème plus petit élément dans le sous-arbre gauche.

C'est - O(log N) en moyenne (en supposant que l'équilibre de l'arbre).

Answer 2

Solution plus simple serait de faire afinde traversal et garder une trace de l’élément actuellement à imprimer (sans l’imprimer). Lorsque nous arriverons k, l’élément d’impression et ignorer le reste du parcours d’une arborescence.

Answer 3

<pre><code></code><p>Il s’agit de mon implémentation en c# basé sur l’algorithme ci-dessus juste pensé que je signalerais ce que les gens puissent comprendre mieux il fonctionne pour moi</p><p>Merci IVlad</p></pre>

Answer 4

Ajouter une version de java sans récursivité

Answer 5

Vous pouvez utiliser afinde itératif traversal : http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal avec un simple recherchez kth élément après poping, un nœud de la pile.