Arboles

• 
  
• 
  
• 

Concepto

En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Definicion: 

Formalmente, podemos definir un árbol de la siguiente forma:

• Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

• Un nuevo árbol a partir de un nodo n_r y k árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre n_r y cada una de las raíces de los k árboles. El árbol resultante de nodos tiene como raíz el nodo n_r, los nodos son los hijos de n_r y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles A_i se les denota ahora subárboles de la raíz.

Recorridos:

• El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
• El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A₁, luego la raíz y luego cada uno de los hijos en orden simétrico.
• El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico (ver también teoría de grafos y Glosario en teoría de grafos)

Tipo de Arboles: 

•  Árboles Binarios
• En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").  

•   Árbol binario de búsqueda auto-balanceable
• En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente
• Árbol AVL 
• es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó

• Árbol rojo-negro

• es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”

•  Árbol AA
• En informática un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson.

• Árboles Multicamino
• Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.
  
• Árboles B
• En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos 

Tipo de Operaciones: 

Las operaciones comunes en árboles son:

• Enumerar todos los elementos.
• Buscar un elemento.
• Dado un nodo, listar los hijos (si los hay).
• Borrar un elemento.
• Eliminar un subárbol (algunas veces llamada podar).
• Añadir un subárbol (algunas veces llamada injertar).
• Encontrar la raíz de cualquier nodo.

Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:

• Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.
• Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.

 Recorridos

El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas.

Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.

Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.

Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo por completo.

Partiremos del nodo raíz:

RecorrerArbol(raiz);

La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas:

void RecorrerArbol(Arbol a) \{
   if(a == NULL) return;
   RecorrerArbol(a->rama[0]);
   RecorrerArbol(a->rama[1]);
   RecorrerArbol(a->rama[2]);
}

Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.

Pre-orden

En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas:

void PreOrden(Arbol a) \{
   if(a == NULL) return;
   Procesar(dato);
   RecorrerArbol(a->rama[0]);
   RecorrerArbol(a->rama[1]);
   RecorrerArbol(a->rama[2]);
}

Si seguimos el árbol del ejemplo en pre-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:

A B E K F C G L M D H I J N O

In-orden

En este tipo de recorrido, el valor del nodo se procesa después de recorrer la primera rama y antes de recorrer la última. Esto tiene más sentido en el caso de árboles binarios, y también cuando existen ORDEN-1 datos, en cuyo caso procesaremos cada dato entre el recorrido de cada dos ramas (este es el caso de los árboles-b):
void InOrden(Arbol a) \{
   if(a == NULL) return;
   RecorrerArbol(a->rama[0]);
   Procesar(dato);
   RecorrerArbol(a->rama[1]);
   RecorrerArbol(a->rama[2]);
}
Si seguimos el árbol del ejemplo en in-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:
K E B F A L G M C H D I N J O

Post-orden
En este tipo de recorrido, el valor del nodo se procesa después de recorrer todas las ramas:
void PostOrden(Arbol a) \{
   if(a == NULL) return;
   RecorrerArbol(a->rama[0]);
   RecorrerArbol(a->rama[1]);
   RecorrerArbol(a->rama[2]);
   Procesar(dato);
}
Si seguimos el árbol del ejemplo en post-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:
K E F B L M G C H I N O J D A

Eliminacion

El proceso general es muy sencillo en este caso, pero con una importante limitación, sólo podemos borrar nodos hoja:

El proceso sería el siguiente:

1. Buscar el nodo padre del que queremos eliminar.
2. Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.
3. Liberar el nodo.
4. padre->nodo[i] = NULL;.

Cuando el nodo a borrar no sea un nodo hoja, diremos que hacemos una "poda", y en ese caso eliminaremos el árbol cuya raíz es el nodo a borrar. Se trata de un procedimiento recursivo, aplicamos el recorrido PostOrden, y el proceso será borrar el nodo.

El procedimiento es similar al de borrado de un nodo:

1. Buscar el nodo padre del que queremos eliminar.
2. Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.
3. Podar el árbol cuyo padre es nodo.
4. padre->nodo[i] = NULL;.

En el árbol del ejemplo, para podar la rama 'B', recorreremos el subárbol 'B' en postorden, eliminando cada nodo cuando se procese, de este modo no perdemos los punteros a las ramas apuntadas por cada nodo, ya que esas ramas se borrarán antes de eliminar el nodo.

De modo que el orden en que se borrarán los nodos será:

K E F y B

Arbol Binario

Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.

Operaciones

El repertorio de operaciones que se pueden realizar sobre un ABB es parecido al que realizábamos sobre otras estructuras de datos, más alguna otra propia de árboles:
Buscar un elemento.
Insertar un elemento.
Borrar un elemento.
Movimientos a través del árbol:
Izquierda.
Derecha.
Raiz.
Información:
Comprobar si un árbol está vacío.
Calcular el número de nodos.
Comprobar si el nodo es hoja.
Calcular la altura de un nodo.
Calcular la altura de un árbol.
Videos:


Imagenes