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

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Estructuras en arbol
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Estructuras en arbol  (Leído 4,126 veces)
Leber


Desconectado Desconectado

Mensajes: 338


"Fracta, non verba"


Ver Perfil WWW
Estructuras en arbol
« en: 9 Abril 2011, 13:31 pm »

Hola, que tal.

Estaba buscando información sobre las EDD en arbol, pero no arboles binarios, si no arboles que puedan tener mas de 2 hijos. Buscando he encontrado algunos enlaces pero casi todos se referían a arboles binarios, o bien profundizaban demasiado poco en los arboles de no binario.

Me preguntaba si tendríais algún enlace donde explicaran minimamente bien esa parte, y mostraran como implementarlo.

Los enlaces que he mirado yo son:

http://c.conclase.net/edd/?cap=006#inicio
http://computacion.cs.cinvestav.mx/~aca ... ode57.html

Gracias de antemano


En línea

"Solo los tontos carecen de preucupaciones." Johann Wolfgang Goethe
Akai


Desconectado Desconectado

Mensajes: 823



Ver Perfil
Re: Estructuras en arbol
« Respuesta #1 en: 9 Abril 2011, 14:17 pm »

Sobre lo que comentas, digamos que si no hay mucha información al respecto es porque son "tweaks" menores. Es decir, cambios mínimos.

Una vez entiendes la estructura y funcionamiento del árbol binario, extender su funcionamiento a cualquier otro número de hijos es tarea fácil

Imaginemos que tenemos un árbol binario de búsqueda donde almacenamos enteros.

Si un elemento es menor que el entero contenido en dicho nodo, nos vamos por la izquierda, en cualquier otro caso, por la derecha.

Como lo ampliamos a 3 nodos?

Tienes infinidad de posibilidades, pero una por ejemplo, puede ser:

Si el elemento es menor que 1/3 del valor almacenado en el nodo, por la izquierda. Si está entre 1/3 y el valor del nodo, por el centro, y para cualquier otro caso, por
la derecha.

Esa hubiese sido una forma de ajustarlo, por ejemplo. Otra:



menor que 1/3 del valor del nodo --> izquierda
(mayor que 1/3 y menor que 2/3) del valor del nodo--> centro
mayor que 2/3 del valor del nodo --> derecha

De esta forma, tienes dos ejemplos sencillos de un árbol ternario de búsqueda.

Como creo que se puede observar, la expansión a n nodos una vez entendido el funcionamiento es trivial cuando se entiende qué se quiere hacer (poniéndote un problema en concreto y a partir de ahí viendo el desarrollo).


En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Estructuras en arbol
« Respuesta #2 en: 9 Abril 2011, 16:59 pm »

Como ya te han dicho, los árboles se suelen hacer de un determinado tipo según el problema que quieras resolver. Por ponerte un ejemplo de cómo sería un árbol de 3 hijos por nodo, te he picado un código para una posible implementación de un TST (Ternary Search Tree).
Código
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct Nodo {
  5.    char c;
  6.    Nodo *lo, *eq, *hi;
  7. };
  8.  
  9. void add(Nodo *&nodo, string& s, int p) {
  10.    if (p == s.size()) return;
  11.    if (nodo == NULL) {
  12.        nodo = new Nodo;
  13.        nodo->c = s[p];
  14.        nodo->lo = nodo->hi = nodo->eq = NULL;
  15.        add(nodo->eq, s, p + 1);
  16.    }
  17.    else {
  18.        if (s[p] < nodo->c) add(nodo->lo, s, p);
  19.        else if (s[p] > nodo->c) add(nodo->hi, s, p);
  20.        else add(nodo->eq, s, p + 1);
  21.    }
  22. }
  23.  
  24. bool search(Nodo *nodo, string& s, int p) {
  25.    if (p == s.size()) return true;
  26.    if (nodo == NULL) return false;
  27.    if (s[p] < nodo->c) return search(nodo->lo, s, p);
  28.    else if (s[p] > nodo->c) return search(nodo->hi, s, p);
  29.    else return search(nodo->eq, s, p + 1);
  30. }
  31.  
  32. int main() {
  33.    Nodo *raiz = NULL;
  34.    char c;
  35.    while (cin >> c) {
  36.        if (c == 'A') {
  37.            string s;
  38.            cin >> s;
  39.            add(raiz, s, 0);
  40.        }
  41.        else if (c == 'S') {
  42.            string s;
  43.            cin >> s;
  44.            if (search(raiz, s, 0)) cout << "String encontrada" << endl;
  45.            else cout << "String NO encontrada" << endl;
  46.        }
  47.    }
  48. }

No es difícil poner n hijos a un árbol, pero hay que tener en cuenta si sirve para algo hacerlo. Hay estructuras de tipo árbol más díficiles de implementar que otras, pero la dificultad no suele estar en el número de hijos, sino en la morfología del árbol. Por poner un par de ejemplos de algunos árboles más díficiles de picar, tienes por ejemplo los Suffix Trees o los TST con funciones de fallo para hacer un Aho-Corasick.
En línea

Leber


Desconectado Desconectado

Mensajes: 338


"Fracta, non verba"


Ver Perfil WWW
Re: Estructuras en arbol
« Respuesta #3 en: 10 Abril 2011, 02:09 am »

Gracias Akai y ghastlyX.

Para lo que lo queria era para cargar en memoria todo un grupo de artistas con sus respectivos discos y canciones.

Quedaría más o menos así:

[root]
|
|
|
[A] (Artistas que empiezan con la letra A)    (Artistas que empiezan con la letra B)
|                                                           |
|                                                           |
|                                                           |
[Agalloch] - [Ape] -[Aninimous]                  [Burzum] - [Basotti]

Y asi para todo.

Tendria 29 ramas principales, (cada una con la letra del abecedario), y a partir de ahi tantas subramas por cada rama por artista que empezará por esa letra. No se si se entiende.

Igualmente con la información que me habéis dado creo que ya puedo empezar a hacer cosas, así que investigaré un poco.

Gracias =)
En línea

"Solo los tontos carecen de preucupaciones." Johann Wolfgang Goethe
Firos
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.410


Enseña lo que sepas... y oculta lo peor...


Ver Perfil
Re: Estructuras en arbol
« Respuesta #4 en: 10 Abril 2011, 03:02 am »

Se me ocurre otra manera de hacerlo.

Podrias hacer un array bidimensional.

El array[0][X] que sea el equivalente a la letra A y X que sea el numero de artistas que tengas y en cada uno de ellos la estructura con lo que tenga cada artista.

 - Nombre.
 - Años.
 - Var3.
 - Var4.
Código
  1. typedef struct{
  2. char nombre[20];
  3. int año;
  4. int var3;
  5. int var4;
  6. } Sdatos;
  7.  
  8. // En el main declaras el array
  9.  
  10. Sdatos array[29][500];
  11.  

Tendrías que asociar las letras a, b, c, d, ... a un número, a lo mejor puedes hacerlo con enumeraciones para hacerlo fácil con el array:
Código
  1. enum {a=0, b=1; x=n }

No lo he probado y tampoco soy avanzado en C pero en teoría debería funcionar.

Podrías también incorporar algún algoritmo de ordenación que te los ordenase de forma automática por si vas añadiendo más con el tiempo.


Espero que te sirva.

Un saludo.
En línea

El final del camino no está determinado, lo determinamos nosotros mismos paso a paso, día a día, y se puede cambiar.
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
estructuras selectivas
.NET (C#, VB.NET, ASP)
leliCabello 3 6,460 Último mensaje 29 Marzo 2010, 20:26 pm
por leliCabello
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines