8
Comment procéder pour choisir un élément aléatoire dans un arbre? Est-il nécessaire de connaître au préalable la profondeur/taille de l'arbre?Comment choisir un nœud aléatoire à partir d'un arbre
A
Répondre
0
Il suffit de faire pour chaque nœud un appel aléatoire dans l'intervalle 0 jusqu'à (nombre d'enfants) -1 et sélectionner l'enfant suivant après ce nombre. Répétez ceci jusqu'à ce que vous soyez dans une feuille.
12
Ce n'est pas le cas. Pour choisir un nœud uniformément au hasard, il suffit de parcourir l'arbre dans l'ordre que vous voulez. Soit le nième nœud examiné avec la probabilité 1/n. C'est-à-dire, conservez un enregistrement du nœud que vous retourneriez dans une variable, et lorsque vous regardez le nième nœud, remplacez le nœud actuel par le nième avec la probabilité 1/n. Vous pouvez montrer par induction que cela retourne un nœud uniformément au hasard sans avoir besoin de savoir combien il y a d'avance.
2
Si vous avez structuré vos feuilles à se stockés dans un type de données en mesure index, comme un tableau, vous pouvez facilement (pseudo-code):
random_leaf = leaf_pile[ random(size of leaf pile) ]
C'est une belle O rafraîchissante (1) :-)
Bien sûr, il peut y avoir des trous, donc vous devrez peut-être recommencer à partir de là. Si elle est stockée en tant que liste liée, vous pouvez itérer cependant.
Juste fournir une alternative à l'évidence. Cela dépend vraiment de votre structure de données et de votre cas d'utilisation le plus courant.
Questions connexes
- 1. Comment obtenir un noeud aléatoire d'un arbre?
- 2. Choisir un nœud xml aléatoire à partir de xmllist selon une condition
- 3. choisir la valeur aléatoire
- 4. Choisir un mot aléatoire en Python?
- 5. Traversée d'un arbre pour trouver un nœud
- 6. sélectionnez un nœud p aléatoire via jQuery
- 7. Ajout d'un nœud à un arbre dans SML
- 8. Comment construire efficacement un arbre à partir d'une structure plane?
- 9. Je dois choisir un point xy aléatoire à partir d'une liste de points xy
- 10. Suppression d'un objet à partir d'un arbre
- 11. Choisir un seul nœud avec un nom d'attribut dans vbscript
- 12. Choisir une action aléatoire, Flash AS3
- 13. Comment implémenter un arbre d'espaces d'états?
- 14. Comment obtenir un résultat aléatoire à partir d'un preg_match_all?
- 15. comment générer un nombre aléatoire à partir d'un tableau
- 16. Arbre d'adjacence à partir d'une table unique
- 17. Comment obtenir un nœud XML à partir de XDocument
- 18. Comment intercepter le dernier nœud ouvert/développé d'un arbre Flex
- 19. Comment récupérer le chemin d'un nœud dans un arbre - efficace (lié au poste 'analyser une table plate dans un arbre?)
- 20. SimpleXML: ajouter un arbre à un autre
- 21. Comment manipuler un arbre d'objets immuables?
- 22. Création d'un nœud enfant à partir d'un nœud parent
- 23. Obtenir un message aléatoire à partir du flux rss
- 24. Comment choisir un ORM
- 25. Matlab choisir la couleur aléatoire pour le traçage
- 26. Retour aléatoire d'éléments à partir d'une collection
- 27. Récupérer une entité aléatoire à partir du magasin de données
- 28. XML interrogeant un nœud particulier à partir de C#
- 29. Drupal obtient un champ CKK à partir d'un objet nœud
- 30. Créer un arbre à partir d'une liste de rectangles
Ceci sera biaisé vers les nœuds aux niveaux supérieurs de l'arbre. Par exemple, la probabilité de sélectionner le rootNode = 1/3 (en supposant un maximum de 2 enfants). La probabilité de sélectionner le nœud foliaire le plus à gauche = (1/3)^k, où k = profondeur du nœud foliaire. –
c'est vrai, cependant, dans certains cas, cela n'a pas d'importance mais merci de le signaler – Quonux