Balancear un arbol binario

Hyemin · #1 (**permalink**) 09/01/2018, 17:47

Hola como están?

Estoy implementando un arbol binario de busqueda en pyhton, tengo todo hecho menos un metodo que balancee el arbol.

Estoy estudiando ahora el Day–Stout–Warren (DSW) algorithm pero me esta costando algo (bastante implementarlo)

Una idea para balancear el arbol que se me ocurria es bizarra, seria meter los nodos en un vector y tomar de a uno aleatoriamente para generar un nuevo arbol, esto en arboles muy trabajados (con mchos nodos insertados y borrados) me puede dar algo de balance pero es muy sucio.

Alguien implemento en Pyhton algo asi? estuve buscando en stackoverflow pero todas las respuestas terminan apuntando al mismo paper que estoy leyendo

La implementacion del arbol esta aca por sila quieren ver o simplemente necesitan un arbol :)

https://github.com/Alexevh/AEDP

Koan · #2 (**permalink**) 18/01/2018, 13:16

Hola!

Yo hace tiempo estuve preguntando por el tema de los árboles. Pero por una cosa u otra no le encontraba una aplicación en mi aprendizaje de python. Y lo deje de lado. Aparte, igual no tengo aún un nivel aceptable para entender esta estructura. Te paso un enlace de un canal donde su autor explica las cosas muy bien y toca estas estructuras.

Me gustaría, aparte, que me dijeras que usos se le pueden dar a los árboles y si recomiendas su estudio. Un saludo!

https://www.youtube.com/channel/UC_5...gZCMJlg/videos

Hyemin · #3 (**permalink**) 18/01/2018, 19:10

Cita:

Iniciado por Koan

Hola!

Yo hace tiempo estuve preguntando por el tema de los árboles. Pero por una cosa u otra no le encontraba una aplicación en mi aprendizaje de python. Y lo deje de lado. Aparte, igual no tengo aún un nivel aceptable para entender esta estructura. Te paso un enlace de un canal donde su autor explica las cosas muy bien y toca estas estructuras.

Me gustaría, aparte, que me dijeras que usos se le pueden dar a los árboles y si recomiendas su estudio. Un saludo!

https://www.youtube.com/channel/UC_5...gZCMJlg/videos

Definitivamente te recomiendo el estudio de arboles y grafos por varias razones

Hay muchas cosas que usan grafos y arboles y que nosotros usamos "sin saber" y cuando terminas estudiando teorias de bases de datos por ejemplo ves los ABB muy a menudo y si sabes de arboles entiendes mejor.

En deep learning se usan mucho los grafos y aunque usemos herramientas como keras y tensorflow cuando estudiamos como funcionan tambien conviene aber al menos la teoria de grafos.

En la vida practica te puede servir para muchas cosas, por ejemplo una búsqueda en un ABB (balanceado) es mucho mas rápida que en una lista, es log(n)