tree - grado - arboles binarios de busqueda en c
Con ''N'' no de nodos, ¿cuántos árboles de búsqueda binarios y binarios diferentes son posibles? (9)
Para árboles binarios: no es necesario considerar los valores de nodo de árbol, solo estoy interesado en diferentes topologías de árbol con nodos ''N''.
Para el árbol de búsqueda binaria: tenemos que considerar los valores de nodo de árbol.
Número total de árboles binarios son =
Al sumar i, se obtiene el número total de árboles de búsqueda binarios con n nodos.
El caso base es t (0) = 1 yt (1) = 1, es decir, hay una BST vacía y hay una BST con un nodo.
Por lo tanto, en general puede calcular el número total de árboles de búsqueda binarios utilizando la fórmula anterior. Me hicieron una pregunta en una entrevista de Google relacionada con esta fórmula. La pregunta fue cuántos números totales de árboles de búsqueda binaria son posibles con 6 vértices. Entonces Answer es t (6) = 132
Creo que te di una idea ...
árbol binario :
No es necesario considerar los valores, tenemos que mirar la estructura.
Dado por (2 potencia n) - n
Ejemplo: para tres nodos es (2 potencia 3) -3 = 8-3 = 5 estructuras diferentes
árbol binario de búsqueda:
Necesitamos considerar incluso los valores del nodo. Lo llamamos como número catalán
Dado por 2n C n / n + 1
Diferentes árboles binarios con n nodos:
(1/(n+1))*(2nCn)
donde C = combinación, por ejemplo.
n=6,
possible binary trees=(1/7)*(12C6)=132
Eric Lippert recientemente tuvo una serie muy profunda de publicaciones en el blog sobre esto: " Every Binary Tree There Is " y " Every Tree There Is " (y algo más después de eso).
En respuesta a su pregunta específica, él dice:
El número de árboles binarios con n nodos está dado por los números catalanes , que tienen muchas propiedades interesantes. ¡El enésimo número catalán está determinado por la fórmula (2n)! / (n + 1)! n !, que crece exponencialmente.
La cantidad de árboles binarios se puede calcular usando el número catalán .
El número de árboles de búsqueda binarios se puede ver como una solución recursiva. es decir, Número de árboles de búsqueda binarios = (Número de subárboles de búsqueda binarios izquierdos ) * (Número de subárboles de búsqueda binarios correctos ) * (Formas de elegir la raíz)
En una BST, solo importa el orden relativo entre los elementos. Entonces, sin ninguna pérdida de generalidad, podemos suponer que los distintos elementos en el árbol son 1, 2, 3, 4, ...., n . Además, permita que el número de BST esté representado por f (n) para n elementos .
Ahora tenemos los casos múltiples para elegir la raíz.
- elija 1 como raíz, no se puede insertar ningún elemento en el subárbol izquierdo. n-1 elementos se insertarán en el subárbol derecho.
- Elija 2 como raíz, se puede insertar 1 elemento en el subárbol izquierdo. Se pueden insertar n-2 elementos en el subárbol correcto.
- Elija 3 como raíz, se pueden insertar 2 elementos en el subárbol izquierdo. Los elementos n-3 se pueden insertar en el subárbol correcto.
...... De manera similar, para el elemento i-ésimo como raíz, los elementos i-1 pueden estar a la izquierda y ni a la derecha.
Estos subárboles son en sí mismos BST, por lo tanto, podemos resumir la fórmula como:
f (n) = f (0) f (n-1) + f (1) f (n-2) + .......... + f (n-1) f (0)
Casos base, f (0) = 1, ya que hay exactamente 1 forma de hacer una BST con 0 nodos. f (1) = 1, ya que hay exactamente 1 forma de hacer una BST con 1 nodo.
Recomiendo este artículo a mi colega Nick Parlante (de cuando todavía estaba en Stanford). El recuento de árboles binarios estructuralmente diferentes (problema 12) tiene una solución recursiva simple (que en forma cerrada termina siendo la fórmula catalana que ya se mencionó en la respuesta de @codeka).
No estoy seguro de cómo el número de árboles de búsqueda binaria estructuralmente diferentes (BST para abreviar) sería diferente del de los árboles binarios "simples", excepto que, si por "considerar valores de nodo de árbol" quiere decir que cada nodo puede ser, por ejemplo cualquier número compatible con la condición BST, entonces el número de BST diferentes (¡pero no todas estructuralmente diferentes! -) es infinito. Dudo que lo diga, así que aclare lo que quiere decir con un ejemplo.
Si se le da no. de Nodos son N Entonces.
Diferente número de BST = catalán (N)
Diferente número de árboles binarios estructuralmente diferentes son = catalán (N)
Diferente número de árboles binarios son = N! * Catalán (N)
(2n)!/n!*(n+1)!
The number of possible binary search tree with n nodes (elements,items) is
=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 )
where ''n'' is number of nodes (elements,items )
Example :
for
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc