Algoritmo creacion arbol binario optimo
Publicado por Rakan (43 intervenciones) el 18/11/2018 23:58:46
He estado mirando y no he encontrado nada que explique que formula utilizar para ordenar los valores de una lista, de tal forma que queden en un orden en el cuál al ser añadidos al arbol binario, se genere un árbol optimo.
Esto iría muy bien para ser implementado en un ámbito cliente-servidor, para agilizar los tiempos de carga del cliente, si hay algún arbol binario en el javascript. El servidor ordena los valores con este algoritmo y los envia al cliente, así el navegador no tiene que ordenar el arbol.
He puesto un título lo más descriptivo posible, por si conseguimos hacer este algoritmo, pues que la gente lo pueda encontrar y utilizar facilmente.
Por ahora, la única forma con la que he conseguido este orden (un lío de bucles y listas horrible), ha sido pasando los valores de la lista con los valores ordenados, hacia otra, haciendo saltos binarios en todas las combinaciones posibles. Por ejemplo:
[1, 2, 4, 5, 6, 8, 10, 12, 20]
Primer salto (añadido el 6):
[6]
Segundo salto (añadidos 2 y 10):
[6, 2, 10]
Tercer salto (añadidos 1, 4, 8 y 12):
[6, 2, 10, 1, 4, 8, 12]
Cuarto salto (añadidos 5y 20):
[6, 2, 10, 1, 4, 8, 12, 5, 20]
Pero es muy malo el sistema que he hecho de mirar todas las combinaciones, por cada valor de la lista se crean como 5 en otras listas, y si se tienen muchos elementos (lo habitual cuando se trabaja con arboles binarios), va a saturar la memoria, además que irá muy lento. Cosa que se quiere evitar a toda costa desde el servidor.
Visto esto, tras pensar un buen rato, me he dado cuenta de que si ya se tienen los valores ordenados, no hace falta hacer búsqueda binaria para ordenarlos de forma optima.
Ya que para
[1, 2, 4, 5, 6, 8, 10, 12, 20]
siempre que esté ordenada, lo unico que nos interesa es saber en que posición recolocar cada indice de la lista, independientemente del valor que tenga dentro (la lista debería estar ordenada ya).
Quedando algo como
[0, 1, 2, 3, 4, 5, 6, 7, 8]
Por lo que todas las listas de 9 elementos, los elementos se organizarían de la misma manera.
Pero soy programador autodidacta, por lo que asuntos como éste, donde hace falta crear una formula algebraica, se me escapan de las manos.
Creo que seríamos los primeros en hacer algo así ^.^
Alguien se anima a intentarlo?
Esto iría muy bien para ser implementado en un ámbito cliente-servidor, para agilizar los tiempos de carga del cliente, si hay algún arbol binario en el javascript. El servidor ordena los valores con este algoritmo y los envia al cliente, así el navegador no tiene que ordenar el arbol.
He puesto un título lo más descriptivo posible, por si conseguimos hacer este algoritmo, pues que la gente lo pueda encontrar y utilizar facilmente.
Por ahora, la única forma con la que he conseguido este orden (un lío de bucles y listas horrible), ha sido pasando los valores de la lista con los valores ordenados, hacia otra, haciendo saltos binarios en todas las combinaciones posibles. Por ejemplo:
[1, 2, 4, 5, 6, 8, 10, 12, 20]
Primer salto (añadido el 6):
[6]
Segundo salto (añadidos 2 y 10):
[6, 2, 10]
Tercer salto (añadidos 1, 4, 8 y 12):
[6, 2, 10, 1, 4, 8, 12]
Cuarto salto (añadidos 5y 20):
[6, 2, 10, 1, 4, 8, 12, 5, 20]
Pero es muy malo el sistema que he hecho de mirar todas las combinaciones, por cada valor de la lista se crean como 5 en otras listas, y si se tienen muchos elementos (lo habitual cuando se trabaja con arboles binarios), va a saturar la memoria, además que irá muy lento. Cosa que se quiere evitar a toda costa desde el servidor.
Visto esto, tras pensar un buen rato, me he dado cuenta de que si ya se tienen los valores ordenados, no hace falta hacer búsqueda binaria para ordenarlos de forma optima.
Ya que para
[1, 2, 4, 5, 6, 8, 10, 12, 20]
siempre que esté ordenada, lo unico que nos interesa es saber en que posición recolocar cada indice de la lista, independientemente del valor que tenga dentro (la lista debería estar ordenada ya).
Quedando algo como
[0, 1, 2, 3, 4, 5, 6, 7, 8]
Por lo que todas las listas de 9 elementos, los elementos se organizarían de la misma manera.
Pero soy programador autodidacta, por lo que asuntos como éste, donde hace falta crear una formula algebraica, se me escapan de las manos.
Creo que seríamos los primeros en hacer algo así ^.^
Alguien se anima a intentarlo?
Valora esta pregunta
0
