El árbol es una estructura de datos fundamental en la informática, muy utilizada en todos sus campos, por que se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación.
La definición de un árbol implica una estructura recursiva. Esto es, la definición del árbol se refiere a otros árboles. Un árbol con ningún nodo es un árbol nulo; no tiene raíz.
-----Nodo:
Un nodo es un punto de intersección o unión de varios elementos que confluyen en el mismo lugar.
-----Árboles Binarios:
Existe un tipo de árbol denominado árbol binario que puede ser implementado fácilmente en una computadora.
Un árbol binario es un conjunto finito de cero o más nodos tales que:
-Existe un nodo denominados raíz del árbol.
-Cada nodo puede tener 0, 1 o 2 subárboles, conocidos como subárbol izquierdo y subárbol derecho.
-Y estos no pueden tener más de dos hijos (de ahí el nombre "binario")
-----Arboles AVL:
Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus
nodos es, como mucho 1.
Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n).
El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.
Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
