Árboles
El árbol es un tipo especial de relación de excepcional utilidad, con gran aplicación en las ciencias de la computación y que por lo general se representa mediante un dígrafo. Estas relaciones son esenciales para construir bases de datos y compiladores de lenguajes de computación, por nombrar solamente dos áreas importantes.
Sea A un conjunto y T una relación en A. T es un árbol si existe un vértice v0 en A con la propiedad de que existe una única trayectoria en T de v0 hacia cualquier otro vértice en A, pero no existe una trayectoria de v0 a v0.
El vértice v0 es único. Con frecuencia es llamado raíz del árbol T, siendo T un árbol con raíz. Se escribe (T, v0) para denotar un árbol T con raíz v0.
Si (T, v0 ) es un árbol con raíz sobre el conjunto A, un elemento v de A es un vértice en T.
Teorema 1.
Sea (T, v0) un árbol con raíz. Entonces:
No existen ciclos en T.
V0 es la única raíz en T.
Cada vértice en T distinto de v0 tiene grado interno 1, y v0 tiene grado interno 0.
El teorema 1 resume las propiedades geométricas de un árbol. Con estas propiedades en mente, es posible analizar la apariencia del dígrafo de un árbol típico.
Primero se traza la raíz v0. Ninguna arista entra a v0 , pero pueden salir varias, las cuales generalmente son trazadas hacia abajo. Los vértices terminales de las aristas que inician en v0 son los vértices de nivel 1, mientras que v0 está en el nivel 0. También se acostumbra decir que v0 es el padre de estos vértices de nivel 1, y los vértices del nivel 1 son los hijos de v0 . Cada vértice en el nivel 1 no tiene otras aristas que entren en él, por la parte (c) del teorema 1, pero cada uno de esos vértices puede tener varias aristas que salgan de él. Se trazan las aristas que salen de un vértice de nivel 1 hacia abajo y terminan en diversos vértices, que existen en el nivel 2. En estos niveles también existe una relación padre – hijo ( y en cada pareja consecutiva de niveles). Los hijos de cada uno de los vértices son llamados hermanos.
El proceso anterior continúa con tantos niveles como sean necesarios para completar el dígrafo. Si se observa el dígrafo de arriba hacia abajo, se entiende por qué a estas relaciones se las llama árboles. El mayor nivel de un árbol, es la altura de éste. Los vértices del árbol que no tienen hijos son las hojas del árbol.
Los vértices de un árbol que se encuentran en cualquier nivel forman simplemente un conjunto de vértices en A. Sin embargo, por lo general, es útil suponer que los hijos de cada vértice del árbol están linealmente ordenados. Así si un vértice v tiene cuatro hijos, se supondrá que están ordenados, por lo que se hará referencia a ellos como el primero, segundo, tercero y cuarto hijo de v. Siempre que se trace el dígrafo del árbol, se supondrá un orden en cada nivel, al disponer los hijos de izquierda a derecha. Un árbol de este tipo es un árbol ordenado.
Ejemplo.
Sean A = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10} y T = {(v2, v3), (v2, v1), (v4, v5), (v4, v6), (v5, v8), (v6, v7), (v4, v2), (v7, v9), (v7, v10)}. Muestre que T es un árbol con raíz e identifíquela.
Solución:
Ninguna trayectoria inicia en lo vértices v1, v3, v8, v9 y v10. Por lo tanto estos vértices son las hojas del árbol. No existen trayectorias de los demás vértices a v4, por lo que se deben eliminar como posibles raíces. Así, si T es un árbol, su raíz es v4.
Se muestra a continuación la estructura de dicho árbol.
Si n es un entero positivo, un árbol T es un n-árbol (árbol n-ario) si cada vértice tiene a lo más n hijos. Si todos los vértices de T distintos de las hojas tienen exactamente n hijos, T es un n-árbol completo. En particular, con frecuencia se dice que un 2-árbol es un árbol binario, y un 2-árbol completo es un árbol binario completo.
Teorema 2.
Si (T, v0) es un árbol con raíz y v ∈ T, entonces T(v) también es un árbol con raíz v. T(v) es el subárbol de T que comienza en v.
Ejemplo.
Considere el árbol T de la figura anterior. Este árbol tiene raíz v4. A continuación se muestran los subárboles T(v5), T(v2) y T(v6) de T.
