8
¿Cómo se puede elegir un elemento aleatorio de un árbol? ¿Es necesario conocer la profundidad/tamaño del árbol de antemano?Cómo elegir un nodo aleatorio de un árbol
A
Respuesta
0
Simplemente haga para cada nodo una llamada aleatoria en el rango 0 hasta (número de hijos) -1 y seleccione el siguiente hijo después de ese número.
Repita esto hasta que esté en una hoja.
12
No lo es. Para elegir un nodo uniformemente al azar, simplemente itere a través del árbol en el orden que desee. Deje que el n-ésimo nodo examinado sea el elegido con probabilidad 1/n. Es decir, mantenga un registro del nodo que devolvería en una variable, y cuando mire el enésimo nodo, reemplace el nodo actual por el enésimo con probabilidad 1/n. Puede mostrar por inducción que esto devuelve un nodo uniformemente al azar sin necesidad de saber cuántos hay de antemano.
2
Si ha estructurado sus hojas que se almacena a sí mismos dentro de un tipo de datos de índice de poder, como una matriz, entonces usted puede fácilmente (pseudocódigo):
random_leaf = leaf_pile[ random(size of leaf pile) ]
Eso es un bonito, O refrescante (1) :-)
Por supuesto, puede haber agujeros, por lo que puede tener que repetir desde allí. Si está almacenado como una lista enlazada, entonces puedes iterar sin embargo.
Simplemente proporcionando una alternativa a lo obvio. Realmente depende de su estructura de datos y su caso de uso más común.
Cuestiones relacionadas
- 1. Elegir al azar un nodo en XSLT
- 2. Boost árbol de propiedades: Eliminar un nodo
- 3. Creando un diagrama de nodo de árbol
- 4. ¿Cómo buscar un nodo en un árbol y devolverlo?
- 5. Cómo encontrar un nodo en un árbol con JavaScript
- 6. Agregar un nodo/propiedad a un árbol de expresiones
- 7. ¿Cómo se puede representar un nodo de árbol B?
- 8. Recorrido de un árbol para encontrar un nodo
- 9. altura de un árbol con sólo un nodo
- 10. Búsqueda recursiva de un nodo en un árbol no binario
- 11. Elegir un conjunto aleatorio que satisfaga cierta propiedad
- 12. XSLT dividió un árbol en un nodo descendente
- 13. Aplicar ordenamiento de nodo horizontal en un árbol .dot
- 14. Escogiendo un elemento aleatorio de un conjunto
- 15. Elegir un archivo aleatorio de un directorio (con una gran cantidad de archivos) en Python
- 16. La mejor manera de elegir un archivo aleatorio de un directorio
- 17. Elegir un analizador Haskell
- 18. ¿Cómo encontrar el primer ancestro común de un nodo en un árbol binario?
- 19. ¿Cómo elegir un elemento de lista aleatorio en una función pura?
- 20. Modelado de un nodo en un RangeTree
- 21. ¿Cómo manipulo un árbol de objetos inmutables?
- 22. Cómo agregar un elemento secundario a un nodo específico en el árbol n-array?
- 23. Cuál es la complejidad de tiempo de eliminar un nodo en un árbol binario
- 24. ¿Cómo elegir un enlace WCF?
- 25. ¿Cómo elegir un contenedor DI?
- 26. ¿Cómo construir un árbol y?
- 27. ¿Cómo crear un nodo duplicado desde un nodo en Neo4j?
- 28. Elegir el elemento aleatorio de una matriz Actionscript 3
- 29. ¿Se puede pasar de un símbolo semántico a un nodo de árbol de sintaxis usando Roslyn?
- 30. ¿Cómo se genera un número aleatorio en tiempo de ejecución?
Esto estará sesgado hacia los nodos en los niveles superiores del árbol. Por ejemplo, la probabilidad de seleccionar el rootNode = 1/3 (suponiendo un máximo de 2 hijos). La probabilidad de seleccionar el nodo de hoja más a la izquierda = (1/3)^k, donde k = profundidad del nodo de hoja. –
esto es cierto, sin embargo, en algunos casos no importa, pero thx para señalar esto – Quonux