Dada una matriz de enteros ordenada, ¿cómo pueden formarse árboles de búsqueda binaria a partir de ella?

Question

Considere que tengo una matriz [3,18,15,25,26], ¿cuántos posibles árboles de búsqueda binarios se pueden formar a partir de ella?

Answer 1

Después de ver la pregunta vinculada por MicSim, todavía no estaba satisfecho con eso, así que comencé a buscarlo yo mismo. Esto es lo que se me ocurrió ...

Cada árbol se puede considerar como dos árboles con un nodo raíz principal. Si conoce por separado el número de combinaciones posibles de las ramas de dos niños, las combinaciones totales que tienen ese nodo raíz son el producto de las combinaciones secundarias.

Podemos comenzar a construir una solución de conteo más alto resolviendo primero las instancias de recuento más bajo.

Utilizaré C(n) para representar las combinaciones posibles totales de n nodos, el número catalán.

Esperamos que estos dos son obvias:

C(0) = 1 
C(1) = 1 

C (2) también es bastante obvio, pero se pueden construir, por lo que vamos a hacer eso. Hay dos formas de elegir el nodo raíz. Uno deja un recuento de niños (izquierda: derecha) de 1:0 y el otro 0:1. Entonces, la primera posibilidad es C(1)*C(0) = 1*1 = 1. Y el segundo es C(0)*C(1) = 1*1 = 1. Sumarlos nos da

Nada demasiado emocionante. Ahora hagamos 3 nodos. Hay 3 formas de elegir el nodo raíz y, por lo tanto, 3 agrupaciones secundarias. Sus posibles grupos son 2:0, 1:1 y 0:2.

Según nuestras definiciones previas, C(3) se puede escribir como C(2)*C(0) + C(1)*C(1) + C(0)*C(2) = 2*1 + 1*1 + 1*2 = 2+1+2 = 5.

C(3) = 5 

4 nodos tiene niño agrupaciones de 3:0, 2:1, 1:2 y 0:3. Por lo tanto, C(4) puede escribirse como C(3)*C(0) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3) = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14.

C(4) = 14 

Con suerte, dos cosas están comenzando a ser evidente. En primer lugar, esto comenzará a ser engorroso bastante pronto. Segundo, que lo que describí, de una manera bastante prolija, es la representación de la relación de recurrencia en la página wiki.

No sé si esto ayuda, pero me ayudó a realizar el ejercicio, así que pensé en compartirlo. No estaba tratando de recrear la relación de recurrencia cuando comencé, por lo que fue bueno que mis resultados coincidieran con uno de los métodos existentes.

Answer 2

El n ° catalan number da la cantidad posible de árboles de búsqueda binaria que pueden crearse con N teclas.

Véase también esta pregunta: The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?

Answer 3

cualquiera de los nodos de la matriz puede ser la raíz de un BST, y para cada raíz, el número de distintos árboles de búsqueda es la combinación (producto) de la izquierda y el subarreglo correcto. Así,

BSTCount(0) = 1 
BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(n-i) 

se puede evaluar esta función durante los primeros n y luego buscar la secuencia en el On-Line Encyclopedia of Integer Sequences™ (OEIS) para encontrar una forma cerrada.