math - programar - arboles en python

La cantidad posible de árboles de búsqueda binaria que pueden crearse con N teclas viene dada por el N ° número catalán. ¿Por qué?

Question

Esto me ha estado molestando por un tiempo. Sé que con las teclas N para organizar en forma de árbol de búsqueda binaria, el número posible de árboles que se pueden crear corresponde al número N de la secuencia catalana .

He estado tratando de determinar por qué es esto; incapaz de encontrar algo que incluso pueda intentar explicarlo intuitivamente, recurro al conocimiento colectivo de SO. Encontré otras maneras de calcular el número de árboles posibles, pero parecían menos intuitivos y no se ofrecía ninguna explicación más allá de cómo usarla. Además, la página wiki (ese enlace de arriba) incluso muestra una imagen de las posibles formaciones en árbol con 3 claves, lo que me llevaría a pensar que hay una explicación agradable y ordenada para ser escuchada (que, huelga decirlo, no está incluida en el artículo). )

¡Gracias por adelantado!

Answer 1

Bueno, aquí está la solución recursiva para contar los árboles ...

int countTrees(int numkeys){

if(numkeys > 1){
    int i =1;
    int sum=0;

    for(i = 1; i <= numkeys; i++){

        int lcount = countTrees(i-1);
        int rcount = countTrees(numkeys-i);
        sum += lcount*rcount;
    }
    return(sum);
}else
    return(1);
}

Answer 2

Dado que hay cuatro pruebas en el artículo de wikipedia al que se hace referencia, parece que no está buscando una explicación matemática para la correspondencia entre los números catalanes y las permutaciones de un árbol binario.

Entonces, en cambio, aquí hay dos formas de intentar visualizar intuitivamente cómo la secuencia catalana (1, 2, 5, 14, 42, ...) surge en sistemas combinatorios.

Cortar polígonos en triángulos

Para un polígono del lado N , ¿de cuántas maneras puede dibujar cortes entre los vértices que cortan el polígono completamente en triángulos?

• Triángulo (N = 3): 1 (ya es un triángulo)
• Cuadrado (N = 4): 2 (puede cortar en diagonal)
• Pentágono (N = 5): 5 (dos líneas de corte que emanan de un vértice. Cinco vértices para elegir)
• Hexágono (N = 6): 14 (Trate de dibujarlo)
• ...y así.

Dibujando un camino a través de una cuadrícula sin cruzar la diagonal

En este caso, el número de rutas únicas es el número catalán.

Rejilla 2x2 => 2 caminos

  _|       |
_|       __|

Rejilla 3x3 => 5 caminos

    _|       |       _|         |         |
  _|      _ _|      |          _|         |
_|      _|       _ _|      _ _|      _ _ _|

Rejilla 4x4 => 14 caminos
Rejilla 5x5 => 42 caminos

y así.

Si tratas de dibujar los posibles árboles binarios para un N dado, verás que la forma en que el árbol se permuta es la misma.

Tu deseo de no aceptar ciegamente la correspondencia entre el árbol y la secuencia es admirable. Desafortunadamente, es difícil ir más lejos con esta discusión (y explicar por qué la fórmula catalana "pasa a ser" tal como es) sin invocar las matemáticas binomiales. La discusión en Wikipedia sobre los coeficientes binomiales es un buen punto de partida si quieres entender la combinatorics (que incluye el conteo de permutación ) en sí misma con más profundidad.

Answer 3

catalán http://www.nohre.se/publicImages/catalan.png

Cualquier árbol de búsqueda binaria se puede codificar visitando todos los nodos preordenados y codificando un 1 para cada padre y un 0 para cada hoja. Si el árbol tiene n padres, tendrá n + 1 hojas y, en consecuencia, el código binario tendrá n 1: s y (n + 1) 0: s. Además, y cualquier prefijo del código tendrá al menos tantos 1: s como 0: s. Por lo tanto, la cantidad de árboles posibles es igual a la cantidad de caminos debajo de la diagonal.