Estructuras en arbol

[Leber]

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

[Akai]

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).

[ghastlyX]

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 (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

struct Nodo {
    char c;
    Nodo *lo, *eq, *hi;
};

void add(Nodo *&nodo, string& s, int p) {
    if (p == s.size()) return;
    if (nodo == NULL) {
        nodo = new Nodo;
        nodo->c = s[p];
        nodo->lo = nodo->hi = nodo->eq = NULL;
        add(nodo->eq, s, p + 1);
    }
    else {
        if (s[p] < nodo->c) add(nodo->lo, s, p);
        else if (s[p] > nodo->c) add(nodo->hi, s, p);
        else add(nodo->eq, s, p + 1);
    }
}

bool search(Nodo *nodo, string& s, int p) {
    if (p == s.size()) return true;
    if (nodo == NULL) return false;
    if (s[p] < nodo->c) return search(nodo->lo, s, p);
    else if (s[p] > nodo->c) return search(nodo->hi, s, p);
    else return search(nodo->eq, s, p + 1);
}

int main() {
    Nodo *raiz = NULL;
    char c;
    while (cin >> c) {
        if (c == 'A') {
            string s;
            cin >> s;
            add(raiz, s, 0);
        }
        else if (c == 'S') {
            string s;
            cin >> s;
            if (search(raiz, s, 0)) cout << "String encontrada" << endl;
            else cout << "String NO encontrada" << endl;
        }
    }
}

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.

[Leber]

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 =)

[Firos]

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 (c) [Seleccionar] Expandir

typedef struct{
char nombre[20];
int año;
int var3;
int var4;
} Sdatos;

// En el main declaras el array

Sdatos array[29][500];


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 (c) [Seleccionar] Expandir

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.