[?] Arbb (arboles binarios de busqueda) C++...???

[Liraa]

Hola.! soy nueva en este foro, esta bien interesante, el motivo de este tema es q necesito realizar un ejercicio pero de verdad la mente ya no me da, las soluciones q penc sirven pero no son para nada eficientes.!

El problema es q necesito generar la cantidad de combinaciones que me generen un mismo arbol binario de busqueda..


Ejemplo:

3,4,3,5,4

Generan muchas combinaciones pero solo 3 generan el mismo arbol binario de busqueda:
3,4,3,5,4
3,4,5,4,3
3,4,5,3,4

de verdad agradeceria mucho q me pudieran ayudar.. yo ya tengo mi clase abb implementada en c++ pero no entiendo como atacar este problema...

habia pensado en hacer un algoritmo q me permute el numero y ir construyendo el arbol para cada uno y luego compararlo, pero resulta q para un caso muy grande tardaria toda la vida haciendolo :s

Gracias!

[ghastlyX]

Dada una secuencia de números, puedes construir el BST (Binary Search Tree) asociado. Entonces, fijado un nodo del árbol que no sea una hoja, si consideras los subárboles izquierdo y derecho, mientras mantengas el orden relativo con los nodos de su subárbol, cualquier orden mantendrá el mismo BST.

En el caso que has puesto, el único nodo que tiene un subárbol a cada lado es el 4. El subárbol izquierdo es un 3 y el derecho un 5 y a continuación un 4. Por lo tanto, el 3, 5, 4 de la entrada lo puedes ordenar como quieras siempre que el 5 vaya antes que el 4, por estar en el mismo subárbol, y así salen las tres posibles opciones (moviendo de sitio el 3).

El cálculo de fijado un nodo cuántas ordenaciones válidas hay lo puedes calcular fácilmente con programación dinámica y seguramente por combinatoria también salga. Lo único que tienes que tener cuidado de no repetir casos.

Lo he pensado rápido así que quizá me haya equivocado en algún punto, pero si es correcto el algoritmo resultante tiene complejidad polinómica y por lo tanto es mucho más eficiente que lo que comentabas.

[Liraa]

Ah ok amigo muchas gracias, pero hay algo q no entendi.. cuando hay varios nodos q tienen subarbol a cada lado,  tambien tengo q guardar el recorrido por niveles de todos esos subarboles??

Gracias.

[ghastlyX]

No tienes que guardar el recorrido, te da igual si sólo quieres saber cuántas ordenaciones hay (no cuáles son), simplemente deberías saber cuántos nodos tiene el subárbol, que lo puedes precalcular linealmente para todos los nodos haciendo un único recorrido inicial del árbol.