Número de posibles rutas de búsqueda al buscar en BST

Tengo la siguiente pregunta, pero no tengo respuesta para esto. Agradecería si mi método es correcto:

P. Cuando se busca el valor clave 60 en un árbol de búsqueda binario, los nodos que contienen los valores clave 10, 20, 40, 50, 70, 80, 90 se atraviesan, no necesariamente en el orden dado. ¿Cuántas órdenes diferentes son posibles en las que estos valores clave pueden aparecer en la ruta de búsqueda desde el nodo raíz que contiene el valor 60?

(A) 35 (B) 64 (C) 128 (D) 5040

A partir de la pregunta, entiendo que todos los nodos dados deben incluirse en el recorrido y, en última instancia, debemos alcanzar la clave, 60. Por ejemplo, una de esas combinaciones sería:

10, 20, 40, 50, 90, 80, 70, 60.

Como tenemos que atravesar todos los nodos dados anteriormente, tenemos que comenzar con 10 o 90. Si comenzamos con 20, no alcanzaremos 10 (ya que 60> 20 y atravesaremos el subárbol derecho de 20)

De manera similar, no podemos comenzar con 80, porque no podremos alcanzar 90, ya que 80> 60, atravesaremos el subárbol izquierdo de 80 y, por lo tanto, no llegaremos a 90.

Tomemos 10. Los nodos restantes son 20, 40, 50, 70, 80, 90. El siguiente nodo podría ser 20 o 90. No podemos tomar otros nodos por la misma razón mencionada anteriormente.

Si consideramos lo mismo, en cada nivel tenemos dos opciones. Como hay 7 nodos, dos opciones para los primeros 6 y ninguna opción para el último. Entonces hay totalmente

$2*2*2*2*2*2*1$ permutaciones = = $2^6$ $64$

¿Es esta una respuesta correcta?
Si no, ¿cuál es el mejor enfoque?
Me gustaría generalizar. Si se dan nodos, el total de rutas de búsqueda posibles sería $n$ $2^{n-1}$

data-structures combinatorics binary-trees search-trees graph-traversal avi
fuente

Respuestas:

Si en busca de la llave 60 se llega a un número de menos de 60, nos vamos a la derecha (donde los números son más grandes) y nunca encontramos con números menores de . Ese argumento puede repetirse, por lo que los números 10, 20, 40, 50 deben aparecer a lo largo de la búsqueda en ese orden. $K$ $K$

Del mismo modo, si en busca de la llave 60 se llega a un número mayor que 60, vamos leftt (donde los números son más pequeños) y nunca números se encuentran más grande que . Por lo tanto, los números 90, 80, 70 deben aparecer a lo largo de la búsqueda en ese orden. $K$ $K$

Las secuencias 10, 20, ~~30,~~ 40, 50 y 90, 80, 70 se pueden mezclar juntas, siempre que sus subsecuencias se mantengan intactas. Por lo tanto, podemos tener 10, 20, 40, 50, 90, 80, 70, pero también 10, 20, 90, 30, 40, 80, 70, 50.

Ahora podemos calcular el número, eligiendo la posición de los números grandes y pequeños. Ver el comentario de Aryabhata. Tenemos dos secuencias de 4 y 3 números. ¿De cuántas maneras puedo barajarlos? En las 7 posiciones finales, tengo que elegir 3 posiciones para los números más grandes (y las 4 restantes para los números más pequeños). Puedo elegir estos en formas. Después de arreglar estas posiciones, conocemos la secuencia completa. Por ejemplo, mi primer ejemplo tiene posiciones SSSSLLL, el segundo tiene SSLSLL S. $7 \choose 3$

Pides una generalización. Siempre los números son menores que el número encontrado, y los números mayores son fijos en su orden relativo. Los números más pequeños deben subir, los números arger deben bajar. El número es entonces . $x$ $y$ $x+y \choose y$

PS (editado). Gracias a Gilles, quien señaló que 30 no está en la pregunta.

Hendrik Jan
fuente

Seguramente me gustaría intentarlo. Dado que los números 90,80,70 tienen que estar juntos, consideremos que son un solo no. y se puede colocar entre 6 lugares: _ 10 _ 20 _ 30 _ 40 _ 50 _ Entonces eso es Si por la misma analogía, los números [10,20,30,40,50] se pueden colocar en 4 lugares, eso es Pero tiene que dividirse por combinaciones comunes que están ocurriendo (que no puedo entender)

2^{6}

$2^6$

2^{4}

$2^4$

avi

@avi No, no tienen que estar juntos, solo en ese orden: 10, 20, 90, 30, 40, 80, 70, 50 está bien.

Hendrik ene

@avi: Intenta pensar de esta manera: grande y pequeño. Ahora tiene 8 puntos, con 5 pequeños y 3 grandes. ¿Cómo los llenas? 8 elige 3. Lo que viene a 56, y supongo que es lo que también obtuvo Hendrik.

Aryabhata

@HendrikJan No había 30 en la pregunta original, solo había 7 valores. Y 7 elegir 3 es (A).

Gilles 'SO- deja de ser malvado'

@HendrikJan: ¿puede explicarme esto ?: Siempre los números son menores que el número encontrado, y los números más grandes se fijan en su orden relativo

x

$x$

y

$y$

avi

Convertiremos movimientos a texto. Se da que durante la búsqueda hemos atravesado estos nodos

como se puede ver que los rojos son más grandes que 60 y los azules son más pequeños que 60.

La ruta al nodo 60 ha involucrado esos nodos. Entonces, una de las posibles soluciones al problema es cualquier otra solución contendrá estos movimientos solamente. porque a la vez en un nodo podemos obtener direcciones como S o L en comparación y dado que se encontraron esos nodos, significa que las direcciones se seleccionaron de ese conjunto.

{S, S, S, S, L, L, L}

$\{S,S,S,S,L,L,L\}$

Por lo tanto, el número total de posibles soluciones = todas las Permutaciones de ese conjunto, que viene dado por respuesta = opción A

\frac{7!}{4! \times 3!} = 35

$\frac{7!}{4! \times 3!} = 35$

amarVashishth
fuente