¿Por qué es
importante el balanceo en un árbol de búsqueda?
La
manera en que los elementos estén distribuidos en un árbol de búsqueda
determinara su altura y, en consecuencia, la cantidad de comparaciones a
realizar al buscar un elemento. Lo ideal sería que el árbol tuviera sus
elementos distribuidos en forma equilibrada o balanceada, consiguiendo así la
mayor eficiencia que ofrece la búsqueda binaria.
¿Cuál es el número
máximo de comparaciones que se realizan en el peor caso de búsqueda en un ABB?
La
cantidad máxima de comparaciones al realizar una búsqueda en un ABB está
determinada por la altura del árbol.Si
un BB degenera en una lista, se tiene un árbol cuya altura es igual a la
cantidad de nodos en el árbol.
¿Qué es un árbol balanceado?
Se
considera que un árbol esta balanceado cuando todos sus niveles, excepto el
ultimo, están integrados a la máxima capacidad de nodos.
¿Qué es un árbol
AVL?
Un
árbol AVL es un árbol binario de búsqueda que trata de mantenerse lo más
balanceado posible, conforme se realizan operaciones de inserción y eliminación.
Fueron propuestos en 1962 por los matemáticos rusos Adelson-Velskii y Landis.
En
estos se debe cumplir el hecho de que para cualquier nodo del árbol, la
diferencia entre las alturas de sus subárboles no exceda una unidad.
No hay comentarios:
Publicar un comentario