algorithm - profundidad - número total de árbol ordenado con 3 nodos

profundidad de un arbol (2)

Consulte el siguiente enlace , es un documento muy bueno sobre el conteo de árboles ordenados.

Estoy recibiendo respuestas mixtas en internet

También vi una pregunta en SO, pero no me ayudó mucho

¿Cuál debería ser la respuesta?

También es esto un árbol?
a / b / c

Primero, sí, su ejemplo es un árbol bajo cualquier definición razonable, a menos que requiera que el árbol esté "lleno", lo cual no se menciona en ninguna parte. Sospecho, por lo tanto, que las respuestas en ambas páginas son (no sorprendentemente) incorrectas.

En segundo lugar, no me gusta la forma en que se formula la pregunta en el segundo enlace, ya que no deja en claro lo que se entiende por igualdad. ¿Solo buscamos árboles que sean topológicamente iguales (la misma estructura, es decir, la colocación de nodos) o buscamos la igualdad de árboles que contienen un conjunto de tres nodos específicos, como en el primer enlace. Por lo tanto, me atengo a la pregunta en el primer enlace.

Estoy usando la siguiente definición de árbol ordenado. Como no importa para esta pregunta, voy a ignorar el borde de un árbol vacío, aunque se podría escribir una definición para incluir el árbol vacío como candidato si así lo desea. Un árbol ordenado consiste en un nodo raíz junto con una lista posiblemente vacía (una secuencia ordenada) de elementos secundarios, cada uno de los cuales también es un árbol ordenado.

Esta definición incluye claramente tu ejemplo. La raíz es A, tiene un único hijo, B, que tiene un único hijo C, que no tiene hijos (una lista vacía de hijos).

Procedamos recursivamente en la cantidad de nodos N que estamos colocando en un árbol. Dejaremos que T (N) sea la cantidad de árboles ordenados distintos que se pueden construir a partir de un conjunto fijo de N (etiquetados) nodos.

Caso base: N = 1. Si tenemos exactamente un nodo, podemos construir solo un árbol donde ese nodo es la raíz. Entonces T (1) = 1.

Segundo caso: N = 2. Hay dos opciones para el nodo raíz. El nodo restante es necesariamente el primer y único hijo de la raíz. Entonces T (2) = 2.

Tercer caso: N = 3. Ahora hay tres opciones para el nodo raíz. Una vez que hemos seleccionado un nodo raíz, nuevamente tenemos dos casos:

Caso A: el nodo raíz tiene dos hijos, cada uno de los cuales es un árbol ordenado con dos elementos. Hay dos formas en que podemos ordenar los dos nodos restantes. Entonces, hay 3 * 2 = 6 árboles ordenados posibles con tres nodos dado que el nodo raíz tiene dos hijos.
Caso B: el nodo raíz tiene un elemento secundario, que es necesariamente un árbol ordenado con dos elementos. Hay T (2) = 2 formas diferentes en que podríamos construir un árbol ordenado a partir de los dos elementos restantes, por lo que hay un total de 3 * 2 = 6 árboles ordenados posibles con tres nodos dado que el nodo raíz tiene solo un elemento secundario.

Estas dos subcategorías cubren todas las posibilidades y no se superponen (dividen los posibles árboles ordenados con tres nodos), así que podemos agregarlos: T (3) = 6 + 6 = 12.

Si está interesado en la pregunta más general, es un poco más complicado y no sé la respuesta, ni sé si se conoce la respuesta. El enfoque que tomaría sería algo como esto:

Caso general: N. Hay una raíz. Los nodos N - 1 restantes deben estar en los subárboles de la raíz. De modo que miraría el número de partición de N - 1 (la cantidad de formas de dividir N - 1 en grupos). Entonces tendría que ver la cantidad de formas de elegir los artículos que entran en cada grupo. Y luego observaría la cantidad de árboles ordenados que podrían formarse a partir de la cantidad de nodos que hay en cada grupo.

De todos modos, hay otros enfoques. Pero eso quizás esté más allá del alcance de esta pregunta.

NOTA: Una pregunta que puede surgir es si olvidé contar algo así como

A A / / B and B / / C C

Pero como árboles ordenados, estos son iguales. Se han mostrado aquí como si fueran árboles binarios (donde cada nodo tiene dos hijos que pueden ser subárboles vacíos). Pero con árboles ordenados, nos importa que la raíz sea la misma y que los niños correspondientes sean iguales. Entonces en los dos casos anteriores, las raíces son ambas A. En ambos casos, la raíz tiene un único hijo B. Y en ambos casos, ese niño tiene un solo hijo C. Entonces los árboles son los mismos.