No estoy seguro de si mi respuesta satisfará suficientemente tu curiosidad, pero déjame seguir adelante y darle una oportunidad.
Antes de llegar a la magia que son las operaciones de inserción y eliminación de un árbol AVL, recopilemos algunos antecedentes. Primero, existían árboles binarios que simplemente seguían una propiedad directa: el nodo raíz es un padre y puede tener un máximo de dos hijos. Y cada niño más adelante sigue la misma propiedad si hay más elementos para insertar. Ninguna otra propiedad ni restricciones.
- ¿Puede la longitud de un comando Mathematica o Wolfram | Alpha ser una aproximación aproximada de su complejidad de Kolmogorov?
- ¿Qué tan útil es el algoritmo genético?
- ¿Cómo realizo la codificación de huffman usando lista enlazada?
- ¿Cómo es tomar CS 267 (Algoritmos gráficos) en Stanford?
- Cómo generar una lista de todas las permutaciones de una matriz 4 × 4 con solo los números 1, 2, 3 y 4 en Python
(Un árbol binario)
Aunque esto era bonito y todo eso, no tenía ningún propósito superior en lugar de simplemente almacenar los elementos como un árbol. La búsqueda de una mejor manera de usar esta propiedad condujo a lo que se conoció como el Árbol de búsqueda binaria. El último punto de venta de un árbol de búsqueda binario, como su nombre lo indica, es su propiedad de búsqueda. Buscar un elemento en un árbol binario es casi similar a buscar un elemento en una matriz no ordenada. La complejidad de encontrar un elemento en un árbol binario es [math] O (n) [/ math]. Pero si introduce una nueva propiedad, la complejidad del tiempo de búsqueda se reduce a [math] O (log n) [/ math]. Esto se debe a una técnica llamada búsqueda binaria que también se puede utilizar en una matriz ordenada. Un árbol de búsqueda binario o un bst tiene una propiedad adicional que dice que todos los hijos izquierdos son menores que la raíz y todos los hijos derechos son mayores que la raíz. Esta propiedad nos ayudó a modificar el árbol binario y, al mismo tiempo, nos ahorró mucho tiempo de búsqueda.
(Un árbol de búsqueda binario)
Pero había un problema con un árbol de búsqueda binario. Cuando los elementos no estaban disponibles en un orden conveniente, el árbol de búsqueda binario seguía creciendo en una dirección particular y se veía así:
Se ve tonto, ¿no? Entonces idearon un concepto llamado balancear un árbol de búsqueda binario que esencialmente mantiene la altura de un árbol de búsqueda binario al mínimo. Después de equilibrar el árbol anterior se vería así:
Esto se ve bien, ¿no?
Por lo tanto, los informáticos no querían hacer esta actividad mundana de equilibrar un árbol de búsqueda binario cada vez que se introduce un nuevo nodo. Como resultado, introdujeron una propiedad más llamada equilibrio. Los árboles AVL no son más que árboles de búsqueda binarios que tienen una capacidad especial llamada auto-equilibrio. Entonces, cada vez que se introduce un nuevo nodo, el árbol AVL verifica si la altura del árbol es mínima. Si no, gira y trata de hacer que la altura sea mínima.
Por ejemplo, considere el siguiente árbol:
Si introduzco un nuevo elemento, digamos 19, el árbol perderá su propiedad de altura mínima. Lo que significa que, el árbol puede bajar aún más de altura. Para lo cual desplazará los elementos 16 y 18, y hará que 18 sea el nodo raíz de ese subárbol particular y que 16 y 19 sean sus hijos. Esta rotación tendrá lugar de forma recursiva cada vez que se viole la altura mínima. La siguiente imagen hace un buen trabajo al describir los múltiples casos que surgirían al insertar elementos en un árbol AVL.
Imágenes cortesía: Wikipedia.
