Arboles (trees)

Los arboles son estructuras no lineales. Una estructura de datos lineal se basan en un nodo apuntando a otro. Es decir lo visto hasta ahora, cada nodo apuntanba a un unico nodo, por lo que permitia recorrer los nodos de manera lineal dado que era ir avanzando sobre una cadena.

Pero en el caso de los árboles esto no es así, ya que los nodos pueden apuntar a un número indefinido de elementos, realmente no es indefinido por que va a ver unos límites pero que no tiene que apuntar a un único elemento, pueden apuntar a dos, a tres, incluso a ninguno.

Los árboles empiezan con el valor envuelto por una estructura llamada nodo . De modo que un árbol organiza los distintos nodos.

En el caso de un árbol los nodos se van a agrupar del siguiente modo:

Tenemos nuestro nodo y nuestro nodo tiene la particularidad de que puede apuntar a otros nodos (hijos), y a la vez puede ser apuntado por otro nodo(padre).

Existe un nodo padre importante que es el nodo raíz, que es el único nodo que no va a tener padre(en el ejemplo el 43). Pero el resto de nodos tienen que ser apuntados por otro nodo padre

El otro nodo importante es el nodo hoja que es un nodo que ya no tiene hijos. Un ejemplo completo de árbol es el siguiente:

Nodo raiz: 16 Nodo hojas: 7, 13, 21

Si separamos el nodo raíz de los nodos a los que apunta, podemos darnos cuenta que en realidad la lista de nodos a los que apunte un nodo son a su vez otro árbol, es decir un subárbol. En ocasiones se usa esta nomenclatura para referirse a los hijos de un nodo

Una particularidad importante para que una estructura pueda considerarse un árbol es que no puede tener ciclos, es decir, volver a pasar por los mismos nodos varias veces. Ejemplos:

En la izquierda B tiene dos padres, A y D y en el caso de la derecha el 4 tiene dos padres también, El del medio no se permite que un nodo apunte a si mismo y una raíz no puede ser apuntando por ningún otro elemento.

Estructura de un árbol en código

class Node{
	private int value;
	
	private List<Node> sons;
}

Propiedades de un árbol

Un árbol puede tener diferentes propiedades que veremos a continuación:

Nivel / Profundidad (depth)

Nos dice a que distancia esta un nodo del nodo raíz usando como medida los diferentes saltos hasta llegar al nodo raíz. Aquí se muestra un ejemplo del nivel de cada nodo del ejemplo anterior

Los nodos 8 y 24 tienen el nivel 1 dado que se necesita un salto para llegar al nodo raíz, y así sucesivamente para los diferentes nodos.

Path o ruta

Una secuencia de nodos conectados por aristas (edges) desde un nodo inicial hasta otro nodo, es decir, el recorrido que se puede hacer para avanzar de un nodo a otro y en este caso, una ruta podría ser 16 - 25 - 19 - 21

Altura (Height):

• La altura de un árbol es la longitud del camino más largo desde la raíz hasta una hoja.
• Se mide en niveles.

Como hemos visto antes la altura sería 3 dado que es el nivel más lejano

Balance:

• Un árbol está equilibrado si la diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo es mínima (generalmente 1 o menos).

Ejemplo árbol balanceado

Grado / Orden (Degree):

• El grado de un nodo es el número de hijos que tiene.
• El grado del árbol es el grado máximo de todos sus nodos.

Nos interesa que los árboles crezcan en profundidad(nodos con pocos hijos), frente a que crezcan en horizontal (nodos con muchos hijos) por eso se limita el número de hijos que puede tener un nodo.

Ejemplos:

Orden 2 : Un nodo puede tener 0, 1 o 2 hijos.

Orden 3 : Un nodo puede tener 0, 1, 2 o 3 hijos.

Orden 4 : Un nodo puede tener 0, 1, 2, 3 o 4 hijos.

Tipos de Árboles

Los árboles según su orden tienen nombres definidos como por ejemplo:

• Árbol binario: árbol de orden 2
• Árbol ternario: árbol de orden 3

Árbol completo

Hay otro concepto interesante de árbol completo que es aquel que todos los nodos tienen o 0 hijos o el número máximo de hijos. Por ejemplo, en un árbol binario completo, todos los nodos tienen 2 hijos o son hojas

Operaciones con árboles

• Insertar elementos
• Eliminar elementos
• Localizar elementos
• Recorrer un árbol