Definición de árboles.

En las ciencias de computación y en la informática los arboles son un tipo abstracto de datos que imita la estructuración jerárquica propia de los árboles (característica porque un objeto y sus componentes tienden a converger en un origen o una raíz).

A su vez un árbol se puede definir como un grafo conexo y acíclico es decir un grafo en el cual se puedan tomar dos vértices (cualesquiera sean) y hallar una cadena entre ambos y a su vez donde para ninguna cadena coincidan el vértice inicial con el vértice final (que no presente bucles o ciclos).

Una forma de determinar si un grafo es un árbol es mediante el numero cíclico (ϕ) que se obtiene de la siguiente manera:

• Para grafos conexos:

  Φ(G) = /A/ - /V/ + 1

• Para grafos con k componentes conexas:

  Φ(G) = /A/ - /V/ + k

En donde:

                               • /A/ es el número de aristas del grafo G.
                               • /V/ es el número de vértices del grafo G.

Si el numero cíclico de un grafo es igual a cero el mismo no presenta ciclos por lo que si cumple con la condición de ser conexo es un árbol.

Si su número cíclico es igual a uno el grafo presenta un ciclo y por último si el numero cíclico es mayor a 1 el grafo tendrá más de un ciclo (en este caso el numero cíclico no nos indicará la cantidad de ciclos que presenta). Una forma de conocer el número cíclico de un grafo es analizando la cantidad de aristas que hay que quitarle para que el mismo se convierta en un árbol.

Cada vértice recibe el nombre de nodo en donde decimos que el nodo A es padre del nodo B si existe un arco que los conecte, de forma reciproca también podemos sentenciar que B es hijo de A. En un árbol solo puede existir un único nodo que no es hijo de otro recibiendo el nombre de raíz, si un nodo no tiene hijos se denomina hoja, el resto de los nodos los cuales tienen un padre y uno o varios hijos reciben el nombre de ramas.

Estos árboles con presencia de una raíz reciben el nombre de árboles orientados en donde:

G= (V, A, Φ) será un árbol orientado de raíz Vi si cumple con las siguientes condiciones:

• Vi no es extremo terminal de ningún arco (es decir no tiene ningún nodo padre).
• G no tiene circuitos (es acíclico).
• Para todos los Vj que componen el árbol se da que es extremo terminal de un solo arco (ningún nodo tiene más de 1 padre).

Los arboles orientados pueden dividirse en niveles y la cantidad de niveles que presente un árbol se denomina altura.

Un conjunto de árboles recibe el nombre de bosque.

Clasificación de árboles.

Los arboles se pueden clasificar en relación a la cantidad de nodos y a la forma en la que los mismos se relacionan como así también en función de la altura.

1. Siguiendo la línea de la cantidad de nodos podemos destacar los siguientes tipos de árboles:

• Arboles Binarios: Se caracterizan porque cada nodo tiene un máximo de 2 nodos hijos (puede tener uno o ninguno). Son muy utilizados en el área de la informática y la programación puesto que al presentar solo dos nodos hijos los mismos se pueden asociar a valores binarios (0 y 1).
• Decimos que un árbol binario es completo cuando cada nodo padre tiene dos nodos hijos o bien ninguno (no puede tener solo uno).

A la izquierda un árbol binario no completo y a la derecha uno completo.


A su vez si un cada nodo de un árbol tiene un máximo de k hijos decimos que dicho árbol es k-ario.

Árbol Ternario (máximo 3 nodos hijos por cada nodo padre)

Árbol Cuaternario (máximo 4 nodos hijos por cada nodo padre)

   2. En relación a la altura (h) de un árbol podemos describir la siguiente clasificación:                        

• Árbol balanceado: Decimos que un árbol esta balanceado cuando la diferencia de altura entre dos hojas (cualesquiera sean) es menor o igual a uno
• Árbol desbalanceado: De forma contraria un árbol desbalanceado o no balanceado será aquel en el que la diferencia de altura en al menos un par de hojas sea superior a 1.