Arboles AVL

Arboles AVL.
Los arboles llamados AVL, en honor de los matemáticos rusos G.M Adel’son-Vel’skii y E.M. Landis, quienes los definieron por vez primera. Un árbol AVL es un árbol balanceado enaltura. Esto significa que existe un límite en la magnitud de la diferencia que se permite entre las alturas de cualesquiera dos subárboles que comparten una raíz común. En un árbol AVL la diferenciamáxima permitida es 1. Por lo tanto, a un árbol AVL se le llama árbol-1 balanceado en altura, o árbol BA(k), a los cuales se permite estar k niveles fuera de balance.
Las dos características en las queradica la importancia de los árboles AVL son:
Al establecer una diferencia máxima permitida en la altura de cualesquiera dos subárboles, los árboles AVL garantizan un cierto nivel mínimo dedesempeño en la búsqueda, y
El mantener un árbol en forma AVL conforme se insertan nodos nuevos implica el uso de una de cuatro posibles rotaciones. Cada una de ellas se restringe a una única área local delárbol. Las rotaciones más complejas requieren solo cinco resignaciones de apuntadores.
Los arboles AVL son una clase importante de estructura de datos. Las operaciones utilizadas para construir ymantener arboles AVL se describen en Knuth (1973b), Standish (1980) y en otros autores. Los arboles AVL no son por si mismos aplicables a la mayoría de los problemas de estructuras de archivos porque,como todos los árboles estrictamente binarios, tienen demasiados niveles; son demasiado profundos. Sin embargo, en el contexto del análisis general del problema de acceso y mantenimiento de índices queson demasiado grandes para entrar en memoria, los árboles AVL son interesantes por que sugieren la posibilidad de definir procedimientos que mantengan un balance en altura.
El hecho de que un árbolAVL este balanceado en altura garantiza que el desempeño de la búsqueda se aproxima al de un árbol completamente balanceado.
Para un árbol completamente balanceado, el peor caso de la búsqueda...