3.3. Árboles de búsqueda balanceados.
Árboles binarios de búsqueda.
- Cada nodo tiene cero, uno o dos hijos. Los nodos menores se encuentran en el subárbol izquierdo y los mayores en el derecho.
- Son útiles para realizar búsqueda e inserción en O(log n), y recorrido ordenado con O(n).
- En el peor caso los árboles son cadenas y la búsqueda necesita O(n): es necesario balancear el árbol.
Árbol de búsqueda perfectamente balanceado.
- Definición: Para todo nodo, la cantidad de nodos de su subárbol izquierdo difiere como máximo en 1 de la cantidad de nodos del subárbol derecho.
- En el peor caso, la búsqueda necesita O(log n).
- La inserción puede necesitar reorganizar todo el árbol, O(n).
Árbol balanceado ó AVL (Adelson-Velskii y Landis).
- Es un árbol binario de búsqueda, con una condición de balanceo más débil que hace que no sea tan costoso el proceso de balancear un árbol.
- Definición: Para todo nodo, la altura de sus subárboles difiere como máximo en 1. (Supondremos que la altura del árbol vacío es -1.)