Fórmula o algoritmo???

MrAllOnA

Alguien sabría decirme si habría alguna fórmula o algoritmo para poder sacar la fila en la que te encuentras en cada momento?
Me explico, suponiendo que conocemos el número total de filas, que conocemos el número de nodo en el que nos encontramos, y el número de columna a la que pertenece dicho nodo, ¿habría algún algoritmo o fórmula para poder sacar la fila en la que se encuentra dicho nodo? Teniendo en cuenta que el árbol podría tener infinitas ramas, no únicamente los dos casos que muestro
Yo creo que algo se podrá hacer, pero le he dao mil vueltas y nada...


TaiCHoKe

Añade un campo que lo indique a caada nodo y listo

1 respuesta
MrAllOnA

#2 pero eso no es lo que pido :)

TaiCHoKe

Con recursividad puedes sacarlo a partir del nodo root o inicial. Yo la verdad es que no estoy acostumbrado a ver los arboles como matrices

B

#1 :
edit :

Los primeros nodos de cada columna ocupan un número de fila que son potencias de dos menos uno, si nos fijamos , la fórmula en concreto es :

(2n) - 1

La distancia entre nodos es también de potencias de dos menos uno, si lo que nos interesa es sumar en función de en qué nodo estamos , nos queda :

( 2n+1 )

Entonces supongo que :

-El cálculo directo es F(num_nodo,columna) = (2columna) - 1 + ( 2columna+1 )*num_nodo

-Para árboles n-arios , las potencias serán como de tantas ramas haya.

MrAllOnA

Esa fórmula que has puesto no funciona, la probé con el nodo numero 2 (perteneciente a la columna número 2) y devuelve 19, teniendo que devolver 3.

Gracias de todos modos ;)

Por cierto, algo he sacado pero más a nivel de programación que a nivel matemático, ahora lo pongo.

1 respuesta
MrAllOnA

Bueno pues aquí va algo que he pensado, eso si, muy enrevesado... xddd
Es a nivel de programación, ya que algo a nivel matemático no he sido capaz de sacar.

• Tenemos el número total de filas: numFilas

• Dividimos dicho número de filas entre 2 para sacar el número de nodos de la columna 0:
nodosCol0 = numFilas/2

• Calculamos el logaritmo en base 2 de nodosCol0 para sacar el número de columnas:
numCol = log(nodosCol0)/log(2)

• Creamos una matríz [numCol X nodosCol0] que albergue por cada columna, los números de nodo que le pertenecen:
Recorremos el arbol de la manera que hay que recorrerlo, desde el nodo 0--> http://oi47.tinypic.com/2dwcnes.jpg
Puesto que para cada nodo conocemos su columna almacenamos cada uno en su registro de la matríz correspondiente, quedando la matríz de esta manera una vez recorrido todo el arbol:

[b]Col0-->0, 4, 5, 7, 8, 11, 12, 14
Col1-->1, 6, 9, 13
Col2-->2, 10
Col3-->3[/b]

• Recorremos la matríz para sacar las filas de los nodos que contiene (suponiendo que la matríz comienza en 0):
Obtenemos un multiplicador (multi) que, multiplicado por la posición de los nodos en la matríz, nos devolverá la fila que ocupa dicho nodo. De esta manera iremos almacenando las filas de cada nodo en un array, el cual contendrá todos los nodos ordenados por filas y no según el orden indicado inicialmente.

[code]for(p=0; p<=numCol; p++){

	multi = 2^(p+1);

	for(j=0; j<nodosCol0; j++){

		fila = j * multi + sumatorio(p);
		array[fila] = matriz[p][j];
	}
}[/code]

• El array que obtendremos para el caso del árbol grande que he puesto en la foto sería el siguiente, es decir el orden "por filas" de los nodos:
[0, 1, 4, 2, 5, 6, 7, 3, 8, 9, 11, 10, 12, 13, 14]

¿Como lo veis? a ver si alguien podría aportar algo más matemático, en caso de que fuera posible ;)

B

#6 Es que lo he hecho suponiendo que con número de nodo te referías a si era el primer nodo , segundo , etc ... empezando por cero y arriba desde la primera imagen. Haciéndolo así sí funciona. De hecho, pensaba que los números de los nodos de tus imágenes eran pesos random y que por número de nodo te referías a algo así.

De hecho , reciclando mi fórmula anterior , pero añadiendo pasos previos , funciona igual , ahora que caigo :

-Si num_nodo == columna , num_nodo para la fórmula anterior será cero , si no , "vuelves atrás" hasta encontrar el nodo del mismo valor y cuentas cuántas vueltas has hecho. Esa guarrada lineal sumada a la fórmula de antes diría que sí va. Porque para ser sinceros , no tengo ni zorra de a qué hacen referencia el resto de números xD.

MrAllOnA

no no, los números de nodo son el orden en que se van leyendo los nodos, y busco obtener los nodos ordenados por filas.

Llevo todo el día entero con esto, madre mia... ajjajaja

1 respuesta
B

#9 Por cierto , ¿cómo generas los grafos así en imagen? puede serme bastante útil esto la verdad.

1 respuesta
MrAllOnA

#10 haha na! con un programilla tipo paint pero más completo, circulito a circulito, sin mas... xdd

LOc0

Por lo que veo parece el típico árbol binario de búsqueda (a la izquierda los menores y a la derecha los mayores). Si es así y vas subiendo desde el nodo actual hasta el raíz lo tienes. Si subes desde la "derecha" restas, y si es desde la "izq" sumas. Lo que sumas o restas es 1, 2, 4, etc...

Ejemplo con

Para sacar la fila del nodo 7:

-1 (6), -2 (2)

Ahora desde el raíz (2), inviertes hasta llegar al (7) Como son 7 filas el raíz está en la fila 3: 3 + 2 + 1 = 6

Para sacar el nodo 5:
+1(6), -2 (2)

3 + 2 -1 = 4

Necesitas que cada nodo guarde puntero a su padre, eso sí.

Salu2 ;)

1 respuesta
MrAllOnA

#12 liada mia, que la imagen 2 estaba equivocada... joder...
Es esta:

LOc0

Y si lo que quieres es tener todo el árbol en un array ordenado por filas, hazte una función recursiva tal que:

pseudo_codigo_guarro

Salu2 ;)

1 respuesta
MrAllOnA

#14 lo dicho, esa imagen estaba mal, tiene que ser esta, ya que siempre tienen que seguir este recorrido: http://oi47.tinypic.com/2dwcnes.jpg
y por ese motivo tal vez también lié a kyelek, cawen die...

LOc0

Lo que he entendido que quieres hacer es "aplastar" el árbol y convertirlo en un array ordenado por filas, y de esa forma saber la fila con saber el nodo. Eso lo puedes hacer con #14 Si NO es eso, pues NI idea.

Me tengo que pirar a dormir, sorry.

Salu2 ;)

1 respuesta
MrAllOnA

#16 pues eso es lo que quiero si, voy a probar si con tu algoritmo saldría, muchas gracias ;)

Pues la verdad que no logro ver lo que hace tu algoritmo. Como funciona el merge?

LOc0

array_merge sería una función que "pega" arrays. Recibe N arrays y devuelve uno.

Salu2 ;)

Usuarios habituales