Con ‘N’ no de nodos, ¿cuántos árboles de búsqueda binarios y binarios diferentes son posibles?

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.

    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.

    1. Número total de árboles binarios son = enter image description! [enter image description here

    2. Al sumr i, se obtiene el número total de árboles de búsqueda binarios con n nodos. enter image description here

    El caso base es t (0) = 1 yt (1) = 1, es decir, hay una BST vacía y hay una BST con un nodo. enter image description here

    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 …

    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.

    1. 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.
    2. 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.
    3. 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.

    Fórmula final

    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)

    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.

    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 
     (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 

    á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

    La respuesta correcta debería ser 2nCn / (n + 1) para los nodos no etiquetados y si los nodos están etiquetados, entonces (2nCn) * n! / (N + 1) .