Árboles

Un árbol es un conjunto de nodos donde cada nodo puede tener 0 o más hijos y a lo más un padre. Existe un único nodo que no tiene padre y es denominado nodo raíz¹. Los nodos que tienen hijos se llaman ramas. Y los nodos que no tienen hijos se llaman hojas.

Tomaremos el concepto general de árbol como el definido por algunos autores como árbol de búsqueda de acceso múltiple:

``Un árbol de búsqueda de acceso múltiple de orden n es un árbol general en el cual cada nodo tiene n o menos subárboles y contiene una llave menos que la cantidad de subárboles...Además si $s_0, s_1, \ldots, s_{m-1}$ son los m subárboles de un nodo que contiene llaves $k_0, k_1, \ldots, k_{m-2}$ en orden ascendente, todas las llaves en el subárbol s₀ son menores o iguales que k₀, todas las llaves en el subárbol s_j (donde j está entre 1 y m-2) son mayores que k_j-1 y menores o iguales que k_j, y todas las llaves en el subárbol s_m-1 son mayores que k_m-2. El subárbol s_j se llama el subárbol izquierdo de llave k_j y su raíz el hijo izquierdo de llave k_j. De manera similar s_j se llama el subárbol derecho y su raíz el hijo derecho, de llave k_j-1''[1].

Así, de manera particular un árbol binario es un árbol de orden 2 donde cada nodo tiene una llave y dos subárboles hijos. Como se puede apreciar en la figura 1.

  

Figure 1: Árboles de orden 2 (a) y de orden 4 (b).

Los árboles presentan problemas de eficiencia si no se construyen en forma balanceada, lo que puede resultar en la creación de un árbol degenerado --árboles que se construyen en base a una entrada ordenada y al terminar de construirlos se asemenjan a una lista ligada --. Los otros problemas a considerar son las operaciones que se realizan sobre los datos del árbol como son: el tiempo de recuperación, borrar datos, insertar datos y recorrer en forma ordenada todos sus elementos.