¿Por qué necesitamos un árbol AVL en informática?

En un árbol de búsqueda binario estándar, el número de elementos en el árbol que debe examinar para encontrar, insertar o eliminar un elemento es el número de nodos en la ruta desde la raíz hasta la raíz buscada, insertada o eliminada. nodo. Esto depende de la forma del árbol en particular. Por ejemplo, supongamos que construimos un árbol de n elementos por inserción repetida y los elementos se insertan en orden ordenado (quizás los datos fueron ordenados por una aplicación anterior). Entonces el árbol degenera en una lista vinculada; Todos los nodos están en una sola ruta. Ahora, una búsqueda debe examinar todos los n nodos en el peor de los casos y aproximadamente n / 2 nodos en promedio (suponiendo que todos los nodos tengan la misma probabilidad de ser buscados). Esto es muy malo en comparación con el valor lg n que obtenemos cuando el árbol está perfectamente equilibrado.

El propósito del árbol AVL es evitar los árboles mal formados y garantizar que el árbol esté siempre bien equilibrado para garantizar que tengamos buenos tiempos de búsqueda, inserción y eliminación.

Supongamos que construimos un árbol (binario o AVL) insertando repetidamente n elementos distintos en un árbol inicialmente vacío. A continuación se presenta una comparación del número promedio de elementos de datos que debemos examinar para encontrar un nodo que esté en el árbol para los dos tipos de árboles. (en lo siguiente lg n significa log base 2 de n).

Árboles de búsqueda binaria

árbol del mejor caso: <= lg n

caso promedio (promedio sobre todos los árboles suponiendo que cada orden de inserción es igualmente probable): (aprox.) 1.39 lg n

árbol del peor de los casos: (n + 1) / 2

Árboles AVL

árbol del mejor caso: <= lg n (idéntico al mejor caso del árbol binario)

promedio: ???

árbol del peor de los casos: 1,44 lg n

Observe que el peor caso para un árbol AVL es solo un poco peor que el caso promedio para un árbol de búsqueda binario (la constante es solo un 3.6% más alta). Empíricamente, los árboles AVL son más eficientes que los árboles de búsqueda binarios.