• Lunes 29 de Abril de 2024, 03:17

Autor Tema:  una consulta.. sobre un algoritmo  (Leído 1791 veces)

manudferreiro

  • Nuevo Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
una consulta.. sobre un algoritmo
« en: Miércoles 2 de Julio de 2008, 09:28 »
0
Bueno gente, aprovecho para hacerles esta consulta.. me dieron como trabajo que haga esta actividad..
/*Implementar una busqueda binaria sobre una lista ordenada.
Dada una lista ordenada de numeros enteros como entrada,
debera poder hacer una busqueda binaria sobre los datos de la misma.
Debera utilizar un arbol binario para poder realizar la busqueda*/
primero que nada no estoy pidiendo que me lo hagan ni mucho menos, lo que sucede es que tengo una duda con la consigna..
lo que tendria que hacer seria (ustedes diganme si estoy en lo cierto) tomo como datos una lista ordenada, estos datos lso paso a un arbol binario de busqueda,aqui me enfrento al primer problema si paso los datos ordenados tengo nuevamente una lista,  lo que no entiendo o no se es cual seria el algoritmo para hacer una busqueda binaria en un arbol. no seria por naturaleza cualquier busqueda en un arbol binaria??
en definitiva no entiendo bien que es lo que me pide la consigna..
espero que me den una mano...

Iganguli

  • Miembro activo
  • **
  • Mensajes: 51
  • Nacionalidad: mx
    • Ver Perfil
Re: una consulta.. sobre un algoritmo
« Respuesta #1 en: Miércoles 2 de Julio de 2008, 21:56 »
0
Pues la busqueda binaria se usa sobre vectores ordenados y generalmente se toma como pivote el elemento de enmedio y si es mayor el elemento que busco desecho la otra mitad  y asi no es necesario pasarlo a un arbol binario

manudferreiro

  • Nuevo Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
Re: una consulta.. sobre un algoritmo
« Respuesta #2 en: Jueves 3 de Julio de 2008, 01:30 »
0
hola gracias por responder... pero justamente ese es el problema que tengo es una tarea que me encargaron para la facultad y me pide explicitamente esto
"/*Implementar una busqueda binaria sobre una lista ordenada.
Dada una lista ordenada de numeros enteros como entrada,
debera poder hacer una busqueda binaria sobre los datos de la misma.
Debera utilizar un arbol binario para poder realizar la busqueda*/"
mi problema es que no se como mier.. hacer o que es lo que tengo que hacer.. cuando habla de lista se refiere a lista enlazada (no array)..
gracias y gracias por responder

gonza_fs

  • Nuevo Miembro
  • *
  • Mensajes: 24
    • Ver Perfil
Re: una consulta.. sobre un algoritmo
« Respuesta #3 en: Miércoles 9 de Julio de 2008, 22:13 »
0
Hola, que tal. Supongo que la respuesta es en base a lo que dijo Iganguli. En parte tiene razon. Ahora como debes usar un arbol, la gracia esta en buscar a la derecha o la izquierda de la raiz, segun si el elemento que buscas es mayor o menor al elemento pivote o del medio. Ese elemento pivote de la lista, es tu raiz. A partir de ahi el algoritmo mas facil para continuar armando el arbol, es la recursion. Pensa que el elemento del medio de la lista es la raiz, la sublista izquierda resultante, es tu subarbol izquierdo, y lo mismo con la sublista derecha, y asi sucesivamente.

Elforious

  • Miembro activo
  • **
  • Mensajes: 44
    • Ver Perfil
Re: una consulta.. sobre un algoritmo
« Respuesta #4 en: Jueves 10 de Julio de 2008, 17:04 »
0
Recuerdo haber hecho ese algoritmo recursivo, pero en un vector, me inspiré en el QuickSort jeje.

Con respecto a la lista enlazada, creo que se refiere al código compuesto, y que tienes que realizar la búsqueda en varias listas según lo que vas encontrando en la anterior.

Espero haber ayudado.

manudferreiro

  • Nuevo Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
Re: una consulta.. sobre un algoritmo
« Respuesta #5 en: Lunes 14 de Julio de 2008, 16:18 »
0
hola, como andan?? primero que nada gracias por responder... les cuento que ya solucione el problema.. es de la siguiente manera:
como en las listas se tiene UNICAMENTE acceso secuencial seria imposible realizar una busqueda binaria ya que para esta se necesitan tener "acceso directo" a los datos, por consiguiente la utilidad del arbol en este  caso era la de realizar un arbol de posiciones para tener acceso "casi directo" a los datos y a partir de ahi poder realizar una busqueda binaria..
Manu
p.d cualquier cosa si quieren el algorimto se los paso.