Discusión sobre el artículo "Del básico al intermedio: Colas, listas y árboles (VIII)"
Está perdiendo oportunidades comerciales:
- Aplicaciones de trading gratuitas
- 8 000+ señales para copiar
- Noticias económicas para analizar los mercados financieros
Registro
Entrada
Usted acepta la política del sitio web y las condiciones de uso
Si no tiene cuenta de usuario, regístrese
Artículo publicado Del básico al intermedio: Colas, listas y árboles (VIII):
En el artículo anterior, Del básico al intermedio: Colas, listas y árboles (VII), explicamos una de las muchas formas posibles de eliminar un nodo de un árbol. Esta operación debe comprenderse muy bien para poder trabajar con árboles destinados a distintos fines. Como mencionamos en el artículo anterior, existen otras formas de implementar la eliminación. Sin embargo, a mi parecer, la que mostramos allí es una de las más sencillas entre las que no utilizan recursividad. Conviene evitar la recursividad al eliminar nodos porque, si es necesario borrar varios datos almacenados en nodos muy profundos, habrá que apilar numerosas llamadas para llegar a cada nodo y después desapilarlas. Este recorrido recursivo genera un coste computacional considerable y aumenta el tiempo necesario para ejecutar las operaciones de construcción y mantenimiento del árbol.
Bien, es necesario comprender lo explicado. De forma muy parecida, la operación de búsqueda debe diseñarse con mucho cuidado para evitar que aumente innecesariamente su tiempo de ejecución. Sin embargo, aquí surge una dificultad adicional: mantener equilibrado el árbol. Comprender esta cuestión es tan importante, o quizá incluso más, que entender los algoritmos de inserción, eliminación y búsqueda ya implementados o pendientes de implementar.
Por tanto, en este artículo veremos qué significa equilibrar un árbol y por qué es tan importante. También comenzaremos a comprender por qué a veces no podemos o no debemos reequilibrar el árbol —cuestión cuya aplicación práctica se abordará en otro artículo—, aunque la estructura conserve una diferencia de altura entre algunos subárboles. Ese desequilibrio estructural puede alargar determinados recorridos, pero no constituye por sí mismo una medida del tiempo de ejecución. Una búsqueda, inserción o eliminación tardará más o menos según la ruta que recorra y la cantidad de nodos que deba visitar. En cualquier caso, pasemos al tema principal de este artículo.
Autor: CODE X