ArbolesAVL

Arboles AVL
Objetivos:
Entender la importancia que tiene el balanceo en un ABB.
Describir las características de los AVL: balanceo badsado
en alturas de subarboles.
Definir el factor de balance(FB) de un nodo en un árbol
AVL.
Rotación simple y rotación doble en un árbol AVL.


Estructura de Datos

M

¿Por qué es importante el balanceo
en un árbol de búsqueda?
La manera en que los elementosestén distribuidos en un
árbol de búsqueda determinará su altura y, en consecuencia,
la cantidad de comparaciones a realizar al buscar un elemento
(eficiencia).

Lo ideal sería que el árbol tuvierasus elementos
distribuidos en forma equilibrada o balanceada, consiguiendo
así la mayor eficiencia que ofrece la búsqueda binaria
Estructura de Datos

¿Cuál es el número máximo de
comparaciones quese realizan en el
peor caso de búsqueda en un ABB?
Análisis general de la eficiencia de búsqueda en
un ABB.
La cantidad máxima de comparaciones al realizar una
búsqueda en un ABB está determinada porla altura del árbol.
Si un árbol degenera en una lista, se tiene un árbol cuya altura
es igual a la cantidad de nodos en el árbol, y el peor caso
corresponderá a realizar tantas comparaciones comonodos
tenga el árbol.
Estructura de Datos

¿Cuál es el número máximo de
comparaciones que se realizan en el
peor caso de búsqueda en un ABB?
¿Qué pasa si el árbol está balanceado?

Si la altura de un ABBdetermina la cantidad máxima de
comparaciones en una busqueda, lo ideal sería tener la altura
mínima que puede tener un ABB para n elementos.
La altura mínima en un ABB con n elementos se dará en lamedida en cada nivel del árbol esté integrado a su máxima
capacidad
Estructura de Datos

¿Cuál es el número máximo de
comparaciones que se realizan en el
peor caso de búsqueda en un ABB?

En general,se tiene que el número máximo de nodos en el
nivel k en un árbil binario es

2k

Con base en esto, se puede encontrar la cantidad total de
elementos que puede guardar un árbol binario de altura k....