elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Tutorial básico de Quickjs


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [?] Arbb (arboles binarios de busqueda) C++...???
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [?] Arbb (arboles binarios de busqueda) C++...???  (Leído 3,661 veces)
Liraa

Desconectado Desconectado

Mensajes: 2


Ver Perfil
[?] Arbb (arboles binarios de busqueda) C++...???
« en: 24 Julio 2010, 23:57 pm »

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!



« Última modificación: 24 Julio 2010, 23:59 pm por Liraa » En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: [?] Arbb (arboles binarios de busqueda) C++...???
« Respuesta #1 en: 25 Julio 2010, 01:00 am »

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.


En línea

Liraa

Desconectado Desconectado

Mensajes: 2


Ver Perfil
Re: [?] Arbb (arboles binarios de busqueda) C++...???
« Respuesta #2 en: 27 Julio 2010, 21:54 pm »

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.
« Última modificación: 27 Julio 2010, 21:56 pm por Liraa » En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: [?] Arbb (arboles binarios de busqueda) C++...???
« Respuesta #3 en: 27 Julio 2010, 22:59 pm »

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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
ayuda en arboles binarios
Programación C/C++
josue_tux 1 2,797 Último mensaje 25 Junio 2011, 14:10 pm
por satu
ayuda urgente en arboles binarios
Programación C/C++
josue_tux 1 3,888 Último mensaje 10 Julio 2011, 16:04 pm
por Triper0
[C] Funciones para arboles binarios
Programación C/C++
gasparenaide 0 1,972 Último mensaje 19 Marzo 2013, 01:47 am
por gasparenaide
Busqueda por posicion en arboles binarios c++
Programación C/C++
Abril7 1 1,527 Último mensaje 12 Mayo 2017, 15:46 pm
por CalgaryCorpus
Problema en arboles binarios de busqueda
Programación C/C++
Josh13 1 1,570 Último mensaje 21 Mayo 2018, 15:19 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines